2020-01-02 16:16:54 vic_torsun 阅读数 87
  • 安卓编译与开发、Linux内核及驱动

    安卓编译与开发、Linux内核及驱动视频教程,该课程内容包括一、源码编译:1、常见的ROM种类、谷歌的ROM、第三方的ROM2、区别3、RockChip的ROM、4、编译环境配置、源码下载、编译命令;二、源码开发:源码结构分析、Launcher开发、需求分析、系统级应用;三、内核讲解:内核用途、内核结构、内核职能、内核源码编译、驱动开发;四、内核开发:1、体系架构、目录结构、中断机制、内核进程控制、2、内核库文件、例子简单分析、3、内核调度流程4、内核组件工具 嘉宾介绍:仝利,英文名Burning,CSDN博客讲师,多年主要从事于流媒体,网络通讯,p2p等技术的开发与研究。目前在创业,产品是面向企业会议室和家庭客厅的多媒体通讯盒子的开发。国内还没有相关产品,预计产品会在8月份上市。

    9147 人正在学习 去看看 CSDN讲师

1. P2P系统

  1. 既是客户端consumer也是服务器端
    producer+consumer=prosumer
  2. 任何时候都有加入或离开的自由
  3. 无限的peer diversity: 服务能力、存储空间 、网络带宽和服务需求
  4. 开放的广域无中心分布系统

2. 混合式P2P网络(第一代)

C/S式集中目录查询,P2P式下载
Peers连接到能提供共享内容的中心目录上,匹配请求与索引
文件直接在两个Peers间交换

2.1. P2P网络先驱 Napster

C/S式集中目录查询,P2P式下载
Peers连接到能提供共享内容的中心目录上,匹配请求与索引
文件直接在两个Peers间交换

Napster的缺点:
C/S的单点故障、系统瓶颈、可扩展性低
未考虑不同用户的能力差异、无鼓励机制
版权问题

2.2. 分片优化的BitTorrent

BT下载,首先需要一个种子文件,种子文件包含以下数据:
announce - tracker的URL(tracker是特殊的服务器,帮助peers之间联系)
info - 该条映射到一个字典,该字典的键将取决于共享的一个或多个文件:
name - 建议保存的文件名(一个文件)和目录名称(多个文件)
piece length - 每个文件块的字节数。通常256KB = 262144B
pieces - 每个文件块的SHA-1的集成Hash。因为SHA-1会返回160-bit的Hash,所以pieces将会得到1个160-bit的整数倍的字符串。
length - (只有一个文件时)文件的大小
files - (多个一个文件时)一个字典的列表(每个字典对应一个文件)与以下的键:
path - 一个对应子目录名的字符串列表,最后一项是实际的文件名称
length - 文件的大小(以字节为单位)

上载
 某Peer想要共享文件或目录,则为该文件或目录生成一“种子”文件
 然后把该“种子”上传到BT网站上
下载
 需下载的Peer到BT网站上
找到所需种子根据种子信息进行下载

  1. 用户通过BT网站搜索文件,得到.torrent文件列表
  2. 用户选择列表中的一项或多项
    每个被选.torrent文件会启动一项下载任务
    通常.torrent会指向该文件对应的Tracker,而Tracker会把一部分用户信息给请求者
  3. 用户根据Tracker用户信息
    与其它用户建立连接从它们下载文件分片,也提供分片
  4. 高速高效
    并不总是和最初邻居交换分片,而是每隔一段时间从Tracker获得新的邻居
    采用“阻塞算法”主动停止那些对自己无贡献的邻居,寻求更好的邻居

2.2.1. BitTorrent原理

协议
种子文件上传下载、Peers和Tracker间通信都是使用HTTP协议
各Peers间通信使用BitTorrent Peer协议(TCP)
问题
Tracker的单点失效
未对Peers身份认证
开发
BitTorrent协议公开,任何人可开发服务器端或客户端
国内流行BitComet,用Python语言开发

2.2.2. BitTorrent的阻塞算法

防止邻居仅仅下载不上传:每个用户一直保持4个邻居的疏通。每隔20秒(10+10)轮询,每隔10s决定将上传数据给自己速率最低的邻居设置为Choking状态,并保持该状态10s,10s足够TCP调整传输率到最大。如果还是处于Choking,就换邻居。
新的邻居加入后,可能会提高下载带宽,就找到了更好的邻居。那么一个新的用户,不拥有任何分片也就不能上传,会不会被一直Choking?
优化疏通(Optimistic unchoking):在任何时候,每个peer都拥有一个称为“optimistic unchoking”的连接,这个连接总是保持疏通状态,而不管它的下载速率是怎样。每隔30秒,重新计算一次哪个连接应该是“optimistic unchoking”。30秒足以让下载能力也相应的达到最大,这样即使是个新加入者,也有机会下载分片

2.3. 优缺点总结

拓扑结构:服务器仍然是网络的核心
底层协议:全部使用TCP,限制了链接的Peer数量
查询与路由简单高效:
Napster和BT的用户访问服务器;服务器返回文件索引或种子文件;用户再直接同另一Peer连接故路由跳数为O(1),即常数跳
容错、自适应和匿名性
服务器单点失效率高
自组织和自适应主要依靠服务器
服务器的存在使匿名性实际不可能
用户接入无安全认证机制

3. 无结构P2P网络(第二代)

