作者：freeyun

Docker安装rabbitmq

拉取镜像

docker pull rabbitmq:3-management

启动镜像（默认用户名密码）,默认guest 用户，密码也是 guest

docker run -d --hostname my-rabbit --name rabbit -p 15672:15672 -p 5672:5672 rabbitmq:3-management

启动镜像（设置用户名密码）

docker run -d --hostname my-rabbit --name rabbit -e RABBITMQ_DEFAULT_USER=user -e RABBITMQ_DEFAULT_PASS=password -p 15672:15672 -p 5672:5672 rabbitmq:3-management

完成后访问：http://freeyun.com:15672/

DHT协议

BitTorrent 使用“分布式哈希表” (DHT) 来存储种子的 peer 信息，且不需要专门的服务器。这样，每一个 peer 都变成一个 tracker。DHT 协议基于 Kademila，且用 UDP 实现。

请注意文档中的术语以免产生误解。
peer 实现了 BitTorrent 协议，既是服务器也是客户端，且监听在 TCP 端口。
node 实现了 DHT 协议，同样既是服务器也是客户端，监听在 UDP 端口。DHT 由 node 和 peer 的位置信息构成。
BitTorrent 客户端有一个 DHT node，用来和 DHT 中的其他 node 通信用，从而获取 peer 的位置。

概述

每一个 node 都有一个全球唯一标识符，称作 node ID。Node ID 是从 160-bit 的空间中随机选取的，这和 BitTorrent 的infohashes 一致。距离参数（Distance metric）用来比较两个 node ID 之间的接近程度。Nodes 必须维护一个包含其他 node 联系信息的路由表。对那些和自身接近的其他 Node ID，路由表中会有跟多细节。所以 DHT 中，接近自己的 ID 有很多，远的 ID 则较少。

在 Kademila 中，距离参数使用异或计算，结果为无符号整形，即

distance(A, B) = | A XOR B |

值越小越接近。

当一个 node 想要获取种子的其他 peer 时，它先计算种子的 infohash 和路由表中已有 nodes 的距离参数。然后向距离种子最近的 node 询问 peer 信息。如果恰巧该 node 有，则返回给询问的 node。否则，该 node 把自己路由表中离种子最近的 node 信息返回。本 node 拿到返回信息之后，不停重复上述步骤直到没有新 node 信息返回。搜索结束时，客户端将自己的 peer 信息返回给离种子最近的 node。

peer 查询的返回值必须包含令牌(token)。如果一个 node 宣称自己拥有的 peer 正在下载种子时，必须使用最近接收到的 token。当本 node 试图下载种子时，被请求的 node 检查 IP 地址对应的 token 是否一致。这么做是为了防止恶意主机从其他主机下载种子。由于 token 仅仅由请求 node 返回给被请求 node，故协议并未规定其实现。token 在分发后一段时间内必须被接受。BitTorrent 使用 IP + secret 的 SHA1 值作为 token，每 5 分钟改变一次，有 10 分钟有效期。

路由表

每一个 node 维护了一个好 node 的路由表。路由表的中 node 被用作查询的起始节点，并返回查询的响应信息。

并非所有 node 是等价的，有些是“好”的，有些则不。大部分 node 能够使用 DHT 协议发送查询和接受响应，但却不能响应其他 node 的查询。所以在路由表中，必须只包含好的 node。一个好的 node 被定义为能在 15 分钟内响应查询，或者 15 分钟内曾经响应过。若 15 钟没响应，则是可疑的。若对一系列请求都失去响应，则为坏的 node。已知的好的 node 拥有更高的优先级。

路由表覆盖从 0 到 2^160 完整的 node ID 空间。路由表又被分为 bucket，每一个拥有一部分子空间。空的表只有一个 bucket，其 ID 范围为 min=0 到 max=2^160。当 ID 为 N 的 node 插入到表中时，它必须放在 min=0 到 max=2^160 之间。由于空的表只有一个 bucket，所有 node 都在该 bucket 中。每个 bucket 可以存放 K 个 node，目前 K <= 8。当 bucket 存满好的 node 时，不允许再插入，除非其本身就在该 bucket 中。在这种情况下，原 bucket 分裂为两个相同大小的 bucket，比如原始 bucket 分裂为 0 到 2^159，2^159 到 2^160。

