emule源码解析

emule源码解析 2009-04-30 10:01 eMule 源代码解析 ( 五） emule 中的Kademlia 代码总体描述当emule 中开始使用 Kademlia 网络后，便不再会有中心服务器失效这样的问题了，因为在这个网络中，没有中心服务器，或者说，所有的用户都是服务器，所有的用户也是客户端，从而完完全全得实现了 P2P 。接下来讲针对 emule 中的 Kademlia 网络进行分析，会有一节进行原理方面的分析。另外的几节将会根据 emule 中实现 Kademlia 所使用的不同的类分别进行讲述。其中...

2009-04-30 10:01 eMule 源代码解析 ( 五） emule 中的Kademlia 代码总体描述当emule 中开始使用 Kademlia 网络后，便不再会有中心服务器失效这样的问题了，因为在这个网络中，没有中心服务器，或者说，所有的用户都是服务器，所有的用户也是客户端，从而完完全全得实现了 P2P 。接下来讲针对 emule 中的 Kademlia 网络进行分析，会有一节进行原理方面的分析。另外的几节将会根据 emule 中实现 Kademlia 所使用的不同的类分别进行讲述。其中： CKademlia 是整个 Kademlia 网络的主控类，可以直接开始或者停止 Kademlia 网，并且含有 Process 方法来处理日常事务。 CPrefs 负责处理自身的 Kademlia 相关信息，如自身的 ID等。 CRoutingZone ，CRoutingBin 和CContact 三个类组成了每个节点所了解的联系信息以及由这些联系信息所组成的数据结构。 CKademliaUDPListener 负责处理网络信息。 CIndexed 负责处理本地存储的索引信息。 CSearch ，CSearchManager 负责处理和搜索有关的操作，其中前者表示的是一个单一的搜索任务，后者负责对所有搜索任务进行处理。 CUInt128 负责处理一个 128 位的长整数，并且内置其各种运算。前面已经提到过。 emule 中的Kademlia 的基本原理 Kademlia 是一种结构化的覆盖网络 (Structured Overlay Network) ，所谓的覆盖网络，就是一种在物理的 Internet 上面再次构建的虚拟网络，所有参与的节点都知道一部分其它节点的 IP 地址，这些节点称为它的邻居，如果需要查找什么东西，它先在本地寻找，如果找不到，就把这个查询转发到它的邻居处，希望能够有可能查找到相应的结果。覆盖网络里面分成了结构化和非结构化的两种情况，它们的区别在于每个节点知道哪些其它节点的信息是否有特定的规律。在非结构化的覆盖网中，每个节点的邻居状况没有特定的规律。因此在非结构化网络中，如果要进行查询，会采取一种叫做泛洪 (flooding) 的方法，每个节点如果在本地没有查找到想要的结果，会把查找请求转发到它的邻居中，然后再通过邻居的邻居这种方式来进行一步步的查找。但是这种方法如果处理不好，会造成整个网络的消息负载过大。已经有不少文章对于优化非结构化覆盖网络中的查询进行了很深入的探讨。对于结构化的覆盖网络，它的特点是每个节点它会选择和哪些节点做邻居是有一定的规律的，从而在进行搜索的时候，节点把搜索请求进行转发的时候它能够通过一定的规律进行选择把请求转发到哪些邻居节点上。这样同时也能减少搜索代价。结构化的覆盖网络通常要求每一个节点随机生成一个 ID，用以判断各个节点之间的关系。这个 ID和它所在的物理网络必须是没有关系的。对于 Kademlia 网络来说，这个 ID是一个 128 位的数值，所有的节点都用这个 ID来衡量自己与其它节点的逻辑距离。而逻辑距离的计算方法就是将两个节点进行异或 (XOR) 操作。在 Kademlia 网络的形成过程中，每个节点选择邻居的原则是离自己逻辑距离越近的节点越有可能被加入到自己的邻居节点列表中，具体来说就是在每次新得到一个节点的信息的时候，是否把它加入到自己的邻居节点列表是根据距离的远近来处理的。后面分析具体程序的代码时会有说明。结构化的网络的好处就是如果我们要寻找一个距离某个 ID逻辑距离足够近的节点，我们可以保证在 O(logn) 级别的跳数找到。只要先寻找自己已知的离目标 ID逻辑距离足够断的节点，然后再问它知不知道更近的，然后就这样下去。因此在搜索的时候也是这样，当需要发布资源的时候，把文件进行 hash ，这样就能够计算出一个 128 位的 ID ，或者把关键字进行 hash 。然后寻找到离这个结果逻辑距离最近的节点，把文件或者关键字的信息发送给它，让它存起来。当有人要搜索同样的东西的时候，由于它用的是同一个hash 算法，因此能够计算出对应的 ID，并且去搜索那些和这个 ID逻辑距离相近的节点，因为它知道，如果网络中真有这些资源的话，这些节点是最有可能知道这些信息的。由此我们可以看出，结构化的网络的资源查找效率是很高的，但是它和非结构化的覆盖网络比起来，缺点是不能进行复杂查询，即只能通过简单的关键字或者文件的 hash 值进行查找。非结构化的网络的查找本身就是随意转发的，每个收到的查询请求的节点都对本地的资源掌握的很清楚，因此自然可以支持复杂查询，但是显然非结构化的网络支持的复杂查询不太可能动员所有的节点都来做这一动作。目前还没有方法能够把两种覆盖网络的优点结合起来，我也非常想知道这样的一种方法。 emule 中的Kademlia 的基础设施类 Kademlia 的主控类是 CKademlia ，它负责启动和关闭整个 Kademlia 网的相关代码。在它的 Process 函数中，会处理和 Kademlia 网相关的事务，例如隔一段时间检查某个区间的节点数是否过少，如果是则寻找一些新的节点。另外经常对自己的邻居进行检查等，这些都是属于需要进行日常安排的工作。所有搜索任务的日常处理也需要它来调度。它还作为 Kademlia 网的代表，向 emule 其它部分的代码返回 Kademlia 网的一些统计信息。另一个基础设施类是 CPrefs ，它和 emule 普通代码中的 CPreferences 作用类似，但是 CPrefs 只保留和 Kademlia 网相关的，需要长期保存的本地信息。具体到这个版本来说，主要就是本地的 ID。还有一个很重要的基础设施就是 CUInt128 ，实现对 128 位的 ID的各种处理，前面的部分已经提到。 emule 中的Kademlia 的联系人列表管理 CRoutingZone ，CRoutingBin 和CContact 三个类组成了联系人列表数据结构。它要达到我们搜索的要求，即搜索到目标的时间要能够接受，而且所占用的空间也要能够接受。首先 CContact 类包含的是一个联系人的信息，主要包括对方的 IP地址， ID，TCP 端口， UDP 端口， kad 版本号和其健康程度 (m_b yType) 。其中健康程度有 0-4 五个等级。刚刚加入的联系人，也就是健康状况未知的，这个数值设置为 3。系统会经常通过与各个联系人进行联系的方式对其进行健康状况检查，经常能够联系上的联系人，这个数值会慢慢减少到 0。而很就没有联系的，这个数值会慢慢增加，如果增加到 4后再过一段时间未能成功联系上的，则将会被从联系人列表中删除。 CRoutingBin 类包含一个 CContact 的列表（ typedef std::list ContactList; ）。这里要注意的是要访问联系人的信息必须通过某个 CRoutingBin ，CRoutingZone 内部是不直接包含联系人信息的。可以把新的联系人信息往一个特定的 CRoutingBin 中加，当然也可以进行联系人查找。它也提供方法能够寻找出离某个 ID距离最近的联系人，并给出这样的一个列表。这是相当重要的。最后，一个 CRoutingBin 类中能够包含的 CContact 的数量也是有限制的。（在Kademila 名字空间中，定义了 #define K 10 ） CRoutingZone 类处于联系人数据结构的最上层，直接为 Kademlia 网提供操作接口。该类的结构为一个二叉树，内含两个 CRoutin gZone 指向它的左子树和右子树，另外也包含一个 CRoutingBin 类型的指针。但是只有在当前的 CRoutingZone 类为整个二叉树的叶节点时，这个指向 CRoutingBin 类型的指针才有意义。（ CRoutingZone *m_pSubZones[2]; CRoutingZone *m_pSuperZone; ）这个二叉树的特点是，每个节点以下的所有联系人的 ID都包含一个共同前缀，节点的层数越深，这个共同前缀越长。例如，根节点的左子树的所有的节点的 ID一定有一个前缀 "0"，而右子树的所有节点一定有前缀 "1"。同样，根节点的左子树的右子树下的所有节点的 ID一定有前缀 "01" ，等等，依此类推。我们设想一下节点不断得往这个二叉树添加的过程。刚开始只有一个根节点，它也就是叶节点，这时它内部的 CRoutingBin 是有意义的，当联系人信息不断得被添加进去以后，这个 CRoutingBin 的容量满了，这时要进行的就是一个分裂的操作。这时，会添加两个左子节点和右子节点，然后把自身的 CRoutingBin 中的联系人信息按照它们的前缀特点分别复制往左节点和右节点，最后把自身的 CRoutingBin 废除掉，这样这个分裂过程就完了。当分裂完成后，就会再次试图添加该联系人信息，此时会试图按照它的 ID，把它添加到对应的子树中。但是并不是所有的这种情况节点都会发生分裂，因为如果允许任意分裂的话，本地所需存储的节点信息数量就会急剧上升。这里，自身 ID的作用就体现了。只有当自身 ID和当前准备分裂的节点有共同前缀时，这个节点才会分裂，而如果判断到一个节点不能分裂，而它的 CRoutingBin 又满掉了，那么就会拒绝添加联系人信息。我们可以看出，在以上政策的进行下，离自身 ID逻辑距离越近 (也就是共同前缀越长 )的联系人信息越有可能被加入，因为它所对应的节点越有可能因为分裂而获得更多的子节点，也就对应了更多的容量。这样，在 Kademlia 网中，每一个参与者知道的其它参与者信息中，离自己逻辑距离越近的参与者比例越高。由于在搜索的时候也只需要不断得寻找更近的 ID，而且每一步都一定会有进展，所以寻找到目标 ID所需要的时间上的代价是 O(logn) ，从这个二叉树的结构来看，我们也可以看到，由于只有部分节点会分裂，所以实质上存储所需要的空间代价也是 O(logn) 。实际上 CRoutingZone 在实现时和理论上的 Kademlia 有一些区别，如从根节点开始，有一个最低分裂层数，也就是说，如果层数过低的话，是永远允许分裂的，这样它知道的其它地区的联系人信息就能够稍微多一些。 emule 中的Kademlia 网络消息处理 CKademliaUDPListener 负责处理所有和 Kademlia 网相关的消息。前面已经对 emule 的通信协议的基本情况做了一个大概的描述，我们就可以知道， CKademliaUDPListener 处理的消息一定是只和 Kademlia 网相关的，分拣工作已经在 emule 的普通 UDP 客户端处理代码那里处理好了。具体的消息格式前面也有一些介绍，下面会就一些具体的消息分类做说明。首先是健康检查方面的消息，这样的消息就是一般的 ping-pong 机制。对应的消息有 KADEMLIA_HELLO_REQ 和KADEMLIA_HE LLO_RES 。当对本地联系人信息列表进行检查时，会对它们发出 KADEMLIA_HELLO_REQ 消息，然后处理收到的 KADEMLIA_H ELLO_RES 消息。最常用的消息是节点搜索消息，在 Kademlia 网络中，进行节点搜索是日常应用所需要传输的主要消息，它的实现方式是迭代式的搜索。这种方式就是说当开始搜索某个 ID时，在本地联系人信息列表中查找到距离最近的联系人，然后向它们发出搜索请求，这样通常都能够得到一些距离更近的联系人信息，然后再向它们发送搜索请求，通过不断得进行这样的搜索查询，就能够得到距离目标 ID最近的那些联系人信息。这里对应的消息代码是 KADEMLIA_REQ 和KADEMLIA_RES 。（这两个消息代码，跟来更新路由表的）接下来就是对内容进行发布或者搜索。这一点结合后面的 CIndexed 类的分析可以知道得更加清楚。 emule 中存储在 Kademlia 网中的信息主要有三类：文件源，关键字信息和文件的评论。文件源对应的是每一个具体的文件，每个文件都用它的内容的 hash 值作为该文件的唯一标示，一条文件源信息就是一条关于某人拥有某个特定的文件的这样一个事实。一条关键字信息则是该关键字对应了某个文件这样一个事实。很显然，一个关键字可能会对应多个文件，而一个特定的文件的文件源也很有可能不止一个。但是它们的索引都以固定的 hash 算法作为依据，这样使得搜索和发布都变得很简单。我们来看发布过程。每个 emule 客户端把自己的共享文件的底细已经摸清楚了，在传统的有中心索引服务器的场景里，它把自己的所有文件的信息都上传到中心索引服务器里。但是在 Kademlia 网里，它就需要分散传播了，它首先做的事情是把文件名进行切词，即从文件名中分解出一个一个的关键词出来，它切词的方法非常简单，就是在文件名中寻找那些有分割符含义的字符，如下划线等，然后把文件名切开。计算出这些关键字的 hash 值后，它把这些关键字信息发布到对应的联系人那里。并且把文件信息也发布到和文件内容 hash 值接近的联系人那里。对应的消息是 KADEMLIA_PUBLISH_REQ 和KADEMLIA_PUBLISH_RES （这两个消息代码，用来发布共享文件的）。另外 emule 允许用户对某个文件发表评论，评论的信息单独保存，但是原理也是一样的。当用户使用 Kademlia 网络来进行搜索并且下载文件的时候，首先是对一个关键词进行搜索，由于使用的是同样的 hash 算法，这样它只要找到 ID值和计算出来的 hash 值结果相近的联系人信息后，它就可以直接向它们发送搜索特定关键词的请求了。如果得到了返回信息，那么搜索者就知道了这个关键词对应了多少文件，然后把这些文件的信息都列出来。当用户决定下载某个文件的时候，针对这一特定文件的搜索过程就开始了，这一次如果搜索成功，那么返回的就是这个文件的文件源信息。这样 emule 接下来就只需要按照这些信息去连接相应的地址，并且使用传统的 emule 协议去和它们协商下载文件了。这里对应的消息是 KADEMLIA_S EARCH_REQ 和 KADEMLIA_SEARCH_RES （这两个消息代码，用来搜索文件的）。实际的实现中有 Kademlia2 这种协议，它的原理是一样的，只有协议代码和具体的消息格式不一样，例如 KADEMLIA_REQ 和 KAD EMLIA_RES 对应了 KADEMLIA2_HELLO_REQ 和KADEMLIA2_HELLO_RES ，但是后者在具体的消息中包含了比前者丰富一些的信息。在实现的时候 0.47c 更加倾向于使用 Kademlia2 ，而 0.47a 更加倾向于使用 Kademlia 。当然，它们两种协议都能够处理。另外， 0.47c 增加了一个对于已发出的请求的追踪的特性，就是一个包含 TrackPackets_Struct 类型的列表，这里面详细纪录了什么时间曾经对哪个 IP 发出过那种 opcode 对应的请求。为什么要这样呢？这是为了防止针对 DHT 的一种路由污染攻击，因为在搜索联系人的时候，如果搜索到了一些联系人信息，也会试图把它先加入到本地的联系人信息列表中。这样如果有人想恶意攻击的话，它只要不断得往它想攻击的 emule 客户端发送 KADEMLIA_RES ，并且在消息的内容中包含大量的虚假联系人信息，就可以使对方的联系人信息列表中充满垃圾。这样，由于缺少正确有效的联系人信息，它的 Kademlia 网功能基本上就废了。而在0.47c 里面增加的这个特性，就会对那种还没有发出请求就收到回应的情况直接无视，从而避免被愚弄。 emule 中的Kademlia 的分布式索引管理 Kademlia 网络的最大的好处是把原来需要存储到中心索引服务器中的信息分散存储到各个客户端当中，如果要说得更加准确一点，那我们就可以说它把这些信息分散得存储到各个 emule 客户端的 CIndexed 类当中。我们可以具体开始看 CIndexed 的设计，看它是如何完成这一工作的。在这之前我们要稍微详细得说一下 emule 发布到 Kademlia 网络中的信息的各种类型。一个文件源信息是一个文件内容的 hash 值和拥有这个文件的客户端的 IP 地址，各种端口号以及其它信息之间的对应关系。而一个关键词信息则是该关键词和它对应的文件之间的关系。在关键词信息中，它对应的文件信息要更加详细，通常包括这个文件的文件名，文件大小，文件内容的 hash 值，如果是 MP3 或者其它媒体文件，还会包含包括作者，生产时间，文件长度 (这个长度是用时间来衡量的媒体文件的播放长度 )，流派等等 tag 信息。其中文件内容的 hash 值用来区分该关键词对应的不同文件。 CIndexed 中利用了一系列的 Map 来存储这些对应信息， CMap 是MFC 中实现标准 STL 中的map 的模板类， CIndexed 中包含了四个这样的类，分别用来存储文件源信息，关键词信息，文件评论信息以及负载信息。其中文件评论信息是不长久保存的，而其它的信息都会在退出的时候写到文件中，下次重新启动 emule 时再重新调入。另外负载信息不是等其它联系人来发布的，而是根据文件源信息和关键词信息的发布情况自行进行动态调整的。每一次收到发布信息时，对应的 ID的负载会增大，这一事实会在回应消息 (KADEMLIA_PUBLISH_RES) 中体现。 CIndexed 中的信息会经常进行检查，每隔三十分钟它会把自己存储的所有信息中太老的信息清除掉。其中文件源信息的保存时间为五小时，关键词信息为二十四小时，文件评论的信息保存时间也为二十四小时。因此文件的发布和关键词也要周期性得反复进行。其实这对于整个 Kademlia 网络的稳定性也是有好处的，因为每一次联系都会试图把对方添加到自己的联系人列表中，或者在联系人列表中标注上一次见到对方的时间。 CIndexed 为其它部分的代码提供了它们所需要的增加信息和搜索信息的接口，这样在从网络中获取到相关的搜索或者发布请求，并且 CKademliaUDPListener 完成消息的解释后，就可以交给 CIndexed 来进行处理了。 emule 中的Kademlia 搜索任务管理 CSearch 和CSearchManager 是完成具体搜索任务的。 CSearch 对应的是一个具体的搜索任务，它包括了一个搜索任务从发起到结束的全部过程，要注意的是搜索任务并不只是指搜索文件源或者关键词的任务，一次发布任务它也需要创建一个 CSearch 对象，并且让它开始执行。 CSearchManager 则掌握所有的搜索任务，它包含了一个包含所有 CSearch 指针对象的 CMap ，使用 CMap 的原因是因为所有的 CSearch 都一定对应一个 ID，那个 ID就是该 CSearch 所对应的目标，不管是要查找节点，还是要搜索或者发布信息，一定都要找到和目标 ID相近的联系人。因此 CSearchManager 可以使用 CMap 来表示所有的搜索任务。我们注意到 CSearch 在创建的时候就把自己加入到 CSearchManager 当中。另外 CSearch 在创建的时候需要说明它的类型，例如是只是为了搜索节点还是要搜索关键词信息或者文件源信息，当然也有可能是发布文件源信息或者关键词信息。我们介绍一下 CSea rch 的几个方法的作用就可以大概了解 CSearch 的工作过程。 Go是它的启动过程，它会开始第一次从本地的联系人列表中寻找候选的联系人，然后开始发动搜索。 SendFindValue 的功能就是向某个联系人发送一个搜索某 ID的联系人信息这样一个请求。 JumpSt art 则是在搜索进行到一定地步的时候，如得到了一些中间结果，开始进行下一步的行动，下一步的行动仍然可能是 SendFindValu e，也有可能认为搜索到的联系人离目标已经足够近了，于是就可以开始实质性的请求。 StorePacket 就是这样一个实质性的请求，例如在一个以发布文件源为任务的 CSearch 中， StorePacket 会向目标联系人发送 KADEMLIA2_PUBLISH_SOURCE_REQ( 如果不支持 Kademlia2 ，那么是 KADEMLIA_PUBLISH_REQ) 。最后， CSearch 能够处理各种搜索结果，然后向调用它的代码返回处理好的结果。 CSearchManager 直接和 Kademlia 网的其它部分代码接触，例如，如果 CKademliaUDPListener 搜索到了一些结果，它会把这些结果交给 CSearchManager ，然后 CSearchManager 再去寻找这个结果是属于那个搜索任务的，并且进行转交。另外 CSearchManag er对外提供创建各种新的搜索任务的接口，作用类似于设计模式中的 Factory ，其它部分的代码只需要说明需要开始一个什么样的搜索任务即可， CSearchManager 来完成相应的创建 CSearch 的任务。

                    本文档为【emule源码解析】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

emule源码解析

你可能还喜欢