过程:洪泛请求模式
每个Peer的请求直接广播到连接的Peers
各Peers又广播到各自连接的Peers
直到收到应答或达到最大洪泛步数(典型5-9步)
特点
可智能发现节点,完全分布式
大量请求占用网络带宽,可扩展性并不一定最好,
协议
Gnutella/KaZaA/eDonkey/Freenet使用该模式
消息协议:用于节点间相互发现和搜索资源
下载协议:用于两节点间传输文件(使用标准的HTTP协议:GET)
改进
Kazaa 设立Super-Peer客户软件,以集中大量请求
Cache最近请求

何为无结构或结构化P2P
根本区别在于每个peer所维护的邻居是否能够按照某种全局方式组织起来以利于快速查找。
无结构网络优点
将重叠网络看作一个完全随机图,结点之间的链路不遵循某些预先定义的拓扑来构建。
容错性好,支持复杂查询
结点频繁加入和退出,但对系统的影响小。

3.1. Gnutella

纯分布式对等
每个Peer即使服务器也是客户机
每个Peer监视网络局部的状态信息,相互协作

工作过程
原始加入:必须首先连接到一个“众所周知”几乎总是在线的【或称中介、自举、入口】节点(功能同一般Peer),进入Gnutella网
查询和应答消息采用广播或回播(Back-propagate)机制
每条消息被一个全局唯一16字节随机数编码为GUID(128 bit)
每个节点缓存最近路由的消息,以支持回播或阻止重广播
每条消息都有一个TTL数,每跳一次减少一次

3.1.1. Gnutella的问题与改进

由于Gnutella每个节点链接数量有限:
 洪泛广播加重网络带宽负担,受TTL限制,消息只能达到一定范围,这又导致有些文件不能查询到

改进:分层P2P=增加超级节点负责查询消息的路由,构成P2P骨干网,叶节点只是通过超级节点代理接入

3.2. 基于超节点的KaZaA

基于FastTrack协议,主要用于MP3 music files共享
比Gnutella更早引入SuperNode
KaZaA是专有协议,对消息加密,存在超级和普通两类节点
超级:高带宽、高处理能力、大存储容量、不受NAT限制
普通:低带宽、低处理能力、小存储容量、受NAT限制
加入、上载与查询
普通节点选择一超级节点作为父节点加入,并维持半永久TCP连接
将自己贡献的文件元数据、描述符上传给它,并生成Hash值
父超节点根据文件描述符关键字查询,返回文件所在IP地址+元数据

3.3. eDonKey/eMule/Overnet

eDonKey,2000年, Jed McCaleb创立专注文件下载
与BT类似,文件分块下载;内容Hash作完整性验证,服务器为核心
BT是基于文件、由 Tracker服务器来查询、搜索和跟踪用户;但eDonKey是基于用户的类似KaZaA的超级节点。

3.4. 无结构网络P2P总结

容错性与自适应
幂率特性对随机节点失效有高容错性
自适应:检测邻居在线否
超级节点列表定期更新
可扩展性
改造洪泛提高可扩展性
安全性与匿名性
无结构不易追踪
增强机制—复制
查询分布:均匀、Zipf
复制份数:均匀、依查询概率比例、方根复制
优势和缺陷
高容错性和良好自适应性,较高安全性和匿名性
路由效率低/可扩展差/准确定位差

4. 结构化P2P网络(第三代)

所谓结构化P2P,核心是采用DHT作为P2P节点和资源的组织方式:
Distributed Hash Table
普通的Hash Table中key和value保存在一台主机上,而DHT把key和value保存在分散的节点上,并通过Hash Table方法进行插入和查询。

DHT的特点
能自适应结点的动态加入/退出
有着良好的可扩展性、鲁棒性
结点ID分配的均匀性和自组织能力。
确定性拓扑结构可精确发现

4.1. DHT

1)一致性hash
The consistent hash function assigns each node and resource an mbit identifier using a base hash function such as SHA-1.
假设资源以(ObjectID,Info)方式保存,每个节点有NodeID,那么NodeID和ObjectID在同一空间
所以一致性hash可以非常方便的建立node和资源之间关系,即哪些node保存了哪些资源可以很容易查询到。

2)结构化路由
节点加入:开始时,获得一个NodeID,连接一个“bootstrap”节点,加入P2P网络
发布资源:生成资源的ObjectID,查找和ObjectID距离最近的N个Node,向这N个node广播新资源信息,告诉这些节点,我有某某资源
资源搜索:找到最靠近资源的N个node(使用NodeID 和ObjectID来计算距离远近),向这些node发送资源查询信息,如果有这个资源的详细信息,就返回给客户端,否则返回离资源更近的node列表给客户端,直到查询到资源提供者信息。
资源下载:如果没查到资源提供者信息,且没有更近的node了,那就说明这个资源没有提供者,如果找到资源提供者信息(NodeID,ip,port)后,向这个资源提供者请求
多个节点有相同资源,那么资源搜索得到一个资源提供者列表,可以开始P2P的下载
结构化路由和洪泛路由的区别:有目的、有针对性的路由

4.2. Chord

环形P2P网络
Chord:优美而精确的P2P网络
在N个节点的网络,每个节点保存O(logN)个其它节点的信息
在O(logN)跳内可找到存储数据对象的节点
节点离开或加入网络时,保持Chord自适应所需消息数O(log2N)=O((logN)2)
可提供数据对象的存储、查询、复制和缓冲
在其上构架有协同文件系统CFS(Cooperative File System)