当 bucket 装满了好的 node，新的 node 会被丢弃。一旦 bucket 中的某个 node 变坏，就会用新的 node 来替换这个坏的 node。如果 bucket 中有在 15 分钟内都没有活跃过的 bucket，则其为可疑的 node，这时我们向最久没有联系的 node 发送 ping。如果有回复，那么我们向下一个可疑的 node 发送 ping，不断这样循环下去，直到有某一个 node 没有给出 ping 的回复，或者当前 bucket 中的所有 node 都是好的 (即都不是可疑节点，且在过去 15 分钟内都有活动)。如果 bucket 中的某个 node 没有对我们的 ping 给出回复，还会再试一次 (再发送一次 ping，也许仍然是活跃的，但由于网络拥塞，所以发生了丢包现象，注意 DHT 的包都是 UDP 的)，而不是立即丢弃该 node 或者直接用新 node 来替代它。这样，路由表中永远是活跃的 node。

每个 bucket 都应该维护一个 lastchange 字段来表明自身的”新鲜”程度。当 bucket 中的 node 被 ping 并给出了回复，或者一个 node 被加入到了 bucket，或者有新的 node 替代了旧的，bucket 的 lastchange 字段都应当更新。如果一个 bucket 的 lastchange 在过去的 15 分钟内都没有变化，那么将重更新它。这个重更新为：从这个 bucket 所覆盖的范围中随机选择一个 node ID，并对这个 ID 执行 find_nodes 搜索。请注意，收到请求的 node 通常不需要常常更新自己所在的 bucket。反之，不常常收到请求的 node 才需要周期性地更新所在 bucket。有了上述措施，在 DHT 时，才能有足够多的好的 node。

当插入第一个 node 到路由表并启动时，这个 node 应试着查找 DHT 中离自己最近的 node。这个查找工作是通过不断的发出 find_node 消息给越来越近的 node 来完成的，当没有更近的 node 时，搜索停止。路由表应当由客户端软件保存。

BitTorrent协议扩展

BitTorrent 协议被扩展为可通过 tracker 得到的 peer 之间互换 node 的 UDP 端口号。在这种方式下，当下载种子时，客户端能够自动更新路由表。新安装的客户端在无 tracker 的种子中获取不到路由表，必须在种子文件中找到联系信息。

Peers 如果支持 DHT 协议，会将 BitTorrent 协议握手消息的 8 字节保留位的最后一位置为 1。如果 peer 收到一个握手消息，表明对方支持 DHT 协议，则应该发送 PORT 消息。它由字节 0x09 开始，payload 的长度是 2 个字节，包含了这个 peer 的 DHT 所使用的 UDP 端口号。当 peer 收到这样的消息是应当向对方的 IP 和消息中指定的端口号的节点发送 ping。如果收到了 ping 的回复，则将新 node 的联系信息加入到路由表中。

种子文件扩展种子文件扩展

无 tracker 的种子文件中不含有 announce 关键字，相反，其包含有 nodes 关键字。该关键字应该包含种子创建者路由表的 K 个最近 node。也可以选择设置成已知的可用 node，比如这个种子的创建者。请不要加入 router.bittorrent.com。

nodes = [["<host>", <port>], ["<host>", <port>], ...]
nodes = [["127.0.0.1", 6881], ["your.router.node", 4804]]

KRPC协议

KRPC 协议是一个简单的 RPC 通信框架，其在 UDP 上使用 bencoded 编码的字典，包含请求与回复，但没有重试。有三种消息类型：query, response, error。对于 DHT 协议来说，有 4 种 query: ping, find_node, get_peers, announce_peer。

KRPC 消息是一个简单字典，包含两个必填关键字，附加的关键字取决于消息类型。第一个必填关键字是 t，这是一个字符串表示的 transaction ID。它由请求 node 产生，且包含在回复中，所以回复有可能对应单个 node 的多个请求。transaction ID 应该被编码成字符串表示的二进制数字，通常是两个字符，这样就能包含 2^16 种请求。另一个必填关键字是 y，其对应值表示消息类型，为 q, r 或 e。

联系信息编码

peer 的联系信息被编码成 6 字节的字符串。4 字节为 IP 地址，2 字节为端口号，均用网络字节序表示。

node 的联系信息被编码成 26 字节的字符串。20 字节为 node ID，剩余为 IP 和端口号信息，均用网络字节序表示。

Queries

query 为键值对 y:q，含有两个附加关键字，q 和 a。关键字 q 的值包含了请求类型的字符串表示。关键字 a 的值包含了一个所有返回值的字典。

Responses

response 为键值对 y:r，含有一个附加关键字 r。关键字 r 的值包含了一个所有返回值的字典。

Errors

error 为键值对 y:e，含有一个附加关键字 e。e 为一个列表。第一个元素是整形表示的错误码。第二个元素是字符串表示的错误信息。以下为可能的错误码，

