前言
之前看到 lantern 这个十分火的翻墙工具，其利用了P2P的思想，就想了解一下P2P相关的协议。看了下最流行的BT协议官方文档，就产生了实现BT协议的想法，顺便根据协议实现了一个BT种子嗅探器。
也有人将BT种子嗅探器称为BT种子爬虫，个人觉得其行为特性和传统的web爬虫相差较大，反而和嗅探器很类似，因此暂且称之为BT种子嗅探器吧。
接下来将写一系列文章来介绍其原理和具体实现方式。这篇文章先提纲挈领，介绍其工作原理，以对全局有一个把握。后序的文章再介绍具体细节。
背景知识
在讲原理之前首先你得具备BitTorrent(简称BT)协议的一些基本知识，以便于理解接下来要讲的嗅探器。BT协议其实是一个协议簇，BEP-3 是其基本协议内容，其他的大部分都是围绕这个来进行扩展或补充。要想从BT网络中下载一个资源，必须具备以下部分：
种子文件（也就是我们常说的种子，后缀是 .torrent，本质上是一个由bencode编码的文本文件，其把资源分成很多虚拟块，并记录每个块的hash值，另外上面还记录着其他信息，比如文件大小、名字、Tracker服务器等）
BT客户端（需要有专门解析BT协议的程序，这样才能下载，比如迅雷，电驴）
Tracker服务器 （记录着peer和种子相关信息，起着中心调控的作用）
下载资源的时候，客户端首先根据bencode（bencode是BT协议中的编码方式）解码种子文件，得到Tracker服务器的地址和资源信息，通过和Tracker服务器沟通得到其他已经下载该资源的peers信息（其他已经拥有该资源的客户端或者发布该资源的人），然后再和这些peers沟通得到自己想要的部分，即互通有无。由于把文件分成很多块来同时从不同的地方下载，这也就是为什么BT通常下载快的原因。
DHT协议
通过上面我们知道，Tracker服务器在资源下载的过程中起着至关重要的作用，只有通过它我们才能得到其他peers的信息，才能够下载，但这同时也成了BT协议的一个弱点，如果Tracker服务器挂掉了或者被封被屏蔽，整个网络也就瘫痪了。由于一些资源都是有版权的，还有一些资源是限制级的，比如色情资源，Tracker服务器很容易被迫关闭或被墙。后来聪明的人类发明了另外一种协议，就是 Distributed hash table, 简称DHT，这个协议就是用来弥补这个弱点的。
BT协议簇中的DHT协议 是基于 Kademlia协议 建立的，其基本思想很好理解。DHT 由很多节点组成，每个节点保存一张表，表里边记录着自己的好友节点。当你向一个节点A查询另外一个节点B的信息的时候，A就会查询自己的好友表，如果里边包含B，那么A就返回B的信息，否则A就返回距离B距离最近的k个节点。然后你再向这k个节点再次查询B的信息，这样循环一直到查询到B的信息，查询到B的信息后你应该向之前所有查询过的节点发个通知，告诉他们，你有B的信息。
举个例子，比如我现在想要Angelababy的微信号（额…我要干嘛），我就从自己的微信好友中挑出k个最可能认识她的人，然后依次问他们有没有Angelababy的微信号，假如其中一个认识，那么他就会给我Angelababy的微信号，我也就不继续问其他人了。假如他不认识，他就给我推荐k个他微信好友中最有可能认识Angelababy的k个人，然后我再继续这k个人，就这样循环一直到我问到为止。OK，现在我已经得到了Angelababy的微信号，我就会告诉之前所有我问过的人，我有Angelababy的微信号。
当客户端下载资源的时候，他会利用上述方式查找peers信息，这样每个人都充当了Tracker的作用，也就解决了上面那个问题。
嗅探器原理
终于到核心部分了。
BT种子嗅探器就是利用了DHT协议得到peer信息后会向他之前查询过的节点发送通知这一点，这就是嗅探器的核心。
剩下的工作就是我们要让更多的节点发给我们通知。那么如何让更多的节点发给我们通知呢？
我们要不断的查询自己的好友节点表，并对返回回来的节点进行查询，这样才会有更多的人认识我们
别人向我们查询Target的时候，我们要伪装成Target的好友，返回结果里边包括自己，这样会有更多被查询、收到通知的机会
这就是BT种子嗅探器的原理，简单吧 :)
种子下载器
在BT网络中，通过上述原理收到信息并不是种子，而是发送消息者的ip和port、种子infohash（可以理解为种子的id）。我们如果想要得到种子的话，还需要做一番工作。这里涉及到另外一个非常重要的协议 BEP-09，BEP-09规定了如何通过种子infohash得到种子。
这里不铺开讲，仅说下大致过程。首先同我们收到的消息里边的 ip:port 建立TCP连接，然后发送握手消息，并告知对方自己支持BEP-09协议，然后向对方请求种子的信息，收到对方返回的种子信息后，依次或同时请求每一个块。最有所有块收集完后，对其进行拼接并通过sha1算法计算其infohash，如果和我们请求的infohash值相同则保存起来，否则丢掉。
应用
这样你可以得到非常多的种子信息，你可以对其进行索引建立自己的BT种子搜索引擎，建立自己的海盗湾。但你需要注意版权问题和色情资源问题。
BT种子嗅探器–DHT篇
背景知识
DHT全称 Distributed Hash Table，中文翻译过来就是分布式哈希表。它是一种去中心化的分布式系统，特点主要有自动去中心化，强大的容错能力，支持扩展。另外它规定了自己的架构，包括keyspace和overlay network（覆盖网络）两部分。但是他没有规定具体的算法细节，所以出现了很多不同的实现方式，比如Chord，Pastry，Kademlia等。BitTorrent中的DHT是基于Kademlia的一种变形，它的官方名称叫做 Mainline DHT。
DHT人如其名，把它看成一个整体，从远处看它，它就是一张哈希表，只不过这张表是分布式的，存在于很多机器上。它同时支持set(key, val)，get(key)操作。DHT可以用于很多方面，比如分布式文件系统，DNS，即时消息(IM)，以及我们最熟悉的点对点文件共享（比如BT协议）等。
下面我们提到的DHT默认都是Mainline DHT，例子都是用伪代码来表示。读下面段落的时候要时刻记着，DHT是一个哈希表。
Mainline DHT
Mainline DHT遵循DHT的架构，下面我们分别从Keyspace和Overlay network两方面具体说明。Keyspace
keyspace主要是关于key的一些规定。
Mainline dht里边的key长度为160bit，注意是bit，不是byte。在常见的编译型编程语言中，最长的整型也才是64bit，所以用整型是表示不了key的，我们得想其他的方式。我们可以用数组方式表示它，数组类型你可以选用长度不同的整型，比如int8，int16，int32等。这里为了下边方便计算，我们采用长度为20的byte数组来表示。
在mainline dht中，key之间唯一的一种计算是xor，即异或（还记得异或的知识吧？）。我们的key是用长度为20的byte数组来表示，因此我们应该从前往后依次计算两个key的相对应的byte的异或值，最终结果得到的是另外一个长度为20的byte数组。算法如下：
|
|
读到这里，你是不是要问xor有啥用？还记得原理篇中DHT的工作方式吗？
xor是为了找到好友表中离key最近的k个节点，什么样的节点最近？就是好友中每个节点和key相异或，得到的结果越小就越近。这里又衍生另外一个问题，byte数组之间怎么比较大小？很简单，从前往后，依次比较每一个byte的大小即可。
在Mainline DHT中，我们用160bit的key来代表每个节点和每个资源的ID，我们查找节点或者查找资源的时候实际上就是查找他们的ID。回想一下，这是不是很哈希表? :)
另外聪明的你可能又该问了，我们怎么样知道每个节点或者每个资源的ID是多少？在Mainline DHT中，节点的ID一般是随机生成的，而资源的ID是用sha1算法加密资源的内容后得到的。
OK，关于key就这么多，代码实现你可以查考这里。
Overlay network
Overlay network主要是关于DHT内部节点是怎么存储数据的，不同节点之间又是怎样通信的。
首先我们回顾一下原理篇中DHT的工作方式:
DHT 由很多节点组成，每个节点保存一张表，表里边记录着自己的好友节点。当你向一个节点A查询另外一个节点B的信息的时候，A就会查询自己的好友表，如果里边包含B，那么A就返回B的信息，否则A就返回距离B距离最近的k个节点。然后你再向这k个节点再次查询B的信息，这样循环一直到查询到B的信息，查询到B的信息后你应该向之前所有查询过的节点发个通知，告诉他们，你有B的信息。
整个DHT是一个哈希表，它把自己的数据化整为零分散在不同的节点里。OK，现在我们看下，一个节点内部是用什么样的数据结构存储数据的。
节点内部数据存储 - Routing Table
用什么样的数据结构得看支持什么样的操作，还得看各种操作的频繁程度。从上面工作方式我们知道，操作主要有两个：
在我（注意：“我”是一个节点）的好友节点中查询离一个key最近的k个节点（在Mainline DHT中，k=8），程度为频繁
把一个节点保存起来，也就是插入操作，程度为频繁
首先看到“最近”、“k”，我们会联想到top k问题。一个很straightforward的做法是，用一个数组保存节点。这样的话，我们看下算法复杂度。top k问题用堆解决，查询复杂度为O(k + (n-k)*log(k))，当k=8时，接近于O(n)；插入操作为O(1)。注：n为一个节点的好友节点总数。
当n很大的时候，操作时间可能会很长。那么有没有O(log(n))的算法呢？
联想到上面堆的算法，你可能说，我们可以维护一个堆啊，插入和查询的时候都是O(log(n))。这种做法堆是根据堆中元素与某一个固定不变的key的距离来维护的，但是通常情况下，我们查询的key都是变化的，因此这种做法不可行。
那还有其他O(log(n))的算法吗？
经验告诉我们，很多O(log(n))的问题都和二叉树相关，比如各种平衡二叉树，我们能不能用二叉树来解决呢？联想到每个ID都是一个160bit的值，而且我们知道key之间的距离是通过异或来计算的，并且两个key的异或结果大小和他们的共同前缀无关，我们应该想到用Trie树（或者叫前缀树）来解决。事实上，Mainline DHT协议中用的就是Trie树，但是与Trie树又稍微有所不同。在Trie树里边，插入一个key时，我们要比对key的每一个char和Trie里边路径，当不一致时，会立刻分裂成一个子树。但是在这里，当不一致时，不会立刻分裂，而是有一个长度为k的buffer（在Mainline DHT中叫bucket）。分两种情况讨论：
如果bucket长度小于k，那么直接插入bucket就行了。
如果bucket长度大于或等于k，又要分两种情况讨论：
第一种情况是当前的路径是该节点ID（注意不是要插入的key，是“我”自己的ID）的前缀，那么就分裂，左右子树的key分别是0和1，并且把当前bucket中的节点根据他们的当前char值分到相应的子树的bucket里边。
第二种情况是当前路径不是该节点ID的前缀，这种情况下，直接把这个key丢掉。
如果还没有理解，你可以参照Kademlia这篇论文上面的图。
插入的时候，复杂度为O(log(n))。查询离key最近的k个节点时，我们可以先找到当前key对应的bucket，如果bucket里边不够k个，那么我们再查找该节点前驱和后继，最后根据他们与key的距离拍一下序即可，平均复杂度也为O(log(n))。这样插入和查询都是O(log(n))。
代码实现你可以查考这里。
节点之间的通信 - KRPC
KRPC比较简单，它是一个简单的rpc结构，其是通过UDP传送消息的，报文是由bencode编码的字典。它包含3种消息类型，request、response和error。请求又分为四种：ping，find_node, get_peers, announce_peer。
ping 用来侦探对方是否在线
find_node 用来查找某一个节点ID为Key的具体信息，信息里包括ip，port，ID
get_peers 用来查找某一个资源ID为Key的具体信息，信息里包含可提供下载该资源的ip:port列表
announce_peer 用来告诉别人自己可提供某一个资源的下载，让别人把这个消息保存起来。还记得Angelababy那个例子吗？在我得到她的微信号后，我会通知所有我之前问过的人，他们就会把我有Angelababy微信号这个信息保存起来，以后如果有人再问他们有没有Angelababy微信号的话，他们就会告诉那个人我有。BT种子嗅探器就是根据这个来得到消息的，不过得到消息后我们还需要进一步下载。
跳出节点，整体看DHT这个哈希表，find_node和get_peers就是我们之前说的get(key)，announce_peer就是set(ke, val)。
剩下的就是具体的消息格式，你可以在官方文档上看到，这里就不搬砖了。
实现KRPC时，需要注意的有以下几点：
每次收到请求或者回复你都需要根据情况更新你的Routing Table，或保存或丢掉。
你需要实现transaction，transaction里边要包含你的请求信息以及被请求的ip及端口，只有这样当你收到回复消息时，你才能根据消息的transaction id做出正确的处理。Mainline DHT对于如何实现transaction没有做具体规定。
一开始你是不在DHT网络中的，你需要别人把你介绍进去，任何一个在DHT中的人都可以。一般我们可以向 router.bittorrent.com:6881、 dht.transmissionbt.com:6881 等发送find_node请求，然后我们的DHT就可以开始工作了。
KRPC的实现你可以参考这里。
总结
DHT整体就是一张哈希表，首先我们本身是里边的一个节点，我们向别人发送krpc find_node或get_peers消息，就是在对这个哈希表执行get(key)操作。向别人发送announce_peer消息，就是在对这个哈希表执行set(key, val)操作。