4.2.1. 工作原理

4.2.1.1. ID的分配

通过hash函数(如SHA-1) (Secure Hash Standard)
NodeID=H(node属性)=H(IP地址/端口号/公钥/随机数/或其组合)
ObjectID=H(object属性)=H(数据名称/内容/大小/发布者/或其组合)
SHA-1的长度值m=160 Bits,从而保证其唯一性和几乎不重复性,故nodeID/objectID均可在[0…2^m)中选取

4.2.1.2. 索引的分配

NodeID从小到大、顺时针排列于1个环上
数据对象k(即ObjectID=k)也按环上顺时针方向,分配到节点k或第一个比k大 (因为环,需要mod 2^m ) 的节点上。这个节点称为Successor(k)节点
形式化表示 Successor(objectk) = nodek 或 nodex ,x是现存网上顺时针第一个大于k的节点

4.2.1.3. 节点路由表的分配

按上述后继关系,Chord显然可以正确工作
但查询效率低下,比如要找ObjectID=K的资源,首先要询问K节点是否存在,然后找K+1,最坏情况要顺序查询O(N)个节点。
所以Chord引入finger table来优化, finger table实际类似路由表:使每步更快接近目的节点

指向表:finger table
每个node存储大小为m的路由表(finger table),以减少路由跳数
节点n的路由表中,第i项指向节点 s = Successor(n+2^i-1),1≤i≤m
故s是在顺时针方向到节点n的距离至少为2^(i-1)的第一个节点:记作n.finger[i].node
除了对象k有Successor,节点n也有Successor节点就是n.finger[1].node
一个路由表项还包括相关节点的NodeID和IP地址、端口号

特点
每节点只保存很少其它节点信息,且对离它越远的节点所知越少
节点不能从自己的路由表中直接看出对象k的后继节点

4.2.1.4. 查找资源(不修改finger)

有了finger table后,就可以快速查找一个key的Successor:
假设k是ObjectID,要找到保存k的Succesor(k)节点,从n节点开始查找 (n可以是任意一个节点)
节点n在自己的路由表中寻找在k之前且离k最近的节点j,让j去找离k进一步最近的节点,如此递归下去,j将离k越来越近,最终找到n’
n’就是在k之前而且离k最近的节点
那么n’的Successor就是要找到的节点Succesor(k)

4.2.1.5. 新节点加入(修改finger)

论文在一个新节点加入到Chord后,为了更新finger table,每个节点除了Successor还有一个Predecessor节点
前驱节点:Predecessor(n)
在节点n之前,不等于n且离n最近的节点Predecessor(n)

4.2.1.6. Chord中节点离开

左图Node 6加入每个节点路由表的变化(灰色是不变)
右图Node 1离开每个节点路由表的变化(论文中错误标记为Node 3)
(另外:Node 1离开后,Node 0的finger table第一项应该是3)

在这里插入图片描述

4.2.2. 协同文件系统CFS简介

CFS是以Chord作为基础的P2P只读文件存储系统
依靠Chord作为其分布式HASH表,提供高效、容错和负载均衡的文件存储和获取
系统由文件系统FS、分布式散列表DHash和底层定位散列表Chord三层构成
每个节点既是服务器又是客户机
功能说明
FS:高层,从DHash层获取数据块,将这些块转换成文件,给更高层文件系统接口
DHash:中间层,分布和缓存数据块以负载平衡,复制数据块以容错,通过服务器选择来减少延迟,用Chord定位数据块
Chord:底层,维护路由表,定位数据块所在的服务器。每个服务器就是Chord的一个节点

4.2.3. Chord:总结

简单、精确,但要求
每个节点的后继节点始终准确
每个对象k的后继节点始终承担k的索引
查询与维护代价
查询代价:m项的平均间隔 delta = [2^0+ 2^1+… +2^m-1]/m ;设经J跳命中,覆盖节点数≤2^m ;故 J*delta≤2^m ;故有J≤m = O(log N) ;一次查询的路由平均跳数为O(logN)
维护代价:节点的进/出,自适应到最新状态需O(log2N)
缺点:
没有实际使用(只有一个文件共享应用)
不支持非精确查找
finger table有冗余
维护finger table(加入/退出)代价比较高

Chord的问题
(1):finger table有冗余
以 2^i 为跨度来寻找路由表中的后继节点,这会在 finger 中产生一定的冗余量,即节点稀疏的时候,路由容易冗余

(2):路由维护开销大
节点加入:Chord需要环形拓扑中的任意一个节点来协助完成,且加入过程包括新节点本身的Join操作和修改其他节点finger表两个阶段;
节点失效的处理:Chord需要周期性对节点的前继节点和后继节点进行探测,并按照节点加入时的算法重建Finger表;
对于节点退出的处理:Chord采取了将节点的退出当作为失效来处理的方式。

4.3. 结构化P2P网络Kademlia

Kademlia和Chord类似,属于常数度P2P网络
路由、定位、自组织方式与前4种区别不大
每个节点的“度”(连接数)是固定的,与规模无关
维护固定路由表项,仍能达到O(logN)跳的指数定位效率
路由表固定导致网络自适应开销减少
更容错实用的结构化网络Kademlia
路由方法类似Chord
加入、离开节点更加简单

4.3.1. 节点间的异或距离