Code        Description 
=======================
201         Generic Error 
202         Server Error 
203         Protocol Error, such as a malformed 
            packet, invalid arguments, or bad 
            token 
204         Method Unknown

示例，

generic error = {"t":"aa", "y":"e", "e":[201, "A Generic Error Ocurred"]}
bencoded = d1:eli201e23:A Generic Error Ocurrede1:t2:aa1:y1:ee

DHT Queries

所有的 query 都有一个键值对 ‘id:请求 node ID’。所有的 response 也有一个键值对 ‘id:响应的 node ID’。

ping

最基本的 query 是 ping。这时候 q=ping，id 为 20 字节网络字节序表示的发送者 node ID。该 query 的响应为 id=响应者 node ID。

arguments:  {"id" : "<querying nodes id>"}
response: {"id" : "<queried nodes id>"}

示例，

ping Query = {"t":"aa", "y":"q", "q":"ping", "a":{"id":"abcdefghij0123456789"}}
bencoded = d1:ad2:id20:abcdefghij0123456789e1:q4:ping1:t2:aa1:y1:qe

Response = {"t":"aa", "y":"r", "r": {"id":"mnopqrstuvwxyz123456"}}
bencoded = d1:rd2:id20:mnopqrstuvwxyz123456e1:t2:aa1:y1:re

find_node

find_node 被用来查找给定 ID 的 node 的联系信息。这时 q == find_node。find_node 请求包含 2 个参数，第一个参数是 id，包含了请求 node ID。第二个参数是 target，包含了请求者正在查找的 node ID。当一个 node 接收到了 find_node 的 query，他应该给出对应的回复，回复中包含 2 个关键字 id 和 nodes，nodes 是字符串类型，包含了被请求 node 的路由表中最接近目标 node 的 K(8) 个最接近的 node 的联系信息。

arguments:  {"id" : "<querying nodes id>", "target" : "<id of target node>"}
response: {"id" : "<queried nodes id>", "nodes" : "<compact node info>"}

示例，

find_node Query = {"t":"aa", "y":"q", "q":"find_node", "a": {"id":"abcdefghij0123456789", "target":"mnopqrstuvwxyz123456"}}
bencoded = d1:ad2:id20:abcdefghij01234567896:target20:mnopqrstuvwxyz123456e1:q9:find_node1:t2:aa1:y1:qe
Response = {"t":"aa", "y":"r", "r": {"id":"0123456789abcdefghij", "nodes": "def456..."}}
bencoded = d1:rd2:id20:0123456789abcdefghij5:nodes9:def456...e1:t2:aa1:y1:re

get_peers

get_peers 与种子文件的 infohash 有关。这时 q=get_peers。get_peers 请求包含 2 个参数。第一个参数是 id，包含了请求 node 的 ID。第二个参数是 info_hash，它代表种子文件的 infohash。如果被请求的 node 有对应 info_hash 的 peers，他将返回一个关键字 values，这是一个列表类型的字符串。每一个字符串包含了 CompactIP-address/portinfo 格式的 peers 信息。如果被请求的 node 没有这个 infohash 的 peers，那么他将返回关键字 nodes，这个关键字包含了被请求 node 的路由表中离 info_hash 最近的 K 个 node，使用 Compactnodeinfo 格式回复。在这两种情况下，关键字 token 都将被返回。之后的 annouce_peer 请求中必须包含 token。token 是一个短的二进制字符串。

arguments:  {"id" : "<querying nodes id>", "info_hash" : "<20-byte infohash of target torrent>"}
response: {"id" : "<queried nodes id>", "token" :"<opaque write token>", "values" : ["<peer 1 info string>", "<peer 2 info string>"]}
or: {"id" : "<queried nodes id>", "token" :"<opaque write token>", "nodes" : "<compact node info>"}

示例，

get_peers Query = {"t":"aa", "y":"q", "q":"get_peers", "a": {"id":"abcdefghij0123456789", "info_hash":"mnopqrstuvwxyz123456"}}
bencoded = d1:ad2:id20:abcdefghij01234567899:info_hash20:mnopqrstuvwxyz123456e1:q9:get_peers1:t2:aa1:y1:qe
Response with peers = {"t":"aa", "y":"r", "r": {"id":"abcdefghij0123456789", "token":"aoeusnth", "values": ["axje.u", "idhtnm"]}}
bencoded = d1:rd2:id20:abcdefghij01234567895:token8:aoeusnth6:valuesl6:axje.u6:idhtnmee1:t2:aa1:y1:re
Response with closest nodes = {"t":"aa", "y":"r", "r": {"id":"abcdefghij0123456789", "token":"aoeusnth", "nodes": "def456..."}}
bencoded = d1:rd2:id20:abcdefghij01234567895:nodes9:def456...5:token8:aoeusnthe1:t2:aa1:y1:re

