2023年7月27日发(作者：)

bt协议分析-DHTTracker：服务器Tracker是指运⾏于服务器上的⼀个服务程序，也称Tracker服务器。这个程序能够追踪到底有多少⼈同时在下载或上传同⼀个⽂件。客户端连上Tracker服务器，就会获得⼀个正在下载和上传的⽤户的信息列表（通常包括IP地址、端⼝、客户端ID等信息），根据这些信息，BT客户端会⾃动连上别的⽤户进⾏下载和上传。PythonPython是⽤来写BT软件的编程语⾔。DHT全称叫分布式哈希表(Distributed Hash Table)1. Kademlia简述Kademlia(简称Kad)属于⼀种典型的结构化P2P覆盖⽹络(Structured P2P Overlay Network)，以分布式的应⽤层全⽹⽅式来进⾏信息的存储和检索是其尝试解决的主要问题。在Kademlia⽹络中，所有信息均以的哈希表条⽬形式加 以存储，这些条⽬被分散地存储在各个节点上，从⽽以全⽹⽅式构成⼀张巨⼤的分布式哈希表。我们可以形象地把这张哈希⼤表看成是⼀本字典：只要知道了信息索 引的key，我们便可以通过Kademlia协议来查询其所对应的value信息，⽽不管这个value信息究竟是存储在哪⼀个节点之上。在eMule、 BitTorrent等P2P⽂件交换系统中，Kademlia主要充当了⽂件信息检索协议这⼀关键⾓⾊，但Kad⽹络的应⽤并不仅限于⽂件交换。下⽂的 描述将主要围绕eMule中Kad⽹络的设计与实现展开。2. eMule的Kad⽹络中究竟存储了哪些信息?只要是能够表述成为字典条⽬形式的信息Kad⽹络均能存储，⼀个Kad⽹络能够同时存储多张分布式哈希表。以eMule为例，在任⼀时刻，其Kad⽹络均存储并维护着两张分布式哈希表，⼀张我们可以将其命名为关键词字典，⽽另⼀张则可以称之为⽂件索引字典。a. 关键词字典：主要⽤于根据给出的关键词查询其所对应的⽂件名称及相关⽂件信息，其中key的值等于所给出的关键词字符串的 160⽐特SHA1散列，⽽其对应的value则为⼀个列表，在这个列表当中，给出了所有的⽂件名称当中拥有对应关键词的⽂件信息，这些信息我们可以简单 地⽤⼀个3元组条⽬表⽰：(⽂件名，⽂件长度，⽂件的SHA1校验值)，举个例⼦，假定存在着⼀个⽂件 “warcraft_frozen_”，当我们分别以“warcraft”、“frozen”、“throne”这三个关键词来查询 Kad时，Kad将有可能分别返回三个不同的⽂件列表，这三个列表的共同之处则在于它们均包含着⼀个⽂件名为“warcraft_frozen_”的信息条⽬，通过该条⽬，我们可以获得对应iso⽂件的名称、长度及其160⽐特的SHA1校 验值。b. ⽂件索引字典：⽤于根据给出的⽂件信息来查询⽂件的拥有者(即该⽂件的下载服务提供者)，其中key的值等于所需下载⽂件的 SHA1校验值(这主要是因为，从统计学⾓度⽽⾔，160⽐特的SHA1⽂件校验值可以唯⼀地确定⼀份特定数据内容的⽂件)；⽽对应的value也是⼀个 列表，它给出了当前所有拥有该⽂件的节点的⽹络信息，其中的列表条⽬我们也可以⽤⼀个3元组表⽰：(拥有者IP，下载侦听端⼝，拥有者节点ID)，根据这 些信息，eMule便知道该到哪⾥去下载具备同⼀SHA1校验值的同⼀份⽂件了。3. 利⽤Kad⽹络搜索并下载⽂件的基本流程是怎样的?基于我们对eMule的Kad⽹络中两本字典的理解，利⽤Kad⽹络搜索并下载某⼀特定⽂件的基本过程便很明⽩了，仍以“warcraft_frozen_”为例，⾸先我们可以通过warcraft、frozen、throne等任⼀关键词查询关键词 字典，得到该iso的SHA1校验值，然后再通过该校验值查询Kad⽂件索引字典，从⽽获得所有提供“warcraft_frozen_”下载的⽹络节点，继⽽以分段下载⽅式去这些节点下载整个iso⽂件。在上述过程中，Kad⽹络实际上所起的作⽤就相当于两本字典，但值得再次指出的是，Kad并不是以集中的索引服务器(如华语P2P源动⼒、 Razorback 2、DonkeyServer 等，骡友们应该很熟悉吧)⽅式来实现这两本字典的存储和搜索的，因为这两本字典的所有条⽬均分布式地存储在参与Kad⽹络的各节点中，相关⽂件信息、下载 位置信息的存储和交换均⽆需集中索引服务器的参与，这不仅提⾼了查询效率，⽽且还提⾼了整个P2P⽂件交换系统的可靠性，同时具备相当的反拒绝服务攻击能 ⼒；更有意思的是，它能帮助我们有效地抵制FBI的追捕，因为俗话说得好：法不治众…看到这⾥，相信⼤家都能理解“分布式信息检索”所带来的好处了吧。但 是，这些条⽬究竟是怎样存储的呢?我们⼜该如何通过Kad⽹络来找到它们?不着急，慢慢来。4. 什么叫做节点的ID和节点之间的距离?Kad⽹络中的每⼀个节点均拥有⼀个专属ID，该ID的具体形式与SHA1散列值类似，为⼀个长达160bit的整数，它是由节点⾃⼰随机⽣成的， 两个节点拥有同⼀ID的可能性⾮常之⼩，因此可以认为这⼏乎是不可能的。在Kad⽹络中，两个节点之间距离并不是依靠物理距离、路由器跳数来衡量的，事实 上，Kad⽹络将任意两个节点之间的距离d定义为其⼆者ID值的逐⽐特⼆进制和数，即，假定两个节点的ID分别为a与b，则有：d=a XOR b。在Kad中，每⼀个节点都可以根据这⼀距离概念来判断其他节点距离⾃⼰的“远近”，当d值⼤时，节点间距离较远，⽽当d值⼩时，则两个节点相距很近。 这⾥的“远近”和“距离”都只是⼀种逻辑上的度量描述⽽已；在Kad中，距离这⼀度量是⽆⽅向性的，也就是说a到b的距离恒等于b到a的距离，因为a XOR b==b XOR a5. 条⽬是如何存储在Kad⽹络中的?从上⽂中我们可以发现节点ID与条⽬中key值的相似性：⽆论是关键词字典的key，还是⽂件索引字典的key，都是160bit，⽽节点ID恰恰 也是160bit。这显然是有⽬的的。事实上，节点的ID值也就决定了哪些条⽬可以存储在该节点之中，因为我们完全可以把某⼀个条⽬简单地存放在节点ID 值恰好等于条⽬中key值的那个节点处，我们可以将满⾜(ID==key)这⼀条件的节点命名为⽬标节点N。这样的话，⼀个查找条⽬的问题便被简单地转化 成为了⼀个查找ID等于Key值的节点的问题。由于在实际的Kad⽹络当中，并不能保证在任⼀时刻⽬标节点N均⼀定存在或者在线，因此Kad⽹络规定：任⼀条⽬，依据其key的具体取值，该条⽬ 将被复制并存放在节点ID距离key值最近(即当前距离⽬标节点N最近)的k个节点当中；之所以要将重复保存k份，这完全是考虑到整个Kad系统稳定性⽽ 引⼊的冗余；这个k的取值也有讲究，它是⼀个带有启发性质的估计值，挑选其取值的准则为：“在当前规模的Kad⽹络中任意选择⾄少k个节点，令它们在任意 时刻同时不在线的⼏率⼏乎为0”；⽬前，k的典型取值为20，即，为保证在任何时刻我们均能找到⾄少⼀份某条⽬的拷贝，我们必须事先在Kad⽹络中将该条 ⽬复制⾄少20份。由上述可知，对于某⼀条⽬，在Kad⽹络中ID越靠近key的节点区域，该条⽬保存的份数就越多，存储得也越集中；事实上，为了实现较短的查询响应 延迟，在条⽬查询的过程中，任⼀条⽬可被cache到任意节点之上；同时为了防⽌过度cache、保证信息⾜够新鲜，必须考虑条⽬在节点上存储的时效性： 越接近⽬标结点N，该条⽬保存的时间将越长，反之，其超时时间就越短；保存在⽬标节点之上的条⽬最多能够被保留24⼩时，如果在此期间该条⽬被其发布源重 新发布的话，其保存时间还可以进⼀步延长。6. Kad⽹络节点需要维护哪些状态信息?在Kad⽹络中，每⼀个节点均维护了160个list，其中的每个list均被称之为⼀个k-桶(k-bucket)，如下图所⽰。在第i个 list中，记录了当前节点已知的与⾃⾝距离为2^i~2^(i+1)的⼀些其他对端节点的⽹络信息(Node ID，IP地址，UDP端⼝)，每⼀个list(k-桶)中最多存放k个对端节点信息，注意，此处的k与上⽂所提到的复制系数k含义是⼀致的；每⼀个 list中的对端节点信息均按访问时间排序，最早访问的在list头部，⽽最近新访问的则放在list的尾部。k-桶中节点信息的更新基本遵循Least-recently Seen Eviction原则：当list容量未满(k-桶中节点个数未满k个)，且最新访问的对端节点信息不在当前list中时，其信息将直接添⼊list队 尾，如果其信息已经在当前list中，则其将被移动⾄队尾；在k-桶容量已满的情况下，添加新节点的情况有点特殊，它将⾸先检查最早访问的队⾸节点是否仍 有响应，如果有，则队⾸节点被移⾄队尾，新访问节点信息被抛弃，如果没有，这才抛弃队⾸节点，将最新访问的节点信息插⼊队尾。可以看出，尽可能重⽤已有节 点信息、并且按时间排序是k-桶节点更新⽅式的主要特点。从启发性的⾓度⽽⾔，这种⽅式具有⼀定的依据：在线时间长⼀点的节点更值得我们信任，因为它已经 在线了若⼲⼩时，因此，它在下⼀个⼩时以内保持在线的可能性将⽐我们最新访问的节点更⼤，或者更直观点，我这⾥再给出⼀个更加⼈性化的解释：MP3⽂件交 换本⾝是⼀种触犯版权法律的⾏为，某⼀个节点反正已经犯了若⼲个⼩时的法了，因此，它将⽐其他新加⼊的节点更不在乎再多犯⼀个⼩时的罪……-_-b由上可见，设计采⽤这种多k-bucket数据结构的初衷主要有⼆：a. 维护最近-最新见到的节点信息更新；b. 实现快速的节点信息筛选操作，也就是说，只要知道某个需要查找的特定⽬标节点N的ID，我们便可以从当前节点的k-buckets结构中迅速地查出距离N 最近的若⼲已知节点。7. 在Kad⽹络中如何寻找某特定的节点?已知某节点ID，查找获得当前Kad⽹络中与之距离最短的k个节点所对应的⽹络信息(Node ID，IP地址，UDP端⼝)的过程，即为Kad⽹络中的⼀次节点查询过程(Node Lookup)。注意，Kad之所以没有把节点查询过程严格地定义成为仅仅只查询单个⽬标节点的过程，这主要是因为Kad⽹络并没有对节点的上线时间作出 任何前提假设，因此在多数情况下我们并不能肯定需要查找的⽬标节点⼀定在线或存在。整个节点查询过程⾮常直接，其⽅式类似于DNS的迭代查询：a. 由查询发起者从⾃⼰的k-桶中筛选出若⼲距离⽬标ID最近的节点，并向这些节点同时发送异步查询请求；b .被查询节点收到请求之后，将从⾃⼰的k-桶中找出⾃⼰所知道的距离查询⽬标ID最近的若⼲个节点，并返回给发起者；c. 发起者在收到这些返回信息之后，再次从⾃⼰⽬前所有已知的距离⽬标较近的节点中挑选出若⼲没有请求过的，并重复步骤1；d. 上述步骤不断重复，直⾄⽆法获得⽐查询者当前已知的k个节点更接近⽬标的活动节点为⽌。e. 在查询过程中，没有及时响应的节点将⽴即被排除；查询者必须保证最终获得的k个最近节点都是活动的。简单总结⼀下上述过程，实际上它跟我们⽇常⽣活中去找某⼀个⼈打听某件事是⾮常相似的，⽐⽅说你是个Agent Smith，想找⼩李(key)问问他的⼿机号码(value)，但你事先并不认识他，你⾸先肯定会去找你所认识的和⼩李在同⼀个公司⼯作的⼈，⽐⽅说⼩ 赵，然后⼩赵⼜会告诉你去找与和⼩李在同⼀部门的⼩刘，然后⼩刘⼜会进⼀步告诉你去找和⼩李在同⼀个项⽬组的⼩张，最后，你找到了⼩张，哟，正好⼩李出差 去了(节点下线了)，但⼩张恰好知道⼩李的号码，这样你总算找到了所需的信息。在节点查找的过程中，“节点距离的远近”实际上与上⾯例⼦中“⼈际关系的密 切程度”所代表的含义是⼀样的。最后说说上述查询过程的局限性：Kad⽹络并不适合应⽤于模糊搜索，如通配符⽀持、部分查找等场合，但对于⽂件共享场合来说，基于关键词的精确查找 功能已经基本⾜够了(值得注意的是，实际上我们只要对上述查找过程稍加改进，并可以令其⽀持基于关键词匹配的布尔条件查询，但仍不够优化)。这个问题反映 到eMule的应⽤层⾯来，它直接说明了⽂件共享时其命名的重要性所在，即，⽂件名中的关键词定义得越明显，则该⽂件越容易被找到，从⽽越有利于其在 P2P⽹络中的传播；⽽另⼀⽅⾯，在eMule中，每⼀个共享⽂件均可以拥有⾃⼰的相关注释，⽽Comment的重要性还没有被⼤家认识到：实际上，这个 ⽂件注释中的关键词也可以直接被利⽤来替代⽂件名关键词，从⽽指导和⽅便⽤户搜索，尤其是当⽂件名本⾝并没有体现出关键词的时候。8. 在Kad⽹络中如何存储和搜索某特定的条⽬?从本质上⽽⾔，存储、搜索某特定条⽬的问题实际上就是节点查找的问题。当需要在Kad⽹络中存储⼀个条⽬时，可以⾸先通过节点查找算法找到距离 key最近的k个节点，然后再通知它们保存条⽬即可。⽽搜索条⽬的过程则与节点查询过程也是基本类似，由搜索发起⽅以迭代⽅式不断查询距离key较近的节 点，⼀旦查询路径中的任⼀节点返回了所需查找的value，整个搜索的过程就结束。为提⾼效率，当搜索成功之后，发起⽅可以选择将搜索到的条⽬存储到查询 路径的多个节点中，作为⽅便后继查询的cache；条⽬cache的超时时间与节点-key之间的距离呈指数反⽐关系。9. ⼀个新节点如何⾸次加⼊Kad⽹络?当⼀个新节点⾸次试图加⼊Kad⽹络时，它必须做三件事，其⼀，不管通过何种途径，获知⼀个已经加⼊Kad⽹络的节点信息(我们可以称之为节点 I)，并将其加⼊⾃⼰的k-buckets；其⼆，向该节点发起⼀次针对⾃⼰ID的节点查询请求，从⽽通过节点I获取⼀系列与⾃⼰距离邻近的其他节点的信 息；最后，刷新所有的k-bucket，保证⾃⼰所获得的节点信息全部都是新鲜的。