定义两个节点x,y(ID值表示)的“异或”距离(非欧距离)
节点与数据对象都用SHA-1分配160 Bits ID,
对象索引由与objectID最接近的nodeID负责,“最接近”由XOR距离度量
d(x,y)=x⊕y,如1011⊕0010=1001=9 > 1011⊕1010=0001=1

异或距离的性质:
合理性: d(x,x)= 0
非负性: d(x,y)≥ 0
对称性: d(x,y) = d(y,x) ,对任何x,y,且 x≠y. (Chord不具备)
三角不等式: d(x,y)+d(y,z)≥ d(x,z)
因为d(x,z) = d(x,y)⊕d(y,z)
对任意 a≥0, b≥0 , a+b≥ a⊕b
单向性:任意节点x和距离d,系统中仅有唯一节点一y满足d(x,y)=d
单向性保证相同数据的定位最终将会汇聚于相同的路径
传递性:显然 if d1≥d2 and d2≥d3 ,then d1≥d3 成立

4.3.2. 异或距离结构性好处

按当前节点ID与所有其它节点ID间XOR距离大小排队,知道目标结点ID后,就很容易计算出目标节点在这条队列中的位置;

如果给定一个异或距离,你也能很容易从这条队列里找出与该距离最接近的那些结点

与自己前缀相似度越高的结点离自己越近(异或之后高位为0)

4.3.3. K-桶路由表

K-buckts:每节点维护一个路由表,它由logN(N为最大节点数)个k桶构成
实质是一个链表集,每节点 0≤i<160个桶;每桶内装Max个(10或20)记录=(序号i,到自己的异或距离[2i—2i+1),节点信息)
节点信息 = <IP,端口,节点ID >三元组
表项以访问时间排序,最久(least-recently)访问的放在尾部,最近(mostrecently)访问的放在头部

4.4. BitCoin和区块链

4.4.1. 非对称加密

Bitcoin使用椭圆曲线算法,一把私钥可以推出唯一的公钥,反之不行。

4.4.2. 交易

通过关联一个密钥的方式将钱赋予一个新的所有者。

4.4.3. 比特币区块

多个比特币交易会打包在一个区块中,每个区块大小是1Mbyte
每个交易都会有一个唯一的ID,在区块的tx数组中
每个交易vin中包含的比特币数量减去vout中的比特币数量就是交易费

4.4.4. 比特币区块链

比特a区块链接为一个单链表
每个区块中保存了前一个区块hash值,因此任何人想要篡改链中一个区块,会导致破坏整个区块 链,被P2P网络其他节点发现。
比特币网络中矿工负责打包区块,任何人都可以成为矿工。
如果不同矿工如右图在不同链上打包区块怎么?全网承认的是最长链(工作量最大)

矿工都可以竞争打包过程,关键是看谁先计算出一个合法的nonce,让当前区块hash值前面有规定个数的0(比如5个)

0的个数由全网hash能力决定,每隔一段时间调整,大概十分钟能计算成功。

打包成功的矿工,交易费归他所有。

4.4.5. 区块链竞争

在这里插入图片描述

2019-08-16 21:16:29 zll_0405 阅读数 312
  • 安卓编译与开发、Linux内核及驱动

    安卓编译与开发、Linux内核及驱动视频教程,该课程内容包括一、源码编译:1、常见的ROM种类、谷歌的ROM、第三方的ROM2、区别3、RockChip的ROM、4、编译环境配置、源码下载、编译命令;二、源码开发:源码结构分析、Launcher开发、需求分析、系统级应用;三、内核讲解:内核用途、内核结构、内核职能、内核源码编译、驱动开发;四、内核开发:1、体系架构、目录结构、中断机制、内核进程控制、2、内核库文件、例子简单分析、3、内核调度流程4、内核组件工具 嘉宾介绍:仝利,英文名Burning,CSDN博客讲师,多年主要从事于流媒体,网络通讯,p2p等技术的开发与研究。目前在创业,产品是面向企业会议室和家庭客厅的多媒体通讯盒子的开发。国内还没有相关产品,预计产品会在8月份上市。

    9147 人正在学习 去看看 CSDN讲师

在上篇文章中说过,要写写 P2P 协议的,嗯,来写写,虽然写的不是太好.

P2P 是什么?
还是要回到这个场景:
如果想要下载一个电影,一般都是通过什么方式呢?
我希望这次你的答案,除了 HTTP 方式,还有 FTP 方式(要不上篇文章岂不是白写了?)
但是你发现了嘛,不管是 HTTP 的方式,还是 FTP 的方式,都有一个比较大的缺点,就是难以解决单一服务器的带宽压力,因为它们使用的都是传统的客户端服务器的方式.
这个时候,一种创新的, P2P 协议就开始流行起来. P2P 就是 peer-to-peer .
传统的方式不是把资源都集中地存储在某些设备上了嘛,那我就创新一下,我不让这些资源都集中在某些设备上了,我让这些资源都分散的存储在多台设备上面去.这些设备,为了理解方便,我们称为 " peer "

那么,当我想要下载一个文件的时候,我只要得到那些已经存在了文件的 peer ,和这些 peer 建立点对点的连接,而不需要到中心服务器上面去,我就可以就近下载文件了.
一旦下载了文件,你也就成为了 peer 中的一员,你旁边的那些机器,也可能会选择从你这里下载文件.
所以当你使用 P2P 软件的时候,往往能够看到,它既有下载的流量,也有上传的流量,也就是说,你自己也加入了这个 P2P 的网络,自己从别人那里下载,同时也提供给其他人下载.
你可以想一下,这种方式,是不是参与的人越多,下载速度就越快,一起简直是完美啊~