announce_peer

announce_peer 表示某个端口正在下载种子文件。announce_peer 包含 4 个参数。第一个参数是 id，包含了请求 node ID；第二个参数是 info_hash，包含了种子文件的 infohash；第三个参数是 port 包含了整型的端口号，表明 peer 在哪个端口下载；第四个参数是 token，这是在之前的 get_peers 请求中收到的回复中所包含的。收到 announce_peer 请求的 node 必须检查这个 token 与回复的 token 是否相同。如果相同，那么被请求的 node 将记录发送者的 IP 和端口号，记录在 peer 联系信息中对应的 infohash 下。

arguments:  {"id" : "<querying nodes id>",
  "implied_port": <0 or 1>,
  "info_hash" : "<20-byte infohash of target torrent>",
  "port" : <port number>,
  "token" : "<opaque token>"}

response: {"id" : "<queried nodes id>"}

示例，

announce_peers Query = {"t":"aa", "y":"q", "q":"announce_peer", "a": {"id":"abcdefghij0123456789", "implied_port": 1, "info_hash":"mnopqrstuvwxyz123456", "port": 6881, "token": "aoeusnth"}}
bencoded = d1:ad2:id20:abcdefghij01234567899:info_hash20:<br />
mnopqrstuvwxyz1234564:porti6881e5:token8:aoeusnthe1:q13:announce_peer1:t2:aa1:y1:qe
Response = {"t":"aa", "y":"r", "r": {"id":"mnopqrstuvwxyz123456"}}
bencoded = d1:rd2:id20:mnopqrstuvwxyz123456e1:t2:aa1:y1:re

 

Mongodb在windows的安装

本文是描述Mongodb3.6在windows10的下的安装，下面的所有步骤都是在cmd运行

下载Mongodb安装包

下载地址：https://www.mongodb.com/download-center，运行安装

管理员运行cmd

按键盘win按键，cmd 然后右键管理员运行

创建目录（数据库和日志目录）

mkdir c:\data\db
mkdir c:\data\log

创建配置文件mongod.cfg

systemLog:
    destination: file
    path: c:\data\log\mongod.log
storage:
    dbPath: c:\data\db

安装Mongodb服务

"C:\Program Files\MongoDB\Server\3.6\bin\mongod.exe" --config "C:\Program Files\MongoDB\Server\3.6\mongod.cfg" --install

启动Mongodb服务

net start MongoDB

停止或者删除Mongodb服务

net stop MongoDB
"C:\Program Files\MongoDB\Server\3.6\bin\mongod.exe" --remove

策略模式与命令模式比较及实现

定义

Strategy策略模式 把易于变化的行为分别封装起来，让它们之间可以互相替换， 让这些行为的变化独立于拥有这些行为的客户。
GoF《设计模式》中说道：定义一系列算法，把它们一个个封装起来，并且使它们可以相互替换。该模式使得算法可独立于它们的客户变化。

Command命令模式是一种对象行为型模式，它主要解决的问题是：在软件构建过程中，“行为请求者”与“行为实现者”通常呈现一种“紧耦合”的问题。
GoF《设计模式》中说道：将一个请求封装为一个对象，从而使你可用不同的请求对客户进行参数化；对请求排队或记录请求日志，以及支持可撤销的操作。

区别

命令模式是含有不同的命令（含有接收者的请求）：做不同的事情；隐藏接收者执行细节。常见菜单事件，
而策略模式含有不同的算法，做相同的事情；
区别在于是否含有接收者。命令模式含有，策略模式不含有。

c++代码

策略模式

#include <iostream.h>
#include <fstream.h>
#include <string.h>

class Strategy;

class TestBed
{
  public:
    enum StrategyType
    {
        Dummy, Left, Right, Center
    };
    TestBed()
    {
        strategy_ = NULL;
    }
    void setStrategy(int type, int width);
    void doIt();
  private:
    Strategy *strategy_;
};

class Strategy
{
  public:
    Strategy(int width): width_(width){}
    void format()
    {
        char line[80], word[30];
        ifstream inFile("quote.txt", ios::in);
        line[0] = '\0';

        inFile >> word;
        strcat(line, word);
        while (inFile >> word)
        {
            if (strlen(line) + strlen(word) + 1 > width_)
              justify(line);
            else
              strcat(line, " ");
            strcat(line, word);
        }
        justify(line);
    }
  protected:
    int width_;
  private:
    virtual void justify(char *line) = 0;
};

