BT源代码分析.doc

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊3,Encoder:一种 Handler类(在分析 tracker 服务器.随机的第一个片断 最少优先的一个例外是在下载. Client在收到tracker的响应后,就能获取其它下载者的信息.啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊BT源代码分析啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊BT源代码分析 概述：相对于 tracker 服务器来说，BT客户端要复杂的多，Bram Cohen 花了一年 full time 的时间来完成 BT，我估计其中大部分时间是用在 BT 客户端的实现和调试上了。由于 BT 客户端涉及的代码比较多，我不能再象分析 tracker 服务器那样，走上来就深入到细节之中去，那样的话，我写的晕晕糊糊，大家看起来也不知所云。所以第一篇文章先来谈谈客户端的功能、相关协议，以及客户端的总体架构和相关的类的层次结构。这样，从整体上把握之后，大家在自己分析代码的过程中，就能做到胸有成竹。客户端的功能：不看代码，只根据 BT 的相关原理，大致可以推测，客户端需要完成以下功能：1、解析 torrent 文件，获取要下载的文件的详细信息，并在磁盘上创建空文件。2、与 tracker服务器 建立连接，并交互消息。 3、根据从 tracker 得到的信息，跟其它 peers 建立连接，并下载需要的文件片断4、监听某端口，等待其它peers 的连接，并提供文件片断的上传。相关协议：对客户端来说，它需要处理两种协议：1、与 tracker 服务器交互的 track HTTP协议。2、与其它 peers 交互的 BT 对等协议。总体架构：从总体上来看，BT客户端实际是以一个服务器的形式在运行。这一点似乎有些难以理解，但确实是这样。为什么是一个服务器了？客户端的主要功能是下载文件，但作为一种P2P软件，同时它必须提供上传服务，也就是它必须守候在某一个端口上，等待其它peers 的连接请求。从这一点上来说，它必须以一个服务器的形式运行。我们在后面实际分析代码的时候，可以看到，客户端复用了 RawServer 类用来实现网络服务器。客户端的代码，是从 download.py 开始的，首先完成功能1，之后就进入服务器循环，在每一次循环过程中，完成功能 2、3、4。其中，Rerequester 类负责完成功能2，它通过 RawServer:add_task()，向 RawServer 添加自己的任务函数，这个任务函数，每隔一段时间与 tracker 服务器进行通信。而Encoder、Connecter 等多个类组合在一起，完成功能3和4。类层次结构：BT 客户端涉及的类比较多，我首先大致描述一下这些类的功能，然后给出它们的一个层次结构。1、RawServer：负责实现网络服务器2、Rerequester：负责和 tracker 通信。它调用 RawServer:add_task() ，向 RawServer 添加自己的任务函数 Rerequester:c()。3、Encoder：一种 Handler类（在分析 tracker 服务器时候提到），负责处理与其它peers建立连接和以及对读取的数据按照BT对等协议进行分析。Encoder 类在Encrypter.py中，该文件中，还有一个 Connection 类，而在 Connecter.py 文件中，也有一个 Connection 类，这两个同名的 Connection 类有些蹊跷，为了区分，我把它们重新命名为 E-Connection 和 C-Connection。3.1、E-Connection：负责 TCP 层次上的连接工作这两个 Connection 是有区别的，这是因为BT对等协议需要在两个层次上建立连接。首先是 TCP 层次上的连接，也就是经过 TCP 的三次握手之后，建立连接，这个连接由 E-Connection 来管理。在 Encoder: external_connection_made() 函数中可以看到，一旦有外部连接到来，则创建一个 E-Connection 类。3.2、C-Connection：管理对等协议层次上的连接。在 TCP 连接之上，是 BT对等协议的连接，它需要经过BT对等协议的两次“握手”，握手的细节大家去看BT对等协议。过程是这样的：为了便于述说，我们假设一个BT客户端为 A，另一个客户端为 X。如果是X主动向A发起连接，那么在TCP连接建立之后，A立刻利用这个连接向X发送BT对等协议的“握手”消息。同样，X在连接一旦建立之后，向 A发送BT对等协议的“握手”消息。A一旦接收到X的“握手”消息，那么它就认为“握手”成功，建立了BT对等协议层次上的连接。我把它叫做“对等连接”。A 发送了一个消息，同时接收了一个消息，所以这个握手过程是两次“握手”。同样，对X 来说，因为连接是它主动发起的，所以它在发送完“握手”消息之后，就等待A的“握手”消息，如果收到，那么它也认为“对等连接”建立了。一旦“对等连接”建立之后，双方就可以通过这个连接传递消息了。这样，原来我所疑惑的一个问题也就有了答案。就是：如果 X 需要从 A 这里下载数据，那么它会同 A 建立一个连接。假如 A 又希望从 X 那里下载数据，它需不需要重新向 X 发起另外一个连接了？答案显然是不用，它会利用已有的一条连接。也就是说，不管是X主动向A发起的连接，还是 A 主动向 X发起的连接，一旦建立之后，它们的效果是一样的。这个同我们平时做 C/S结构的网络开发是有区别的。我们可以看到在 E-Connection的初始化函数中，会主动连接的另一方发送“握手”消息，在 E-Connection:data_came_in() 中，会首先对对方的“握手”消息进行处理。这正是我上面所描述的情形。在 E-Connection:read_peer_id() 中，是对“握手”消息的最后一项 peer id进行处理，一旦正确无误，那么就认为“对等连接”完成，self.encoder.connecter.connection_made(self)在 Connecter:connection_made() 函数中，就创建了管理“对等连接”的 C-Connectinon类。所以，更高一层的“对等连接”是由 C-Connection 来管理的。3.3、Connecter：连接器，管理下载、上传、阻塞、片断选择、读写磁盘等等。下载和上传不是孤立的，它们之间相互影响。下载需要有片断选择算法，上传的时候要考虑阻塞，片断下载之后，要写到磁盘上。上传的时候，也需要从磁盘读取。这些任务，是由 Connecter 来统一调度的。类层次结构，我用缩进来表示一种包含关系。Encoder: E-Connection C-Connection Upload SingleDownloader Connecter Choker：负责阻塞的管理 Downloader： SingleDownloader Picker：片断选择策略 StorageWrapper：i Last edited by 太极 on 2005-10-26 at 07:27 /i太极 2005-10-25 23:18Storage 类由于 Storage 类比较简单，我直接在源码基础上进行注释。掌握Storage，为进一步分析 StorageWrapper 类打下基础。几点说明：1、Storage 类封装了对磁盘文件的读和写的操作。2、BT既支持单个文件的下载，也支持多个文件，包括可以有子目录。但是它并不是以文件为单位进行下载和上传的，而是以“文件片断”为单位。这可以在BT协议规范以及另一篇讲BT技术的文章中看到。所以，对于多个文件的情况，它也是当作一个拼接起来的“大文件”来处理的。例如，有文件 aaa和bbb，大小分别是 400和1000，那么它看作一个大小为 1400 的大文件，并以此来进行片断划分。3、文件在下载过程中，同时提供上传，所以是以读写方式打开的，wb+和rb+都指的读写方式。在下载完毕之后，改为只读方式。4、由于下载可能中断，所以在 Storage 初始化的时候，磁盘上可能已经存在文件的部分数据，必须检查一下文件的大小。为了便于描述，我们把完整文件的大小称为“实际长度”，把文件当前的大小成为“当前长度”。class Storage:# files 是一个二元组的列表（list），二元组包含了文件名称和长度，例如：(“aaa”, 100), (“bbb”, 200)def _init_(self, files, open, exists, getsize): self.ranges = # 注意，这里是 0l，后面的l表示类型是长整形，而不是 01。 total = 0l so_far = 0l for file, length in files: if length != 0: # ranges 是一个三元组列表，三元组的格式是： 在“整个”文件的起始位置、结束位置、文件名。BT在处理多个文件的时候，是把它们看作一个拼接起来的大文件。 self.ranges.append(total, total + length, file) total += length # so_far 是实际存在的文件的总长度，好像没有起作用 if exists(file): l = getsize(file) if l length: l = lengthso_far += l# 如果文件长度为0， 则创建一个空文件 elif not exists(file): open(file, wb).close() # begins 是一个列表，用来保存每个文件的起始位置 self.begins = i0 for i in self.ranges self.total_length = total self.handles = self.whandles = self.tops = 太极 2005-10-25 23:19StorageWrapper 类StorageWrapper 的作用：把文件片断进一步切割为子片断，并且为这些子片断发送 request消息。在获得子片断后，将数据写入磁盘。请结合 Storage 类的分析来看。几点说明：1、为了获取传输性能，BT把文件片断切割为多个子片断。2、BT为获取一个子片断，需要向拥有该子片断的peer发送request消息（关于 request消息，参见BT协议规范）。3、 例如一个256k大小的片断，索引号是10，被划分为16个16k大小的子片断。那么需要为这16个子片断分别产生一个 request 消息。这些request消息在发出之前，以list的形式保存在 inactive_requests 这个list中。例如对这个片断，就保存在inactive_requests下标为 10（片断的索引号）的地方，值是如下的 list：(0,16k),(16k, 16k), (32k, 16k), (48k, 16k), (64k, 16k), (80k, 16k), (96k, 16k), (112k, 16k), (128k, 16k), (144k, 16k), (160k, 16k), (176k, 16k), (192k, 16k), (208k, 16k), (224k, 16k), (240k, 16k)。这个处理过程在 _make_inactive() 函数中。因为这些request还没有发送出去，所以叫做 inactive request（未激活的请求）。如果一个 request 发送出去了，那么叫做 active request。为每个片断已经发送出去的request个数记录在 numactive 中。如果收到一个子片断，那么 active request 个数就要减1。amount_inactive 记录了尚没有发出request的子片断总的大小。4、 每当获得一个子片段，都要写入磁盘。如果子片断所属的片断在磁盘上还没有分配空间，那么首先需要为整个片断分配空间。如何为片断分配空间？这正是 StorageWrapper 类中最难理解的一部分代码。这个“空间分配算法”说起来很简单，但是在没有任何注释的情况下去看代码，耗费了我好几天的时间。具体的算法分析，请看 _piece_came_in() 的注释。class StorageWrapper:def _init_(self, storage, request_size, hashes, piece_size, finished, failed, statusfunc = dummy_status, flag = Event(), check_hashes = True,data_flunked = dummy_data_flunked): self.storage = storage # Storage 对象 self.request_size = request_size #子片断大小 self.hashes = hashes # 文件片断摘要信息 self.piece_size = piece_size# 片断大小 self.data_flunked = data_flunked # 一个函数，用来检查片断的完整性 self.total_length = storage.get_total_length() # 文件总大小 self.amount_left = self.total_length # 未下载完的文件大小 # 文件总大小的有效性检查 # 因为最后一个片断长度可能小于 piece_size if self.total_length piece_size * len(hashes): raise ValueError, bad data from tracker - total too big # 两个事件，分布在下载完成和下载失败的时候设置 self.finished = finished self.failed = failed 这几个变量的作用在前面已经介绍过了。 self.numactive = 0 * len(hashes) inactive_requestinactive_requests 的值全部被初始化为1，这表示每个片断都需要发送 request。后面在对磁盘文件检查之后，那些已经获得的片断，在 inactive_requests中对应的是 None，表示不需要再为这些片断发送 request了。 self.inactive_requests = 1 * len(hashes) self.amount_inactive = self.total_length# 是否进入 EndGame 模式？关于 endgame 模式，在Incentives Build Robustness in BitTorrent 的“片断选择算法”中有介绍。后面可以看到，在为最后一个“子片断”产生请求后，进入 endgame 模式。 self.endgame = False self.have = Bitfield(len(hashes) # 该片是否检查了完整性 self.waschecked = check_hashes * len(hashes) 这两个变量用于“空间分配算法” self.places = self.holes = if len(hashes) = 0: finished() return targets = total = len(hashes)# 检查每一个片断， for i in xrange(len(hashes):# 如果磁盘上，还没有完全为这个片断分配空间，那么这个片断需要被下载，在 targets 字典中添加一项（如果已经存在，就不用添加了），它的关键字（key）是该片断的摘要值，它的值（value）是一个列表， 这个片断的索引号被添加到这个列表中。这里一度让我非常迷惑，因为一直以为不同的文件片断肯定具有不同的摘要值。后来才想明白了，那就是：两个不同的文件片断，可能拥有相同的摘要值。不是么？只要这两个片断的内容是一样的。这一点，对后面的分析非常重要。if not self._waspre(i): targets.setdefault(hashesi, ).append(i) total -= 1 numchecked = 0.0 if total and check_hashes: statusfunc(activity : checking existing file, fractionDone : 0)# 这是一个内嵌在函数中的函数。在 c+ 中，可以有内部类，不过好像没有内部函数的说法。这个函数只能在 _init_() 内部使用。这个函数在一个片段被确认获得后调用# piece: 片断的索引号# pos: 这个片断在磁盘上存储的位置例如，片断5可能存储在片断2的位置上。请参看后面的“空间分配算法” def markgot(piece, pos, self = self, check_hashes = check_hashes): self.placespiece = pos self.havepiece = True self.amount_left -= self._piecelen(piece)self.amount_inactive -= self._piecelen(piece)不用再为这个片断发送 request消息了 self.inactive_requestspiece = None self.wascheckedpiece = check_hashes lastlen = self._piecelen(len(hashes) - 1) # 最后一个片断的长度# 对每一个片断 for i in xrange(len(hashes):#如果磁盘上，还没有完全为这个片断分配空间，那么在 holes 中添加该片断的索引号。if not self._waspre(i): self.holes.append(i) # 否则，也就是空间已经分配。但是还是不能保证这个片断已经完全获得了，正如分析 Storage 时提到的那样，可能存在“空洞” # 如果不需要进行有效性检查，那么简单调用 markgot() 表示已经获得了该片断。这显然是一种不负责任的做法。 elif not check_hashes: markgot(i, i)# 如果需要进行有效性检查else:sha是python内置的模块，它封装了 SHA-1摘要算法。SHA-1摘要算法对一段任意长的数据进行计算，得出一个160bit （也就是20个字节）长的消息摘要。在 torrent 文件中，保存了每个片断的消息摘要。接收方在收到一个文件片断之后，再计算一次消息摘要，然后跟 torrent 文件中对应的值进行比较，如果结果不一致，那么说明数据在传输过程中发生了变化，这样的数据应该被丢弃。这里，首先，根据片断i的起始位置开始，lastlen长的一段数据构造一个 sha 对象。 sh = sha(self.storage.read(piece_size * i, lastlen)计算这段数据的消息摘要 sp = sh.digest()然后，更新 sh 这个 sha 对象，注意，是根据片断 i 剩下的数据来更新的。关于 sha:update() 的功能，请看 python的帮助。如果有两段数据 a 和 b，那么sh = sha(a)sh.update(b)，等效于 sh = sha(a+b)所以，下面这个表达式等于sh.update(self.storage.read(piece_size*i, self._piecelen(i) sh.update(self.storage.read(piece_size * i + lastlen, self._piecelen(i) - lastlen)所以，这次计算出来的就是片断i 的摘要（原来的困惑：为什么不直接计算 i 的摘要，要这么绕一下了？后来分析清楚“空间分配算法”之后，这后面一段代码也就没有什么问题了。） s = sh.digest()如果计算出来的摘要和 hashesi 一致（后者是从 torrent 文件中获得的），那么，这个片断有效且已经存在于磁盘上。 if s = hashesi:markgot(i, i) elif targets.get(s) and self._piecelen(i) = self._piecelen(targetss-1): markgot(targetss.pop(), i) elif not self.havelen(hashes) - 1 and sp = hashes-1 and (i = len(hashes) - 1 or not self._waspre(len(hashes) - 1):markgot(len(hashes) - 1, i) else: self.placesi = i if flag.isSet(): return