种子 (.torrent )文件
这里其实是有一个问题的,当我想要下载一个文件的时候,我怎么知道哪儿些 peer 有这个文件呢?
这就是种子文件,也就是「 torrent」文件.它由两部分组成: announce ( tracker URL )和文件信息.

  • 文件信息里面有这些内容:
    • info 区:这里指定的是该种子有几个文件,文件有多长,目录结构,以及目录和文件的名字;
    • Name 字段:指定顶层目录名字;
    • 每个段的大小: BitTorrent ( 简称 BT )协议把一个文件分成很多个小段,然后分段下载;
    • 段哈希值:将整个种子中,每个段的 SHA-1 哈希值拼在一起.

下载时, BT 客户端首先解析 .torrent 文件,得到 tracker 地址,然后连接 tracker 服务器. tracker 服务器回应下载者的请求,将其他下载者(包括发布者)的 IP 提供给下载者.下载者再连接其他下载者,根据 .torrent 文件,两者分别告诉对方自己已经有的数据,然后交换对方没有的数据.这个时候,就不需要其他服务器的参与,就分散了单个线路上的数据流量,从而减轻了服务器的负担.

从上面的过程,我们能够看出, P2P 这种方式特别依赖 tracker . tracker 需要收集下载者信息的服务器,并且将这些信息提供给其他下载者,使得下载者们相互之间能够连接起来,传输数据.虽然说,在整个下载的过程中,是非中心化的,但是加入这个 P2P 网络的时候,都需要借助 tracker 中心服务器,因为 tracker 服务器是用来登记有哪些用户在请求哪些资源.
到这里你可能就会比较清楚了,这种方式的限制就是 tracker 服务器.只要它出现故障或者线路遭到屏蔽, BT 工具就没办法再正常工作了.

去中心化网络( DHT )
在整个下载的过程中,是非中心化的,但是它还是受限制的.那到底能不能做到彻底非中心化呢?
所以就有了 DHT ( Distributed Hash Table )的去中心化网络.每一个加入这个 DHT 网络的人,都要负责存储这个网络中的资源信息和其他成员的联系信息,相当于所有人一起构成了一个庞大的分布式存储数据库.
在这里有一种著名的 DHT 协议,叫 Kademlia 协议.

Kademlia 协议详解
在 Kademlia 协议中,任何一个 BitTorrent 启动之后,它都有两个角色.一个是 peer ,监听一个 TCP 端口,用来上传和下载文件,这个角色就是为了说明,我这里有某个文件.另一个角色 DHT node ,监听一个 UDP 的端口,通过这个角色,这个节点加入了一个 DHT 的网络.
在 DHT 网络中,每一个 DHT node 都有一个 ID .这个 ID 是一个很长的串.每个 DHT node 都有责任掌握一些知识,也就是文件索引,也就是说,它应该知道某些文件是保存在哪些节点上.它只需要知道这些东西就行了,不一定就是保存这个文件的节点.
这样我想要实现去中心化就好实现了.

以上就是想要分享的内容了,感谢您的阅读~

2018-06-28 21:24:59 championhengyi 阅读数 2059
  • 安卓编译与开发、Linux内核及驱动

    安卓编译与开发、Linux内核及驱动视频教程,该课程内容包括一、源码编译:1、常见的ROM种类、谷歌的ROM、第三方的ROM2、区别3、RockChip的ROM、4、编译环境配置、源码下载、编译命令;二、源码开发:源码结构分析、Launcher开发、需求分析、系统级应用;三、内核讲解:内核用途、内核结构、内核职能、内核源码编译、驱动开发;四、内核开发:1、体系架构、目录结构、中断机制、内核进程控制、2、内核库文件、例子简单分析、3、内核调度流程4、内核组件工具 嘉宾介绍:仝利,英文名Burning,CSDN博客讲师,多年主要从事于流媒体,网络通讯,p2p等技术的开发与研究。目前在创业,产品是面向企业会议室和家庭客厅的多媒体通讯盒子的开发。国内还没有相关产品,预计产品会在8月份上市。

    9147 人正在学习 去看看 CSDN讲师

结构化与非结构化网络

非结构化的 P2P 网络是指网络节点之间不存在组织关系,节点之间完全是对等的,比如第一代 P2P 网络 Napster。

结构化的 P2P 网络与非结构化恰好相反,我们认为网络在逻辑上存在一个人为设计的结构,比如 Chord 假定网络是一个环,Kadelima 则假定为一颗二叉树。有了这些逻辑结构,就给我们资源查找引入了更多的算法和思路。


引言

我们在 计算机网络–详解P2P对等网络(一)—BitTorrent协议 这一篇博客中讲述了 BT 下载的过程:在对等用户拿到种子文件的时候,首先会联系 tracker 服务器,然后加入用户集群,并在用户集群中寻找自己所需的内容,最后与拥有内容的对等用户进行联系。

从 BT 下载的过程中引出本节所要讨论的问题:如何高效的从用户集群中找出哪些对等用户拥有你正在寻求的具体内容?