class LeftStrategy: public Strategy
{
  public:
    LeftStrategy(int width): Strategy(width){}
  private:
     /* virtual */void justify(char *line)
    {
        cout << line << endl;
        line[0] = '\0';
    }
};

class RightStrategy: public Strategy
{
  public:
    RightStrategy(int width): Strategy(width){}
  private:
     /* virtual */void justify(char *line)
    {
        char buf[80];
        int offset = width_ - strlen(line);
        memset(buf, ' ', 80);
        strcpy(&(buf[offset]), line);
        cout << buf << endl;
        line[0] = '\0';
    }
};

class CenterStrategy: public Strategy
{
  public:
    CenterStrategy(int width): Strategy(width){}
  private:
     /* virtual */void justify(char *line)
    {
        char buf[80];
        int offset = (width_ - strlen(line)) / 2;
        memset(buf, ' ', 80);
        strcpy(&(buf[offset]), line);
        cout << buf << endl;
        line[0] = '\0';
    }
};

void TestBed::setStrategy(int type, int width)
{
  delete strategy_;
  if (type == Left)
    strategy_ = new LeftStrategy(width);
  else if (type == Right)
    strategy_ = new RightStrategy(width);
  else if (type == Center)
    strategy_ = new CenterStrategy(width);
}

void TestBed::doIt()
{
  strategy_->format();
}

int main()
{
  TestBed test;
  int answer, width;
  cout << "Exit(0) Left(1) Right(2) Center(3): ";
  cin >> answer;
  while (answer)
  {
    cout << "Width: ";
    cin >> width;
    test.setStrategy(answer, width);
    test.doIt();
    cout << "Exit(0) Left(1) Right(2) Center(3): ";
    cin >> answer;
  }
  return 0;
}

命令模式

#include <iostream>
using namespace std;

#define SAFE_DELETE(p) if (p) { delete p; p = NULL; }

class Receiver
{
public:
     void Action()
     {
          cout<<"Receiver->Action"<<endl;
     }
};

class Command
{
public:
     virtual void Execute() = 0;
};

class ConcreteCommand : public Command
{
public:
     ConcreteCommand(Receiver *pReceiver) : m_pReceiver(pReceiver){}
     void Execute()
     {
          m_pReceiver->Action();
     }
private:
     Receiver *m_pReceiver;
};

class Invoker
{
public:
     Invoker(Command *pCommand) : m_pCommand(pCommand){}
     void Invoke()
     {
          m_pCommand->Execute();
     }
private:
     Command *m_pCommand;
};

int main()
{
     Receiver *pReceiver = new Receiver();
     Command *pCommand = new ConcreteCommand(pReceiver);
     Invoker *pInvoker = new Invoker(pCommand);
     pInvoker->Invoke();
     SAFE_DELETE(pInvoker);
     SAFE_DELETE(pCommand);
     SAFE_DELETE(pReceiver);
     return 0;
}

 

BT种子嗅探器:DHT

之前写了原理篇，在原理篇里简单的介绍了一下DHT，但是还不够详细。今天我们就专门详细的讲一下嗅探器的核心-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数组。算法如下：

​for i = 0; i < 20; i++ {
​ result[i] = key1[i] ^ key2[i];
​}

 

读到这里，你是不是要问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)操作。

OK，今天就说到这里，关于怎么样下载，我们下篇再说

转自：https://github.com/shiyanhui/dht/wiki

加速github访问克隆

不定期更新ip地址2017 7月8日更新

github的各种问题

针对GitHub.com 打开忙，布局乱，Git clone速度慢到4K ，或者断开
fatal: early EOF
fatal: The remote end hung up unexpectedly
fatal: index-pack failed
git did not exit cleanly (exit code 128)

修改hosts

  • 用文本编辑器打开：%SystemRoot%\System32\drivers\etc\hosts
  • 复制内容上面文件

已失效

# GitHub Start
#151.101.112.249 github.global.ssl.fastly.net
#110.4.24.178    bit.ly
110.4.24.178    github.com
110.4.24.178    raw.githubusercontent.com
110.4.24.178    gist.github.com
110.4.24.178    assets-cdn.github.com
110.4.24.178    avatars0.githubusercontent.com
110.4.24.178    avatars1.githubusercontent.com
110.4.24.178    avatars2.githubusercontent.com
110.4.24.178    avatars3.githubusercontent.com
110.4.24.178    camo.githubusercontent.com
110.4.24.178    cloud.githubusercontent.com
110.4.24.178    collector.githubapp.com
# GitHub End

已失效