在历史中有三种比较典型的模型来解决这个问题:

  • Napster:使用一个中心服务器接收所有的查询,服务器告知去哪下载其所需要的数据。存在的问题是中心服务器单点失效导致整个网络瘫痪。

  • Gnutella:使用消息洪泛(message flooding)来定位数据。一个消息被发到用户集群内每一个节点,直到找到其需要的数据为止。存在的问题是消息数与节点数成线性关系,导致网络负载较重。

  • SN 型:超级节点(Super Node),SN 保存网络中节点的索引信息,这一点和中心服务器类型一样,但是网内有多个 SN,其索引信息会在这些 SN 中进行传播,所以整个系统的崩溃几率就会小很多。尽管如此,网络还是有崩溃的可能。

关于 P2P 网络拓扑结构更详细的内容,请参考:P2P网络的拓扑结构

现在的研究结果中,Chord、Pastry、CAN 和 Tapestry 等常用于构建结构化 P2P 的分布式哈希表系统。

Chord 算法是麻省理工学院(MIT)提出的一种基于 DHT 技术的结构化 P2P 路由协议,具有完全分布式、负载均衡、可用性及可扩展性好、命名方式灵活等特点。本文主要对 Chord 算法展开分析。


分布式哈希表(DHT)

对于本节问题的思考,我们可以给出一种基本的解决方案:每个对等节点维护了一张路由表(索引),这张路由表只保存了少量有关其他节点的信息,这个特点意味着它保持最新索引的代价不会很昂贵。其次,每个节点可以快速的查看索引中的表项,否则,它就不是个有效的索引。最后,每个节点可以同时使用索引,即使其他节点来来去去,这个属性意味着索引的性能随着节点数量的增长反而越来越好~

该解决方案就被称为分布式哈希表,因为对等节点所维护的路由表就是一张索引表,而索引的基本功能就是将一个关键字映射到一个值。这简直就是一张哈希表,但是我们的解决方案是分布式版本。我们可以再看一下维基对于 DHT 的定义:

分布式哈希表(distributed hash table,缩写DHT):分布式计算系统中的一类,用来将一个关键值(key)的集合分散到所有在分布式系统中的节点,并且可以有效地将消息转送到唯一一个拥有查询者提供的关键值的节点(Peers)。这里的节点类似散列表中的存储位置。分布式散列表通常是为了拥有极大节点数量的系统,而且在系统的节点常常会加入或离开(例如网络断线)而设计的。在一个结构性的覆盖网络(overlay network)中,参加的节点需要与系统中一小部分的节点沟通,这也需要使用分布式散列表。

上述我特意加粗的语句,正是对 P2P 网络架构的描述。

如果对于 DHT 的概念还抱有一定的疑惑,可以在网上搜寻更白话的说明,博主不再进行贴出。

DHT与一致性哈希

如上所述,DHT 的主要想法是把网络上资源的存取像哈希表一样,可以简单而快速地进行put、get。与一致性哈希相比,DHT 更强调的是资源的存取,而不管添加删除节点时产生的资源震荡的问题。与一致性哈希相同的是,DHT 也只是一个概念,具体细节留给各实现。

当前这些 P2P 实现可以被作为 DHT 的具体实现,再次列举一些有代表性的实现:

Chord、CAN、Tapestry、Pastry、Apache Cassandra、Kadelima、P-Grid、BitTorrent DHT


Chord算法

Chord是什么?

Chord 是一个算法,也是一个协议。作为一个算法,Chord 可以从数学的角度严格证明其正确性和收敛性;作为一个协议,Chord 详细定义了每个环节的消息类型。当然,Chord 之所以受追捧,还有一个主要原因就是 Chord 足够简单,3000 行的代码就足以实现一个完整的 Chord。

Chord概述

Chord 的实现方式如下:给定一个关键字 Key,将其映射到某个节点。为此,采用相同哈希函数(SHA-1)为每个节点和关键字产生一个 m bit 的 ID,并按照 ID 大小构成环形拓扑。节点所产生的 ID 被称为节点标识符,关键字所产生的 ID 我们称它为关键字 ID。运行 Chord 的主机相互连接构成 Chord 网络,这是一个建立在 IP 网络之上的覆盖(overlay)网络。每个节点 N 有 2 个邻居:以顺时针为正方向排列在 N 之前的第 1 个节点称为 N 的前继(predecessor),在 N 之后的第 1 个节点称为 N 的后继(successor)。如下图(蓝色节点为节点 ID,白色节点为关键字 ID):

此处输入图片的描述

同一致性哈希一样,资源放置在关键字 ID 的后继节点上,如上图,资源 2 被放置在节点 3 中。

Finger表

我们在本篇博客 分布式哈希表(DHT) 一节中已经讲过,每个对等节点都会维护一张路由表,以便在用户集群中寻找拥有所需资源的其他对等节点。这张路由表就被称为 Finger 表,Finger 表的表项大小为 m(哈希函数作用于节点与关键字产生的 m bit 大小的 ID),由两列数据项组成,如下:

ID+2的i次方 successor

其中 ID 就代表节点标识符,i 表示 Finger 表中表项的下标,从 0 开始,successor 则表示存储资源的后继节点。

举个例子:我们现在有一个 m = 3(也就是 3 个 bit)的 Chord 环,它可以容纳 2 的 3 次方,也就是 8 个节点。现在有 4 台机器,假设它们经过哈希之后所产生的 ID 为 0,1,2,6,那么机器 1 中将要维护的 Finger 表如下:

i ID+2的i次方 successor
0 2 2
1 3 6
2 5 6

其中 ID+2 的 i 次方表示的是关键字 ID。

对于上表的解释:

首先,由一致性哈希可知,机器 1 本地存储着关键字 ID 为 1 的数据,机器 2 本地存储着关键字 ID 为 2 的数据,机器 6 本地存储着关键字 ID 为 3,4,5,6 的数据,机器 0 本地存储着关键字 ID 为 7,0 的数据。

与此同时,如上表,机器 1 上还存储着关键字 ID 为 2,3,5 的数据所在的机器地址。比如,机器 1 知道,关键字 ID 为 5 的数据存储在机器 6 上面。

Chord的查找

Chord 采取幂次逼近查询法。任何一个节点收到查询关键字 ID 为“K”的请求时,首先检查 K 是否落在该节点标识和它的后继节点标识之间,如果是的话,这个后继节点就是存储目标(K, V)对的节点。否则,节点将查找它的 Finger 表,找到表中节点标识符最大但不超过 K 的节点,并将这个查询请求转发给该节点。通过重复这个过程,最终可以定位到 K 的后继节点,即存储有目标(K, V)对的节点。

比如,当机器 1 接收到查询关键字 ID 为 7 的数据在哪台机器上时,它发现关键字 ID “7”并不在该节点标识符和它的后继节点标识符之间,因此它查找节点标识符最大但没有超过 7 的节点,为 5,于是将查询请求转发到机器 6 上。

机器 6 的路由表按照上述规则进行生成,如下(环形拓扑):

i ID+2的i次方 successor
0 7 0
1 0 0
2 2 2

机器 6 上的路由表指出:关键字 ID 为 7 的数据在机器 0 上… …重复这个过程,最终可找到保存关键字 ID 为 7 的资源的节点。

通过在每台机器上保存 m 项的路由信息,上面的方式可以做到 O(logN) 的查询时间复杂度。另外,比如 Amazon Dynamo 在论文中所说:通过在每台机子上保存足够多的路由信息,理论上可以做到 O(1) 时间的查询(相应的,节点间冗余信息也会更多)。

节点的加入

新节点的加入需要一个称为向导的已知节点(n0)进行协助,任何一个运行在 Chord 网络中的节点都可以充当这个角色。加入过程包括新节点本身的 Join 操作和被其他节点发现 2 个阶段。如下图所示,假设 np 和 ns 是 Chord 网络中相邻两节点,n 为新节点,它加入网络后应该位于 np 和 ns 节点之间。

这里写图片描述

新节点的加入有三个操作:

  • Join() :n 加入一个 Chord 环,已知其中有一个向导节点 n0;
  • Stabilize(): 每个节点在后台周期性的进行此项操作,查询自身节点的后继节点的前序节点是否是自身,如果不是自身,说明有新加入的节点,此时将自身的后继节点修改为新加入的节点;
  • Notify(n): n 通知其他节点它的存在,若此时其他节点没有前序节点或 n 比其现有的前序节点更加靠近自身,则将 n 设置为前序节点。

在了解了上述三个操作之后,我们讨论一下 n 节点加入的具体过程:

  1. n 请求向导为它查找后继 (即 ns),并初始化自身 Finger 表,按照 Finger 表的定义,此时只有 n 对自身属性进行了设置,其他节点并不知道新节点的加入(如上图 a);
  2. 在 n 节点将自身的后继节点修改为 ns 后,会对 ns 进行 Notify(n) 操作,即 n 节点通知 ns 它的存在,此时 ns 标记 n 成为自己的前序节点;
  3. 所有节点会在后台周期性的进行 Stabilize 操作,此时 np 发现 ns 的前序结点已不是自身,则 np 将自己的后继节点修改为 n;
  4. np 对 n 进行 Notify(np) 操作,n 接到通知,将 np 修改为自己的前序节点。

在这里有一个问题:向导节点如何帮助新加入的节点寻找它的后继节点以及新加入的节点如何初始化其 Finger 表?

第一点:对于新节点 n,通过向向导节点提交查找 n 自身节点标识符的请求,向导节点检索其后继;
第二点:新节点通过向向导节点请求 ID + 2的m次方 从而构建 Finger 表。

节点的失效

节点的失效是节点没有通知其他节点而突然离开网络,这通常由主机崩溃或 IP 网络断开等意外原因造成,此时失效节点的前继保存的后继信息变得不可用,从而造成 Chord 环的断裂。为了处理这个问题,需要周期性的对节点的前序和后继进行探测。如果节点 n 发现其后继或前序已经失效,则从 Finger 表中顺序查找第 1 个可用节点进行替换,并重建 Finger 表。对前序节点失效的处理仍需要借助于 Notify 消息。考虑上图中的例子,ns 虽然能够感知 n 的失效却无法进行修复。由于上述对后继失效的处理过程能够保证 Chord 环后继链的正确性,因此 np 通过在 Stabilize 中向新后继 ns 发送 Notify,把 ns 的前继改成 np。值得注意的是,其他节点也可能在 Finger 表项中保存有失效节点的记录,因此需要多次 Stabilize,把失效信息扩散到Chord 网络中。虽然这种方法最终能够保证 Chord 网络的完整性,但在节点频繁进出的情况下,其效率仍须更深入地研究。

节点的退出