# Github start
192.30.255.118  github.global.ssl.fastly.net
192.30.253.118	gist.github.com
# Github end

2017 07 08

192.30.255.112	gist.github.com
151.101.44.249	global-ssl.fastly.net

windows刷新DNS

启动cmd 命令窗口输入：ipconfig/flushdns
Linux的etc/hosts

bt种子搜索原理

前言

之前看到L灯 这个十分火的工具，其利用了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种子搜索引擎，建立自己的海盗湾。但你需要注意版权问题和色情资源问题。
转自：https://github.com/shiyanhui/dht/wiki

mysql x64在windows安装

windwos mysql x64版，没提供exe的安装包。

下载mysql x64

选择Windows (x86, 64-bit), ZIP Archive:
https://dev.mysql.com/downloads/mysql/最新版
（trinitycore推荐版本）5.6：https://dev.mysql.com/downloads/mysql/5.6.html#downloads
解压到F盘：F:\mysql-5.6.34-winx64

安装mysql x64

1、在F:\mysql-5.6.34-winx64目录下新建my.ini

[mysqld]

#绑定IPv4和3306端口
bind-address = 0.0.0.0
port = 3306

# 设置mysql的安装目录
basedir=F:/mysql-5.6.34-winx64

# 设置mysql数据库的数据的存放目录
datadir=F:/mysql-5.6.34-winx64/data

# 允许最大连接数
max_connections=200

2、管理员运行cmd进入F:\mysql-5.6.34-winx64\bin：
安装：mysqld -install

mysql 5.7以上的版本必须执行下面的
mysqld --initialize [with random root password] //root 随机密码
mysqld --initialize-insecure [without random root password]//root 空密码

启动：net start mysql
删除：mysqld -remove
3、添加F:\mysql-5.6.34-winx64\bin到环境变量PATH

管理添加用户：

喜欢用命令的用命令，或者图形管理

cocos2d-x安卓静态库

cocos2d-x的新建工程项目重新编译整个引擎，在windows系统下好说，只需要把库指定。android和IOS如果也是每个项目都生成引擎，游戏项目多硬盘空间也吃紧。适用cocos2d3.13 ，3.5版不通过

  1.  首先找到一个cocos2d-x的测试项目（如cpp_test)，进行一次编译。完成后，在proj.android/obj/local目录下可以找到中间过程中生成的所有静态库文件。把这些静态库文件（带上ABI目录）复制出来，objs-debug和objs文件夹可删除，放到一个新的目录（如：cclib）中。
  2.  在cclib中创Android.mk文件，文件内容见代码附1.
  3. 新建Windows环境变量 CC_SRC_ROOT 为cocos2d源码目录（即cocos与external的上层目录）
  4. 在编译你的项目时依赖cclib即可，不需要依赖cocos2d目录下的Android.mk 附2

附1(cclib/Android.mk)

LOCAL_PATH := $(call my-dir)

include $(CLEAR_VARS)

LOCAL_MODULE := cc_static
LOCAL_MODULE_FILENAME := libcc

LOCAL_EXPORT_C_INCLUDES := $(CC_SRC_ROOT)/cocos \
                    $(CC_SRC_ROOT)/cocos/. \
                    $(CC_SRC_ROOT)/cocos/.. \
                    $(CC_SRC_ROOT)/cocos/platform \
                    $(CC_SRC_ROOT)/cocos/base \
					$(CC_SRC_ROOT)/extensions \
                    $(CC_SRC_ROOT)/external \
                    $(CC_SRC_ROOT)/external/tinyxml2 \
                    $(CC_SRC_ROOT)/external/unzip \
                    $(CC_SRC_ROOT)/external/chipmunk/include/chipmunk \
                    $(CC_SRC_ROOT)/external/xxhash \
                    $(CC_SRC_ROOT)/external/nslog \
                    $(CC_SRC_ROOT)/external/poly2tri \
                    $(CC_SRC_ROOT)/external/poly2tri/common \
                    $(CC_SRC_ROOT)/external/poly2tri/sweep \
					$(CC_SRC_ROOT)/cocos/platform/android \
					$(CC_SRC_ROOT)/cocos/audio/include \
					$(CC_SRC_ROOT)/external/curl/include/android \
					$(CC_SRC_ROOT)/external/websockets/include/android \
					$(CC_SRC_ROOT)/cocos/editor-support \
					$(CC_SRC_ROOT)/external/Box2D \
					$(CC_SRC_ROOT)/external/flatbuffers \
					$(CC_SRC_ROOT)/external

LOCAL_CFLAGS   :=  -DUSE_FILE32API -fexceptions