由于节点失效处理方法是稳定的,因此节点的退出可看作为失效而不采取其他附加措施。但基于效率的考虑,节点 n 退出时进行如下操作:1. 把 n 后继节点的前继改成 n 的前继;2. 把 n 前继节点的后继改成 n 的后继;3. 从 n 前继的 Finger 表中删除 n。


总结

  1. 熟悉 DHT、一致性哈希、Chord 算法之间的概念及联系;
  2. 熟悉 Chord 算法的思想(Finger 表的构建、Chord 查询、节点的加入等);
  3. 了解 P2P 网络的一些其它拓扑结构。

PS:关于 Chord 算法数学角度上的证明与分析,有兴趣的同学可以自行查阅相关资料~


参考阅读

计算机网络(第五版) — Andrew S. TanenBaum/David J. Wetherall

结构化P2P网络chord算法研究与分析

分布式哈希算法

【学术之门之P2P算法研读】P2P中的Chord算法

Chord算法(原理)

2020-01-06 03:34:04 qq_40167046 阅读数 11
  • 安卓编译与开发、Linux内核及驱动

    安卓编译与开发、Linux内核及驱动视频教程,该课程内容包括一、源码编译:1、常见的ROM种类、谷歌的ROM、第三方的ROM2、区别3、RockChip的ROM、4、编译环境配置、源码下载、编译命令;二、源码开发:源码结构分析、Launcher开发、需求分析、系统级应用;三、内核讲解:内核用途、内核结构、内核职能、内核源码编译、驱动开发;四、内核开发:1、体系架构、目录结构、中断机制、内核进程控制、2、内核库文件、例子简单分析、3、内核调度流程4、内核组件工具 嘉宾介绍:仝利,英文名Burning,CSDN博客讲师,多年主要从事于流媒体,网络通讯,p2p等技术的开发与研究。目前在创业,产品是面向企业会议室和家庭客厅的多媒体通讯盒子的开发。国内还没有相关产品,预计产品会在8月份上市。

    9147 人正在学习 去看看 CSDN讲师

一 混合式P2P网络(第一代)

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

二 无结构P2P网络(第二代)

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

三 结构化P2P网络(第三代)

在这里插入图片描述在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

四 Chord协议

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

五 Kademlia协议

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

六 Bitcoin以及区块链

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

2018-11-25 13:13:34 TingHW 阅读数 17817
  • 安卓编译与开发、Linux内核及驱动

    安卓编译与开发、Linux内核及驱动视频教程,该课程内容包括一、源码编译:1、常见的ROM种类、谷歌的ROM、第三方的ROM2、区别3、RockChip的ROM、4、编译环境配置、源码下载、编译命令;二、源码开发:源码结构分析、Launcher开发、需求分析、系统级应用;三、内核讲解:内核用途、内核结构、内核职能、内核源码编译、驱动开发;四、内核开发:1、体系架构、目录结构、中断机制、内核进程控制、2、内核库文件、例子简单分析、3、内核调度流程4、内核组件工具 嘉宾介绍:仝利,英文名Burning,CSDN博客讲师,多年主要从事于流媒体,网络通讯,p2p等技术的开发与研究。目前在创业,产品是面向企业会议室和家庭客厅的多媒体通讯盒子的开发。国内还没有相关产品,预计产品会在8月份上市。

    9147 人正在学习 去看看 CSDN讲师

peer - to - peer

  • 没有服务器
  • 任意端系统之间直接通信
  • 节点阶段性接入internet
  • 节点可能更换ip地址

文件分发 BitTorrent协议

  • 参与交换文件块的文件形成一个组 torrent
  • 对于每一个torrent 有一个tracker跟踪参与torrent的节点
  • 文件被划分为256kb的chunk
  • 新加入的节点,向tracker注册,获取torrent节点清单,与之建立连接,下载的同时上传自己的chunk
  • 动态加入或离开

获取chunk:

  • 给定某一时刻,不同的节点持有文件的不同chunk集合
  • 节点定期查询每个邻居所持有的chunk的列表
  • 节点发送请求,请求获取缺失的chunk(稀缺优先)

发送chunk tit-for-tat

  • 向对自己贡献最大的节点发送chunk
  • 每隔一段时间重新评估
  • 每隔一段时间随机向某个节点发送

 

bittorrent技术对网络性能有哪些潜在的危害:

  • 对硬盘的损害
  • 对网络带宽的损害
  • 助长了病毒的传播
  • 可能面临着版权侵害的风险

 

p2p 索引技术 :信息到节点位置(ip地址+端口号)的映射

  • 集中式索引(比如napster公司)(内容和文件的传输是分布式的,但是内容的定位是高度集中式的)(单点失效问题,性能瓶颈问题,版权问题)
  • 洪泛式查询(完全分布式架构,如Gnutella公司)(每个节点只对它共享的文件进行索引)(查询消息通过已有的TCP连接发送,节点转发查询消息,如果查询命中,则利用反向路径发回查询节点)
  • 层次式覆盖网络(介于以上两种,如skype)(每个节点或者是一个超级节点,或者被分配一个超级节点)

覆盖网络

  • 节点之间如果有tcp连接,那么构成一个边
  • 所有的活动节点和边构成构成覆盖网络
  • 边:虚拟链路
  • 节点一般邻居数小于十个

 

 

 

 

 

 

 

没有更多推荐了,返回首页