LOCAL_CPPFLAGS := -Wno-deprecated-declarations -Wno-extern-c-compat

LOCAL_EXPORT_CFLAGS   := -DUSE_FILE32API -fexceptions

LOCAL_EXPORT_CPPFLAGS := -Wno-deprecated-declarations -Wno-extern-c-compat

LOCAL_EXPORT_LDLIBS := -lGLESv2 \
                       -llog \
                       -landroid \
               -lGLESv1_CM \
                       -lEGL \
               -lOpenSLES

# define the macro to compile through support/zip_support/ioapi.c


LOCAL_WHOLE_STATIC_LIBRARIES := cocos_freetype2_static
LOCAL_WHOLE_STATIC_LIBRARIES += cocos_png_static
LOCAL_WHOLE_STATIC_LIBRARIES += cocos_jpeg_static
LOCAL_WHOLE_STATIC_LIBRARIES += cocos_tiff_static
LOCAL_WHOLE_STATIC_LIBRARIES += cocos_webp_static
LOCAL_WHOLE_STATIC_LIBRARIES += cocos_chipmunk_static
LOCAL_WHOLE_STATIC_LIBRARIES += cocos_zlib_static
LOCAL_WHOLE_STATIC_LIBRARIES += cocos_curl_static
LOCAL_WHOLE_STATIC_LIBRARIES += websockets_static

LOCAL_WHOLE_STATIC_LIBRARIES += flatbuffers_static
LOCAL_WHOLE_STATIC_LIBRARIES += libaudioengine_static
LOCAL_WHOLE_STATIC_LIBRARIES += libbox2d_static
LOCAL_WHOLE_STATIC_LIBRARIES += libbullet_static
LOCAL_WHOLE_STATIC_LIBRARIES += libcocos2d_static
LOCAL_WHOLE_STATIC_LIBRARIES += libcocos2dandroid_static
LOCAL_WHOLE_STATIC_LIBRARIES += libcocos2dxinternal_static
LOCAL_WHOLE_STATIC_LIBRARIES += libcocos3d_static
LOCAL_WHOLE_STATIC_LIBRARIES += libcocosbuilder_static
LOCAL_WHOLE_STATIC_LIBRARIES += libcocosdenshion_static
LOCAL_WHOLE_STATIC_LIBRARIES += libcocostudio_static
#LOCAL_WHOLE_STATIC_LIBRARIES += libcpufeatures_static
LOCAL_WHOLE_STATIC_LIBRARIES += libextension_static
LOCAL_WHOLE_STATIC_LIBRARIES += libnetwork_static
LOCAL_WHOLE_STATIC_LIBRARIES += librecast_static
LOCAL_WHOLE_STATIC_LIBRARIES += libspine_static
LOCAL_WHOLE_STATIC_LIBRARIES += libui_static

include $(BUILD_STATIC_LIBRARY)

include $(CLEAR_VARS)
LOCAL_MODULE := flatbuffers_static
LOCAL_SRC_FILES := $(TARGET_ARCH_ABI)/flatbuffers.a
include $(PREBUILT_STATIC_LIBRARY)

include $(CLEAR_VARS)
LOCAL_MODULE := libaudioengine_static
LOCAL_SRC_FILES := $(TARGET_ARCH_ABI)/libaudioengine.a
include $(PREBUILT_STATIC_LIBRARY)

include $(CLEAR_VARS)
LOCAL_MODULE := libbox2d_static
LOCAL_SRC_FILES := $(TARGET_ARCH_ABI)/libbox2d.a
include $(PREBUILT_STATIC_LIBRARY)

include $(CLEAR_VARS)
LOCAL_MODULE := libbullet_static
LOCAL_SRC_FILES := $(TARGET_ARCH_ABI)/libbullet.a
include $(PREBUILT_STATIC_LIBRARY)

include $(CLEAR_VARS)
LOCAL_MODULE := libcocos2d_static
LOCAL_SRC_FILES := $(TARGET_ARCH_ABI)/libcocos2d.a
include $(PREBUILT_STATIC_LIBRARY)

include $(CLEAR_VARS)
LOCAL_MODULE := libcocos2dandroid_static
LOCAL_SRC_FILES := $(TARGET_ARCH_ABI)/libcocos2dandroid.a
include $(PREBUILT_STATIC_LIBRARY)

include $(CLEAR_VARS)
LOCAL_MODULE := libcocos2dxinternal_static
LOCAL_SRC_FILES := $(TARGET_ARCH_ABI)/libcocos2dxinternal.a
include $(PREBUILT_STATIC_LIBRARY)

include $(CLEAR_VARS)
LOCAL_MODULE := libcocos3d_static
LOCAL_SRC_FILES := $(TARGET_ARCH_ABI)/libcocos3d.a
include $(PREBUILT_STATIC_LIBRARY)

include $(CLEAR_VARS)
LOCAL_MODULE := libcocosbuilder_static
LOCAL_SRC_FILES := $(TARGET_ARCH_ABI)/libcocosbuilder.a
include $(PREBUILT_STATIC_LIBRARY)

include $(CLEAR_VARS)
LOCAL_MODULE := libcocosdenshion_static
LOCAL_SRC_FILES := $(TARGET_ARCH_ABI)/libcocosdenshion.a
include $(PREBUILT_STATIC_LIBRARY)

include $(CLEAR_VARS)
LOCAL_MODULE := libcocostudio_static
LOCAL_SRC_FILES := $(TARGET_ARCH_ABI)/libcocostudio.a
include $(PREBUILT_STATIC_LIBRARY)

include $(CLEAR_VARS)
LOCAL_MODULE := libcpufeatures_static
LOCAL_SRC_FILES := $(TARGET_ARCH_ABI)/libcpufeatures.a
include $(PREBUILT_STATIC_LIBRARY)

include $(CLEAR_VARS)
LOCAL_MODULE := libextension_static
LOCAL_SRC_FILES := $(TARGET_ARCH_ABI)/libextension.a
include $(PREBUILT_STATIC_LIBRARY)

include $(CLEAR_VARS)
LOCAL_MODULE := libnetwork_static
LOCAL_SRC_FILES := $(TARGET_ARCH_ABI)/libnetwork.a
include $(PREBUILT_STATIC_LIBRARY)

include $(CLEAR_VARS)
LOCAL_MODULE := librecast_static
LOCAL_SRC_FILES := $(TARGET_ARCH_ABI)/librecast.a
include $(PREBUILT_STATIC_LIBRARY)

include $(CLEAR_VARS)
LOCAL_MODULE := libspine_static
LOCAL_SRC_FILES := $(TARGET_ARCH_ABI)/libspine.a
include $(PREBUILT_STATIC_LIBRARY)

include $(CLEAR_VARS)
LOCAL_MODULE := libui_static
LOCAL_SRC_FILES := $(TARGET_ARCH_ABI)/libui.a
include $(PREBUILT_STATIC_LIBRARY)

#==============================================================
$(call import-module,freetype2/prebuilt/android)
$(call import-module,png/prebuilt/android)
$(call import-module,zlib/prebuilt/android)
$(call import-module,jpeg/prebuilt/android)
$(call import-module,tiff/prebuilt/android)
$(call import-module,webp/prebuilt/android)
$(call import-module,chipmunk/prebuilt/android)
$(call import-module,curl/prebuilt/android)
$(call import-module,websockets/prebuilt/android)

附2(cpp-empty-test)

LOCAL_PATH := $(call my-dir)

include $(CLEAR_VARS)

LOCAL_MODULE := cpp_empty_test_shared

LOCAL_MODULE_FILENAME := libcpp_empty_test

LOCAL_ARM_MODE := arm

LOCAL_SRC_FILES := main.cpp \
                   ../../Classes/AppDelegate.cpp \
                   ../../Classes/HelloWorldScene.cpp

LOCAL_C_INCLUDES := $(LOCAL_PATH)/../../Classes \
                    $(LOCAL_PATH)/../../../../extensions \
                    $(LOCAL_PATH)/../../../.. \
                    $(LOCAL_PATH)/../../../../cocos/editor-support

#LOCAL_STATIC_LIBRARIES := cocos2dx_static
LOCAL_WHOLE_STATIC_LIBRARIES := cc_static
include $(BUILD_SHARED_LIBRARY)

#$(call import-module,.)
$(call import-module,cclib)

参考：http://www.cnblogs.com/leaving/p/5362918.html

unrealengine最新版源代码

获取ue4全部源代码

什么是github？

github是程序员乐园，用来托管开发项目的源代码，基于web。

如何访问github上的ue4源代码

简单的四步骤：
1、创建登录github.com账号
2、注册ue的账号，拼关联github的账号https://www.unrealengine.com/dashboard/settings
ue-github
3、访问UE的地址：http://github.com/EpicGames，看到UE的邀请点击它将会看到
EpicGames
4、用git工具下载开发中的版本，或者下载稳定版https://github.com/EpicGames/UnrealEngine/releases

你需要的源代码

大部分程序员只需安装版本，如果你直接修改UE引擎源代码，那么你是来对地方。
引用网址：https://www.unrealengine.com/ue4-on-github