2021年4月 – 王春伟的技术博客

最多能创建多少个TCP连接？

https://mp.weixin.qq.com/s/mGkf-9LZhhUgSIRBRqfRDw

低并发编程

战略上藐视技术，战术上重视技术

本文坚持看到结尾才有动图

气不气？

我是一个 Linux 服务器上的进程，名叫小进。

老是有人说我最多只能创建 65535 个 TCP 连接。

我不信这个邪，今天我要亲自去实践一下。

我走到操作系统老大的跟前，说：

“老操，我要建立一个 TCP 连接！”

老操不慌不忙，拿出一个表格递给我，”小进，先填表吧”

我一看这个表，这不就是经典的 socket 四元组嘛。我只有一块网卡，其 IP 地址是 123.126.45.68，我想要与 110.242.68.3 的 80 端口建立一个 TCP 连接，我将这些信息填写在了表中。

源端口号填什么呢？我记得端口号是 16 位的，可以有 0 ~ 65535 这个范围的数字，那我随便选一个吧！

正当我犹豫到底选什么数字的时候，老操一把抢过我的表格。

“你墨迹个啥呢小进？源端口号不用你填，我会给你分配一个可用的数字。源IP也不用你填，我知道都有哪些网卡，并且会帮你选个合适的。真是个新手，回去等消息吧。”

“哦”

老操带着我的表格，走了。

过了很长时间，老操终于回来了，并且带着一个纸条。

“小进，你把这个收好了。”

我问道，”这是啥呀？”

老操不耐烦地说道，”刚刚说你是新手你还不服，这个 5 表示文件描述符，linux 下一切皆文件，你待会和你那个目标 IP 进行 TCP 通信的时候，就对着这个文件描述符读写就好啦。”

“这么方便！好的，谢谢老操。”

我拿着这个文件描述符，把它放到属于我的内存中裱起来了，反正我只是想看看最多能创建多少 TCP 连接，又不是去真的用它，嘻嘻。

端口号

过了一分钟，我又去找老操了。

“老操，我要建立一个 TCP 连接！”

老操不慌不忙，拿出一个表格递给我，”小进，先填表吧”

这回我熟悉了，只把目标IP和目标端口填好。

老操办好事之后，又带着一个纸条回来，上面写着数字”6″。

就这样，我每隔一分钟都去找老操建立一个新的 TCP 连接，目标 IP 都是110.242.68.3，目标端口都是 80。

老操也很奇怪，不知道我在这折腾啥，他虽然权力大，但无权拒绝我的指令，每次都兢兢业业地把事情办好，并给我一张一张写着文件描述符的纸条。

直到有一次，我收到的纸条有些不同。

我带着些许责怪的语气问，”老操，这是怎么回事呀？”

老操也没好气地说，”这表示端口号不够用啦！早就觉得你小子不对劲了，一个劲地对着同一个 IP 和端口创建 TCP 连接，之前没办法必须执行你给的指令，现在不行了，端口号不够用了，源端口那里我没法给你填了。”

我也不是那么好骗的，质疑道。”老操，你也别欺负我这个新手，我可是知道端口号是 16 位的，范围是 1~65535，一共可以创建 65535 个 TCP 连接，我现在才创建了 63977 个，怎么就不够了！”

老操鄙视地看了我一眼，”你小子可真是闲的蛋疼啊，还真一个个数，来我告诉你吧，Linux 对可使用的端口范围是有具体限制的，具体可以用如下命令查看。”

[root]# cat /proc/sys/net/ipv4/ip_local_port_range 
1024 65000

“看到没，当前的限制是1024~65000，所以你就只能有63977个端口号可以使用。”

我赶紧像老操道歉，”哎哟真是抱歉，还是我见识太少，那这个数可以修改么？”

老操也没跟我一般见识，还是耐心地回答我，”可以的，具体可以 vim /etc/sysctl.conf 这个文件进行修改，我们在这个文件里添加一行记录”

net.ipv4.ip_local_port_range = 60000 60009

“保存好后执行 sysctl -p /etc/sysctl.conf 使其生效。这样你就只有 10 个端口号可以用了，就会更快报出端口号不够用的错误”

“原来如此，谢谢老操又给我上了一课。”

哎不对，建立一个 TCP 连接，需要将通信两端的套接字（socket）进行绑定，如下：

源 IP 地址：源端口号 <—-> 目标 IP 地址：目标端口号

只要这套绑定关系构成的四元组不重复即可，刚刚端口号不够用了，是因为我一直对同一个目标IP和端口建立连接，那我换一个目标端口号试试。

我又把这个表交给老操，老操一眼就看破了我的小心思，可是也没办法，马上去给我建立了一个新的TCP连接，并且成功返回给我一个新的文件描述符纸条。

看来成功了，只要源端口号不用够用了，就不断变换目标 IP 和目标端口号，保证四元组不重复，我就能创建好多好多 TCP 连接啦！

这也证明了有人说最多只能创建 65535 个TCP连接是多么荒唐。

文件描述符

找到了突破端口号限制的办法，我不断找老操建立TCP连接，老操也拿我没有办法。

直到有一次，我又收到了一张特殊的纸条，上面写的不是文件描述符。

我又没好气地问老操，”这又是咋回事？”

老操幸灾乐祸地告诉我，”呵呵，你小子以为突破端口号限制就无法无天了？现在文件描述符不够用啦！”

“怎么啥啥都有限制啊？你们操作系统给我们的限制也太多了吧？”

“废话，你看看你都建了多少个TCP连接了！每建立一个TCP连接，我就得分配给你一个文件描述符，linux 对可打开的文件描述符的数量分别作了三个方面的限制。”

系统级：当前系统可打开的最大数量，通过 cat /proc/sys/fs/file-max 查看

用户级：指定用户可打开的最大数量，通过 cat /etc/security/limits.conf 查看

进程级：单个进程可打开的最大数量，通过 cat /proc/sys/fs/nr_open 查看

天呢，真是人在屋檐下呀，我赶紧看了看这些具体的限制。

[root ~]# cat /proc/sys/fs/file-max
100000
[root ~]# cat /proc/sys/fs/nr_open
100000
[root ~]# cat /etc/security/limits.conf
...
* soft nproc 100000
* hard nproc 100000

原来如此，我记得刚刚收到的最后一张纸条是。

再之后就收到文件描述符不够的错误了。

我又请教老操，”老操，那这个限制可以修改么？”

老操仍然耐心地告诉我，”当然可以，比如你想修改单个进程可打开的最大文件描述符限制为100，可以这样。”

echo 100 > /proc/sys/fs/nr_open

“原来如此，我这就去把各种文件描述符限制都改大一点，也不多，就在后面加个0吧”

“额，早知道不告诉你小子了。”老操再次用鄙视的眼睛看着我。

线程

突破了文件描述符限制，我又开始肆无忌惮地创建起了TCP连接。

但我发现，老操的办事效率越来越慢，建立一个TCP连接花的时间越来越久。

有一次，我忍不住责问老操，”你是不是在偷懒啊？之前找你建一个TCP连接就花不到一分钟时间，你看看最近我哪次不是等一个多小时你才搞好？”

老操也忍不住了，”小进啊你还好意思说我，你知不知道你每建一个TCP连接都需要消耗一个线程来为你服务？现在我和CPU老大那里都忙得不可开交了，一直在为你这好几十万个线程不停地进行上下文切换，我们精力有限啊，自然就没法像以前那么快为你服务了。”

听完老操的抱怨，我想起了之前似乎有人跟我说过 C10K 问题，就是当服务器连接数达到 1 万且每个连接都需要消耗一个线程资源时，操作系统就会不停地忙于线程的上下文切换，最终导致系统崩溃，这可不是闹着玩的。

我赶紧像操作系统老大请教，”老操，实在不好意思，一直以为你强大无比，没想到也有忙得不可开交的时候呀，那我们现在应该怎么办呀？”

老操无奈地说，”我劝你还是别再继续玩了，没什么意义，不过我想你也不会听我的，那我跟你说两句吧。”

你现在这种每建一个TCP连接就创建一个线程的方式，是最传统的多线程并发模型，早期的操作系统也只支持这种方式。但现在我进化了，我还支持 IO 多路复用的方式，简单说就是一个线程可以管理多个 TCP 连接的资源，这样你就可以用少量的线程来管理大量的 TCP 连接了。

我一脸疑惑，”啥是 IO 多路复用啊？”。

老操一脸鄙视，”你这… 你去看看闪客的《你管这破玩意叫 IO 多路复用》，就明白了。”

这次真是大开眼界了，我赶紧把代码改成了这种 IO 多路复用的模型，将原来的 TCP 连接销毁掉，改成同一个线程管理多个 TCP 连接，很快，操作系统老大就恢复了以往的办事效率，同时我的 TCP 连接数又多了起来。

内存

突破了端口号、文件描述符、线程数等重重限制的我，再次肆无忌惮地创建起了TCP连接。

直到有一次，我又收到了一张红牌。

嗨，又是啥东西限制了呀，改了不就完了。我不耐烦地问老操，”这回又是啥毛病？”

老操说道。”这个错误叫内存溢出，每个TCP连接本身，以及这个连接所用到的缓冲区，都是需要占用一定内存的，现在内存已经被你占满了，不够用了，所以报了这个错。”

我看这次老操特别耐心，也没多说什么，但想着被内存限制住了，有点不太开心，于是我让老操帮我最后一个忙。

“老操呀，帮小进我最后一个忙吧，你权利大，你看看把那些特别占内存的进程给杀掉，给我腾出点地方，我今天要完成我的梦想，看看TCP连接数到底能创建多少个！”

老操见我真的是够拼的，便答应了我，杀死了好多进程，我很是感动。

CPU

有了老操为我争取的内存资源，我又开始日以继日地创建TCP连接。

老操也不再说什么，同样日以继日地执行着我的指令。

有一次，老操语重心长地对我说，”差不多了，我劝你就此收手吧，现在 CPU 的占用率已经快到 100% 了。”

我觉得老操这人真的可笑，经过这几次的小挫折，我明白了只要思想不滑坡，方法总比苦难多，老操这人就是太谨慎了，我岂能半途而废，不管他。

我仍然继续创建着 TCP 连接。

直到有一天，老操把我请到一个小饭馆，一块吃了顿饭，吃好后说道。”咱哥俩也算是配合了很久啦，今天我是来跟你道个别的。”

我很不解地问，”怎么了老操，发生什么事了？。”

老操说，”由于你的 TCP 连接，CPU 占用率已经很长时间维持在 100%，我们的使用者，也就是我们的上帝，几乎什么事情都做不了了，连鼠标动一下都要等好久，所以他给我下达了一个重启的指令，我执行这个指令后，你，以及像你一样的所有进程，包括我这个操作系统本身，一切都就消失了。”

我大惊失色，”啊，这么突然么？这条指令什么时候执行？”

老操缓缓起身，”就现在了，刚刚这条指令还没得到 CPU 运行的机会，不过现在到了。”

突然，我眼前一黑，一切都没了。

总结

资源	一台Linux服务器的资源	一个TCP连接占用的资源	占满了会发生什么
CPU	看你花多少钱买的	看你用它干嘛	电脑卡死
内存	看你花多少钱买的	取决于缓冲区大小	OOM
临时端口号	ip_local_port_range	1	cannot assign requested address
文件描述符	fs.file-max	1	too many open files
进程\线程数	ulimit -n	看IO模型	系统崩溃

后记

其实这个问题，我觉得结论不重要，最重要的是思考过程。

而思考过程其实相当简单，就是，寻找限制条件而已，其实一开始这篇文章，我写了个故事在开头，但后来感觉放在后记更合适。故事是这样的。

闪客：小宇，我问你，你一天最多能吃多少个汉堡？

小宇：额，你这问的太隐私了吧，不过看在你教我技术的份上，我就告诉你，最多能吃 4 个左右吧。

闪客：咳咳真的么？好吧，那你一分钟最多能吃多少个汉堡？

小宇：快的话可能 2 个，不过正常应该最多就能吃完 1 个了。

闪客：好的，那我问你，刚刚这两个问题你为什么能不假思索地回答出来呢？

小宇：哈哈你这是什么话，我自己我当然了解了。

闪客：不，你仔细想想你回答这两个问题的逻辑。

小宇：哦我明白你的意思了，当你问我一天最多能吃多少个汉堡时，我考虑的是我的胃的容量最多能容下多少个汉堡。而当你问我一分钟最多能吃多少个汉堡时，我考虑的时我吃汉堡的速度，按照这个速度在一分钟内能吃多少。

闪客：没错，你总结得很好！一天最多吃多少个汉堡，此时时间非常充裕，所以主要是胃的容量限制了这个汉堡最大值，计算公式应该是：

最多汉堡数 = 胃的容量 ÷ 汉堡的体积

而一分钟最多吃多少个汉堡，此时胃的容量非常充裕，限制汉堡最大值的是时间因素，计算公式是：

最多汉堡数 = 一分钟 ÷ 吃一个汉堡的耗时

所以，取决于最先触达的那个限制条件。

而最大 TCP 连接数这个问题，假如面试被问到了，即使你完全不会，也应该有这样的思路。

而如果你有了这样的思路，你多多少少都能回答出让面试官满意的答案，因为计算机很多时候，更看重思路，而不是细枝末节。

你管这破玩意叫 IO 多路复用？

https://mp.weixin.qq.com/s/YdIdoZ_yusVWza1PU7lWaw

低并发编程

战略上藐视技术，战术上重视技术

为了讲多路复用，当然还是要跟风，采用鞭尸的思路，先讲讲传统的网络 IO 的弊端，用拉踩的方式捧起多路复用 IO 的优势。

为了方便理解，以下所有代码都是伪代码，知道其表达的意思即可。

Let’s go

阻塞 IO

服务端为了处理客户端的连接和请求的数据，写了如下代码。

listenfd = socket();   // 打开一个网络通信端口
bind(listenfd);        // 绑定
listen(listenfd);      // 监听
while(1) {
  connfd = accept(listenfd);  // 阻塞建立连接
  int n = read(connfd, buf);  // 阻塞读数据
  doSomeThing(buf);  // 利用读到的数据做些什么
  close(connfd);     // 关闭连接，循环等待下一个连接
}

这段代码会执行得磕磕绊绊，就像这样。

可以看到，服务端的线程阻塞在了两个地方，一个是 accept 函数，一个是 read 函数。

如果再把 read 函数的细节展开，我们会发现其阻塞在了两个阶段。

这就是传统的阻塞 IO。

整体流程如下图。

所以，如果这个连接的客户端一直不发数据，那么服务端线程将会一直阻塞在 read 函数上不返回，也无法接受其他客户端连接。

这肯定是不行的。

非阻塞 IO

为了解决上面的问题，其关键在于改造这个 read 函数。

有一种聪明的办法是，每次都创建一个新的进程或线程，去调用 read 函数，并做业务处理。

while(1) {
  connfd = accept(listenfd);  // 阻塞建立连接
  pthread_create（doWork);  // 创建一个新的线程
}
void doWork() {
  int n = read(connfd, buf);  // 阻塞读数据
  doSomeThing(buf);  // 利用读到的数据做些什么
  close(connfd);     // 关闭连接，循环等待下一个连接
}

这样，当给一个客户端建立好连接后，就可以立刻等待新的客户端连接，而不用阻塞在原客户端的 read 请求上。

不过，这不叫非阻塞 IO，只不过用了多线程的手段使得主线程没有卡在 read 函数上不往下走罢了。操作系统为我们提供的 read 函数仍然是阻塞的。

所以真正的非阻塞 IO，不能是通过我们用户层的小把戏，而是要恳请操作系统为我们提供一个非阻塞的 read 函数。

这个 read 函数的效果是，如果没有数据到达时（到达网卡并拷贝到了内核缓冲区），立刻返回一个错误值（-1），而不是阻塞地等待。

操作系统提供了这样的功能，只需要在调用 read 前，将文件描述符设置为非阻塞即可。

fcntl(connfd, F_SETFL, O_NONBLOCK);
int n = read(connfd, buffer) != SUCCESS);

这样，就需要用户线程循环调用 read，直到返回值不为 -1，再开始处理业务。

这里我们注意到一个细节。

非阻塞的 read，指的是在数据到达前，即数据还未到达网卡，或者到达网卡但还没有拷贝到内核缓冲区之前，这个阶段是非阻塞的。

当数据已到达内核缓冲区，此时调用 read 函数仍然是阻塞的，需要等待数据从内核缓冲区拷贝到用户缓冲区，才能返回。

整体流程如下图

IO 多路复用

为每个客户端创建一个线程，服务器端的线程资源很容易被耗光。

当然还有个聪明的办法，我们可以每 accept 一个客户端连接后，将这个文件描述符（connfd）放到一个数组里。

fdlist.add(connfd);

然后弄一个新的线程去不断遍历这个数组，调用每一个元素的非阻塞 read 方法。

while(1) {
  for(fd <-- fdlist) {
    if(read(fd) != -1) {
      doSomeThing();
    }
  }
}

这样，我们就成功用一个线程处理了多个客户端连接。

你是不是觉得这有些多路复用的意思？

但这和我们用多线程去将阻塞 IO 改造成看起来是非阻塞 IO 一样，这种遍历方式也只是我们用户自己想出的小把戏，每次遍历遇到 read 返回 -1 时仍然是一次浪费资源的系统调用。

在 while 循环里做系统调用，就好比你做分布式项目时在 while 里做 rpc 请求一样，是不划算的。

所以，还是得恳请操作系统老大，提供给我们一个有这样效果的函数，我们将一批文件描述符通过一次系统调用传给内核，由内核层去遍历，才能真正解决这个问题。

select

select 是操作系统提供的系统调用函数，通过它，我们可以把一个文件描述符的数组发给操作系统，让操作系统去遍历，确定哪个文件描述符可以读写，然后告诉我们去处理：

select系统调用的函数定义如下。

int select(
    int nfds,
    fd_set *readfds,
    fd_set *writefds,
    fd_set *exceptfds,
    struct timeval *timeout);
// nfds:监控的文件描述符集里最大文件描述符加1
// readfds：监控有读数据到达文件描述符集合，传入传出参数
// writefds：监控写数据到达文件描述符集合，传入传出参数
// exceptfds：监控异常发生达文件描述符集合, 传入传出参数
// timeout：定时阻塞监控时间，3种情况
//  1.NULL，永远等下去
//  2.设置timeval，等待固定时间
//  3.设置timeval里时间均为0，检查描述字后立即返回，轮询

服务端代码，这样来写。

首先一个线程不断接受客户端连接，并把 socket 文件描述符放到一个 list 里。

while(1) {
  connfd = accept(listenfd);
  fcntl(connfd, F_SETFL, O_NONBLOCK);
  fdlist.add(connfd);
}

然后，另一个线程不再自己遍历，而是调用 select，将这批文件描述符 list 交给操作系统去遍历。

while(1) {
  // 把一堆文件描述符 list 传给 select 函数
  // 有已就绪的文件描述符就返回，nready 表示有多少个就绪的
  nready = select(list);
  ...
}

不过，当 select 函数返回后，用户依然需要遍历刚刚提交给操作系统的 list。

只不过，操作系统会将准备就绪的文件描述符做上标识，用户层将不会再有无意义的系统调用开销。

while(1) {
  nready = select(list);
  // 用户层依然要遍历，只不过少了很多无效的系统调用
  for(fd <-- fdlist) {
    if(fd != -1) {
      // 只读已就绪的文件描述符
      read(fd, buf);
      // 总共只有 nready 个已就绪描述符，不用过多遍历
      if(--nready == 0) break;
    }
  }
}

正如刚刚的动图中所描述的，其直观效果如下。（同一个动图消耗了你两次流量，气不气？）

可以看出几个细节：

1. select 调用需要传入 fd 数组，需要拷贝一份到内核，高并发场景下这样的拷贝消耗的资源是惊人的。（可优化为不复制）

2. select 在内核层仍然是通过遍历的方式检查文件描述符的就绪状态，是个同步过程，只不过无系统调用切换上下文的开销。（内核层可优化为异步事件通知）

3. select 仅仅返回可读文件描述符的个数，具体哪个可读还是要用户自己遍历。（可优化为只返回给用户就绪的文件描述符，无需用户做无效的遍历）

整个 select 的流程图如下。

可以看到，这种方式，既做到了一个线程处理多个客户端连接（文件描述符），又减少了系统调用的开销（多个文件描述符只有一次 select 的系统调用 + n 次就绪状态的文件描述符的 read 系统调用）。

poll

poll 也是操作系统提供的系统调用函数。

int poll(struct pollfd *fds, nfds_tnfds, int timeout);

struct pollfd {
  intfd; /*文件描述符*/
  shortevents; /*监控的事件*/
  shortrevents; /*监控事件中满足条件返回的事件*/
};

它和 select 的主要区别就是，去掉了 select 只能监听 1024 个文件描述符的限制。

epoll

epoll 是最终的大 boss，它解决了 select 和 poll 的一些问题。

还记得上面说的 select 的三个细节么？

1. select 调用需要传入 fd 数组，需要拷贝一份到内核，高并发场景下这样的拷贝消耗的资源是惊人的。（可优化为不复制）

3. select 仅仅返回可读文件描述符的个数，具体哪个可读还是要用户自己遍历。（可优化为只返回给用户就绪的文件描述符，无需用户做无效的遍历）

所以 epoll 主要就是针对这三点进行了改进。

1. 内核中保存一份文件描述符集合，无需用户每次都重新传入，只需告诉内核修改的部分即可。

2. 内核不再通过轮询的方式找到就绪的文件描述符，而是通过异步 IO 事件唤醒。

3. 内核仅会将有 IO 事件的文件描述符返回给用户，用户也无需遍历整个文件描述符集合。

具体，操作系统提供了这三个函数。

第一步，创建一个 epoll 句柄

int epoll_create(int size);

第二步，向内核添加、修改或删除要监控的文件描述符。

int epoll_ctl(
  int epfd, int op, int fd, struct epoll_event *event);

第三步，类似发起了 select() 调用

int epoll_wait(
  int epfd, struct epoll_event *events, int max events, int timeout);

使用起来，其内部原理就像如下一般丝滑。

如果你想继续深入了解 epoll 的底层原理，推荐阅读飞哥的《图解 | 深入揭秘 epoll 是如何实现 IO 多路复用的！》，从 linux 源码级别，一行一行非常硬核地解读 epoll 的实现原理，且配有大量方便理解的图片，非常适合源码控的小伙伴阅读。

后记

大白话总结一下。

一切的开始，都起源于这个 read 函数是操作系统提供的，而且是阻塞的，我们叫它 阻塞 IO。

为了破这个局，程序员在用户态通过多线程来防止主线程卡死。

后来操作系统发现这个需求比较大，于是在操作系统层面提供了非阻塞的 read 函数，这样程序员就可以在一个线程内完成多个文件描述符的读取，这就是 非阻塞 IO。

但多个文件描述符的读取就需要遍历，当高并发场景越来越多时，用户态遍历的文件描述符也越来越多，相当于在 while 循环里进行了越来越多的系统调用。

后来操作系统又发现这个场景需求量较大，于是又在操作系统层面提供了这样的遍历文件描述符的机制，这就是 IO 多路复用。

多路复用有三个函数，最开始是 select，然后又发明了 poll 解决了 select 文件描述符的限制，然后又发明了 epoll 解决 select 的三个不足。

所以，IO 模型的演进，其实就是时代的变化，倒逼着操作系统将更多的功能加到自己的内核而已。

如果你建立了这样的思维，很容易发现网上的一些错误。

比如好多文章说，多路复用之所以效率高，是因为用一个线程就可以监控多个文件描述符。

这显然是知其然而不知其所以然，多路复用产生的效果，完全可以由用户态去遍历文件描述符并调用其非阻塞的 read 函数实现。而多路复用快的原因在于，操作系统提供了这样的系统调用，使得原来的 while 循环里多次系统调用，变成了一次系统调用 + 内核层遍历这些文件描述符。

就好比我们平时写业务代码，把原来 while 循环里调 http 接口进行批量，改成了让对方提供一个批量添加的 http 接口，然后我们一次 rpc 请求就完成了批量添加。

一个道理。

找时间我再专门写一篇，讲讲这块网络上鱼龙混杂的花式错误理解。

Understanding Linux CPU Load – when should you be worried?

copy from:https://scoutapm.com/blog/understanding-load-averages

You might be familiar with Linux load averages already. Load averages are the three numbers shown with the uptime and top commands – they look like this:

load average: 0.09, 0.05, 0.01

Most people have an inkling of what the load averages mean: the three numbers represent averages over progressively longer periods of time (one, five, and fifteen-minute averages), and that lower numbers are better. Higher numbers represent a problem or an overloaded machine. But, what’s the threshold? What constitutes “good” and “bad” load average values? When should you be concerned over a load average value, and when should you scramble to fix it ASAP?

First, a little background on what the load average values mean. We’ll start out with the simplest case: a machine with one single-core processor.

The traffic analogy

A single-core CPU is like a single lane of traffic. Imagine you are a bridge operator … sometimes your bridge is so busy there are cars lined up to cross. You want to let folks know how traffic is moving on your bridge. A decent metric would be how many cars are waiting at a particular time. If no cars are waiting, incoming drivers know they can drive across right away. If cars are backed up, drivers know they’re in for delays.

So, Bridge Operator, what numbering system are you going to use? How about:

0.00 means there’s no traffic on the bridge at all. In fact, between 0.00 and 1.00 means there’s no backup, and an arriving car will just go right on.
1.00 means the bridge is exactly at capacity. All is still good, but if traffic gets a little heavier, things are going to slow down.
over 1.00 means there’s backup. How much? Well, 2.00 means that there are two lanes worth of cars total — one lane’s worth on the bridge, and one lane’s worth waiting. 3.00 means there are three lanes worth total — one lane’s worth on the bridge, and two lanes’ worth waiting. Etc.

undefined

This is basically what CPU load is. “Cars” are processes using a slice of CPU time (“crossing the bridge”) or queued up to use the CPU. Unix refers to this as the run-queue length: the sum of the number of processes that are currently running plus the number that are waiting (queued) to run.

Like the bridge operator, you’d like your cars/processes to never be waiting. So, your CPU load should ideally stay below 1.00. Also, like the bridge operator, you are still ok if you get some temporary spikes above 1.00 … but when you’re consistently above 1.00, you need to worry.

So you’re saying the ideal load is 1.00?

Well, not exactly. The problem with a load of 1.00 is that you have no headroom. In practice, many sysadmins will draw a line at 0.70:

The “Need to Look into it” Rule of Thumb: 0.70 If your load average is staying above > 0.70, it’s time to investigate before things get worse.
The “Fix this now” Rule of Thumb: 1.00. If your load average stays above 1.00, find the problem and fix it now. Otherwise, you’re going to get woken up in the middle of the night, and it’s not going to be fun.
The “Arrgh, it’s 3 AM WTF?” Rule of Thumb: 5.0. If your load average is above 5.00, you could be in serious trouble, your box is either hanging or slowing way down, and this will (inexplicably) happen in the worst possible time like in the middle of the night or when you’re presenting at a conference. Don’t let it get there.

What about Multi-processors? My load says 3.00, but things are running fine!

Got a quad-processor system? It’s still healthy with a load of 3.00.

On a multi-processor system, the load is relative to the number of processor cores available. The “100% utilization” mark is 1.00 on a single-core system, 2.00, on a dual-core, 4.00 on a quad-core, etc.

If we go back to the bridge analogy, the “1.00” really means “one lane’s worth of traffic”. On a one-lane bridge, that means it’s filled up. On a two-lane bridge, a load of 1.00 means it’s at 50% capacity — only one lane is full, so there’s another whole lane that can be filled.

Same with CPUs: a load of 1.00 is 100% CPU utilization on a single-core box. On a dual-core box, a load of 2.00 is 100% CPU utilization.

Multicore vs. multiprocessor

While we’re on the topic, let’s talk about multicore vs. multiprocessor. For performance purposes, is a machine with a single dual-core processor basically equivalent to a machine with two processors with one core each? Yes. Roughly. There are lots of subtleties here concerning amount of cache, frequency of process hand-offs between processors, etc. Despite those finer points, for the purposes of sizing up the CPU load value, the total number of cores is what matters, regardless of how many physical processors those cores are spread across.

Which leads us to two new Rules of Thumb:

The “number of cores = max load” Rule of Thumb: on a multicore system, your load should not exceed the number of cores available.
The “cores is cores” Rule of Thumb: How the cores are spread out over CPUs doesn’t matter. Two quad-cores == four dual-cores == eight single-cores. It’s all eight cores for these purposes.

Bringing It Home

Let’s take a look at the load averages output from uptime:

~ $ uptime
23:05 up 14 days, 6:08, 7 users, load averages: 0.65 0.42 0.36

This is on a dual-core CPU, so we’ve got lots of headroom. I won’t even think about it until load gets and stays above 1.7 or so.

Now, what about those three numbers? 0.65 is the average over the last minute, 0.42 is the average over the last five minutes, and 0.36 is the average over the last 15 minutes. Which brings us to the question:

Which average should I be observing? One, five, or 15 minutes?

For the numbers we’ve talked about (1.00 = fix it now, etc), you should be looking at the five or 15-minute averages. Frankly, if your box spikes above 1.0 on the one-minute average, you’re still fine. It’s when the 15-minute average goes north of 1.0 and stays there that you need to snap to. (obviously, as we’ve learned, adjust these numbers to the number of processor cores your system has).

So # of cores is important to interpreting load averages … how do I know how many cores my system has?

cat /proc/cpuinfo to get info on each processor in your system. Note: not available on OSX, Google for alternatives. To get just a count, run it through grep and word count: grep 'model name' /proc/cpuinfo | wc -l

More servers? Or faster code?

Adding servers can be a band-aid for slow code. Scout APM helps you find and fix your inefficient and costly code. We automatically identify N+1 SQL calls, memory bloat, and other code-related issues so you can spend less time debugging and more time programming.

Ready to optimize your site? Sign up for a free trial.

差值哈希（DHash）

某些情况下，我们需要检测图片之间的相似性，进行我们需要的处理：删除同一张图片、标记盗版等。
如何判断是同一张图片呢？最简单的方法是使用加密哈希（例如MD5, SHA-1）判断。但是局限性非常大。例如一个txt文档，其MD5值是根据这个txt的二进制数据计算的，如果是这个txt文档的完全复制版，那他们的MD5值是完全相同的。但是，一旦改变副本的内容，哪怕只是副本的缩进格式，其MD5也会天差地别。因此加密哈希只能用于判断两个完全一致、未经修改的文件，如果是一张经过调色或者缩放的图片，根本无法判断其与另一张图片是否为同一张图片。
那么如何判断一张被PS过的图片是否与另一张图片本质上相同呢？比较简单、易用的解决方案是采用感知哈希算法（Perceptual Hash Algorithm)。

感知哈希算法是一类算法的总称，包括aHash、pHash、dHash。顾名思义，感知哈希不是以严格的方式计算Hash值，而是以更加相对的方式计算哈希值，因为“相似”与否，就是一种相对的判定。

aHash：平均值哈希。速度比较快，但是常常不太精确。
pHash：感知哈希。精确度比较高，但是速度方面较差一些。
dHash：差异值哈希。Amazing！精确度较高，且速度也非常快。因此我就选择了dHash作为我图片判重的算法。

一、相似图片检测步骤：

分别计算两张图片的dHash值
通过dHash值计算两张图片的汉明距离（Hamming Distance），通过汉明距离的大小，判断两张图片的相似程度。

二、dHash计算

需要计算dHash值的图片

Step1. 缩放图片

如果我们要计算上图的dHash值，第一步是把它缩放到足够小。为什么需要缩放呢？因为原图的分辨率一般都非常高。一张 200*200 的图片，就有整整4万个像素点，每一个像素点都保存着一个RGB值，4万个RGB，是相当庞大的信息量，非常多的细节需要处理。因此，我们需要把图片缩放到非常小，隐藏它的细节部分，只见森林，不见树木。建议缩放为9*8，虽然可以缩放为任意大小，但是这个值是相对合理的。而且宽度为9，有利于我们转换为hash值，往下面看，你就明白了。

resize_width = 9
resize_height = 8
# 1. resize to (9,8)
smaller_image = image.resize((resize_width, resize_height))

缩放为9*8分辨率后

Step2. 灰度化

dHash全名为差异值hash，通过计算相邻像素之间的颜色强度差异得出。我们缩放后的图片，细节已经被隐藏，信息量已经变少。但是还不够，因为它是彩色的，由RGB值组成。白色表示为（255,255,255）,黑色表示为（0,0,0），值越大颜色越亮，越小则越暗。每种颜色都由3个数值组成，也就是红、绿、蓝的值。如果直接使用RGB值对比颜色强度差异，相当复杂，因此我们转化为灰度值——只由一个0到255的整数表示灰度。这样的话就将三维的比较简化为了一维比较。

# 2. 灰度化 Grayscale
grayscale_image = smaller_image.convert("L")

灰度化后

Step3. 差异计算

差异值是通过计算每行相邻像素的强度对比得出的。我们的图片为9*8的分辨率，那么就有8行，每行9个像素。差异值是每行分别计算的，也就是第二行的第一个像素不会与第一行的任何像素比较。每一行有9个像素，那么就会产生8个差异值，这也是为何我们选择9作为宽度，因为8bit刚好可以组成一个byte，方便转换为16进制值。
如果前一个像素的颜色强度大于第二个像素，那么差异值就设置为True（也就是1），如果不大于第二个像素，就设置为False（也就是0）。

# 3. 比较相邻像素
pixels = list(grayscale_image.getdata())
difference = []
for row in range(resize_height):
row_start_index = row * resize_width
for col in range(resize_width - 1):
left_pixel_index = row_start_index + col
difference.append(pixels[left_pixel_index] > pixels[left_pixel_index + 1])

Step4. 转换为hash值

我们将差异值数组中每一个值看做一个bit，每8个bit组成为一个16进制值，将16进制值连接起来转换为字符串，就得出了最后的dHash值。

# 转化为16进制(每个差值为一个bit,每8bit转为一个16进制)
decimal_value = 0
hash_string = ""
for index, value in enumerate(difference):
if value: # value为0, 不用计算, 程序优化
decimal_value += value * (2 ** (index % 8))
if index % 8 == 7: # 每8位的结束
hash_string += str(hex(decimal_value)[2:].rjust(2, "0")) # 不足2位以0填充。0xf=>0x0f
decimal_value = 0

三、计算汉明距离（Hamming Distance）

汉明距离这个概念不止运用于图片对比领域，也被使用于众多领域，具体的介绍可以参见Wikipedia。
汉明距离表示将A修改成为B，需要多少个步骤。比如字符串“abc”与“ab3”，汉明距离为1，因为只需要修改“c”为“3”即可。
dHash中的汉明距离是通过计算差异值的修改位数。我们的差异值是用0、1表示的，可以看做二进制。二进制0110与1111的汉明距离为2。
我们将两张图片的dHash值转换为二进制difference，并取异或。计算异或结果的“1”的位数，也就是不相同的位数，这就是汉明距离。

difference = (int(dhash1, 16)) ^ (int(dhash2, 16))
return bin(difference).count("1")

如果传入的参数不是两张图的dHash值，而是直接比较两张图片，那么不需要生成dHash值，直接用Step3中的difference数组，统计不相同的位数，就是汉明距离。

hamming_distance = 0
for index, img1_pix in enumerate(image1_difference):
img2_pix = image2_difference[index]
if img1_pix != img2_pix:
hamming_distance += 1

一般来说，汉明距离小于5，基本就是同一张图片。大家可以根据自己的实际情况，判断汉明距离临界值为多少。

Github：

https://github.com/hjaurum/DHash

参考文档：

对simhash的简单理解

-1为什么这么长

我整理这个文档的最初目的是将simhash的基本原理搞清楚，这个初心在学习的过程中逐渐改变了。

在整理和学习simhash相关资料的过程中，我不理解simhash得到的文本特征有效性的来源，于是开始了解simhash所属的局部敏感哈希，尝试找到解释。从论文和大家的博客来看，随机投影hash和随机超平面hash局部敏感哈希的经典形式。于是，我盯着这两个“随机”朋友看了很久。当了解到随机投影是一种数据降维方法的时候，我终于相信这两个hash算法区别不是特别大。

为了记录simhash相关知识内容，也为了记录自己在知识地图中搜索的过程，我搞了一个新花样——大杂烩。新花样总的来说会让人的大脑分泌一些带来快乐的东西，然后露出如图-1-1的表情。这也是强化自己的学习动力的一种方式。

本文的目录如图-1-2。

0引言

21世纪不是生物的世纪，而是数据的世纪。数据已经成为我们这个文明必不可少的一部分，不管走到哪里，我们都沐浴在数据形成的空气中。现在，这种空气有点太多，大家快要氧中毒了——互联网、工业生产等领域产生的数据太多，我们在管理和使用这些数据时遇到了几种困难：高维度、极大的数量、重复问题。我们需要使用包括simhash在内的算法来解决这些问题。

0.1我要降维

随着采集能力和存储能力的强大，我们得了贪食症，不管一个字段是否有用，先存起来再说。总的来说，字段越多，我们可以构造的特征就越多、可以输入模型的信息就越多。不过呢，特征多是有代价的，它会降低模型的训练和计算速度。但是，我比较贪心，就是要马儿不吃草、还跑得快：在特征数量较小的情况下，尽量多地向模型提供信息。

那只能降维了。

0.2我要搜索

采集和存储能力的强大，也让我们的数据积累了海量的文档、“啥都有”。但是，如果没有较强的检索能力，“海量数据”就是“啥都找不到”“啥都没有”的代名词。

我们需要强有力的搜索技术。

0.3我需要去重

很多情况下，我们需要对文本数据进行去重：当文本分类语料有重复的样本；有些网站会将同一片文章重复发若干次，导致我们采集到大量重复的内容，进而影响后续热点检测等任务的效果；等等。

假如有10篇文档需要去重，我可以亲自上、手工排重。这个任务几十秒钟就完成了。

假如有10000篇文档需要去重，可以使用适当的相似度算法判断是否重复，然后用single-pass的框架对文档进行聚类，最后保留所有簇的中心文档即可。这种算法最多需要计算大约（1+9999）*10000/2次相似度，耗时会很久。当然了，我们可以用一个倒排索引来加速。

假如我们有100000000篇文档需要去重，按我以前的套路，就是用Spark这样的工具咔咔算，算到天荒地老。不过呢，如果我们使用合适的文本相似度算法和倒排索引的构建方法，用一台内存足够的机器，可以在有生之年完成这个任务。

我需要一个高效的文本去重算法。

0.4我要局部敏感哈希

前面所说的几个需求，我们可以用很多方法来满足。可选的方案中，有一朵奇葩，那就是局部敏感哈希(Local Sensitive Hash)。LSH的思想是，在保留数据相对位置的条件下，将原始数据映射到一个碰撞率较高的低维的新空间里，从而降低下游任务的计算量。利用局部敏感哈希编码的高碰撞率，我们可以设计出更加稀疏的倒查索引键值，从而得到非常高效的文本去重方案，即基于simhash的文本去重方法。

如图0-1，是我在整理simhash相关的内容时，探索出来的知识地图，算是本文的另一种目录。

1从基于随机投影的数据降维说起

1.1向量点积的含义

随机投影的基础方法，是向量点积运算。而理解随机投影的基础，是理解向量点积运算的含义。如图1-1，二维平面中有两个向量

和

。二者的点积为:

一般来说，我们会把向量点积理解为，计算向量夹角时的中间结果。

这里，为了帮助理解随机投影，需要重新解释一下。向量点积表示的是，向量

在向量

法平面上投影长度的加权值，其中权重为

的长度(当然由于乘法可交换，这里两个向量可以互换)。得到的投影向量为:

如果我们将

看做一个新空间的坐标轴，那么，在新的空间中，点A的坐标就是

这样，我们就用向量

完成了对点A的映射。

举个例子，假设两个向量:

那么a.b=7*1+3*(-1)=4。点A以

向量所在直线为坐标轴的空间中，坐标是4。

注意，经过这通操作，点A(在新空间中)的坐标由2维降到了1维。

1.2基于随机投影的降维——2维到1维

Johnson–Lindenstrauss引理指出，在欧式空间中的若干点，经过相同的映射后进入新的空间，它们仍然会保持原来的相对位置。简单来说，“相对位置”指的是一些点相距较近，一些点相距较远。这里只从直觉上展示随机投影“保留数据相对位置”的性质。具体的证明暂时就免了。

假设二维平面中，有若干点A=(7,3), C=(-0.5,-1.5),D=(9,2),E=(-0.5,2.5)。目测，A和D离得比较近；C和E里的比较近。

我们使用向量

，将这4个点映射到新的空间，坐标分别是A1=4，C1=1,D1=7,E1=-3。A1和D1里的比较近；C1和E1离得比较近；当然了，C1和D1也挺近的。这样，二维坐标系里的4个点，被映射到了一个1维空间中，还在一定程度上保留了原来的相对位置。

那么，

是怎么来的呢？随机生成。我们可以基于高斯分布，生成B点的横坐标和纵坐标。为啥是高斯分布呢？有一定的原因，这里暂时无力讲述。

这可省事了，我们在原始数据所属的空间中，随机生成一个向量，就可以基于这个向量，将原始数据映射到一个1维空间中。不过呢，在新空间中，数据点之间的相对距离存在一定程度的失真，怎么办呢？

1.3随机投影的降维——N维到K维

假设有M条数据，维度非常高，为N。随机投影法将帮我们把这种数据压缩为K维(K远小于N)。

将原始数据看做高维空间中的一个点。那么对应第m条数据，有一个向量

，从原点出发到这个数据点。

我们随机生成K(K远小于N)个长度为N的一维向量

，将原始数据映射到以这些随机向量所在直线为坐标轴的新空间中，得到点

。这种降维方法叫做“随机投影法”。总的来说，K越大，降维后的数据，保留的信息越多，数据之间的相对位置越“保真”——可以证明，但是这里无力搞了。

1.4随机投影法降维的python实现

github地址：

https://github.com/lipengyuer/DataScience/blob/master/src/algoritm/RandomProjectionDimReduction.pygithub.com

2随机投影与局部敏感哈希

2.1随机投影降维的简化——基于随机投影的局部敏感哈希

在1.3中提到，随机投影法可以把高维数据映射到新的空间中。由于特征维度大大降低了，聚类、分类、搜索等任务的计算量也大大降低了。不过呢，人心不足蛇吞象，我还想进一步降低计算量。

新的空间里，坐标轴还是实数轴，降维后的特征是连续特征。有人认为，这样的话还得用float这种类型存储数据、还得进行float*float的操作，浪费。有些高手本着如图2-1的原则，对随机投影降维进行了改进。

在将数据映射到新空间后，我们将落在坐标轴负轴的维度(该维度取值为负数)，统一赋值为0，表示数据与对应随机向量夹角大于90度。或者说，数据点与随机向量，在以后者为法向量、过原点的超平面的同侧。类似的，我们将落在坐标轴非负轴的维度，统一赋值为1。这样原始数据就被映射到了一个离散的新空间里。

这里所述的数据映射方法，就是我们常说的基于随机投影的局部敏感哈希。局部敏感哈希，与常见的hash有啥关系呢？局部敏感哈希是hash算法的一种，是数据映射方法，通常被用来对数据进行降维。

2.2黑白分明的hash

一般来说，我们遇到的数据长度n是可变的。我们可以用hash函数，将数据映射为一个长度固定为K(K远小于n)的编码。Hash函数的输出，是对原始数据的一种压缩表示，也叫做数字签名、数字指纹、消息摘要或者散列值。常见的hash算法非常严格，要求碰撞率尽量低，即每条数据拥有一个唯一的id。

从hash的原理来看，内容相同的文档，具有相同的哈希码；内容略有不同的文档，对应的哈希码会有很大的不同。如表2-1，是一些句子的hash值。其中句子1和3的哈希码相等；句子1和句子4只差了一个字，哈希码具有肉眼可见的巨大差异。

Hash码可以用来判断两个字符串是否相等。这样做有什么意义呢？我们把文档的哈希码存储起来，当需要判断两篇文档是否相等时，直接判断二者的哈希码即可。如果文档比较长(几百字)，而哈希码比较短(几十位)，那么后者的相等判断是比较快的。如果说，我们用位运算来进行哈希码的相等判断，那就更快了。因此，基于哈希码来判断文档内容是否相同，在一些场景里是非常高效的方案。

表2-1 句子们和它们的hash编码

在信息检索任务中，我们可以为每一条记录生成一个hash码、作为id，这样就可以为一篇文档快速地找到相关的字段了。然而，假如需要检索的是相似的文档，普通的hash算法就没办法了。这时候，我们需要不太严格的hash编码方法。

2.3随机投影hash的用途

局部敏感哈希是非常适合文本数据检索场景的编码方法。局部敏感哈希在随机投影降维方法的基础上，增加了离散化环节。这个“离散”有啥用呢？

直观地看，原来空间中的-0.66和-100，在新空间都成为1或者0,也就是说，二者在新的空间中是相等的。这样的结果是，在原来空间中比较接近的数据点，在新的空间中，在一些维度上可能是相等的。

基于取值相同的维度，我们可以把数据分组(俗称分到桶里)。在搜索文档的时候，我们对查询语句进行hash，然后把各个维度上、桶的编号相同的文档召回，最后进行精排，可以实现快速而高质量的搜索。一个基于分桶构建的倒查索引可以帮助我们实现这样的操作。

一些在原来空间接近的数据点，经过这样的映射后，仍然相似甚至相等(各个维度坐标都相等)。对二进制编码进行相似度计算是非常快速的，在这个基础上我们可以进行非常快速的聚类。

另外，我们可以把映射后相等的数据看做是相同的数据，进而进行排重。

2.4随机超平面hash

随机超平面hash是在随机投影hash的基础上发展而来的。二者的名称含义相近，就像算法内容一样。与随机投影hash的主要区别是，随机超平面hash的编码结果是-1和1组成的串——与随机向量点积为负数，新空间中该维度取值-1；与随机向量点积为非负数，新空间中该维度取值为1。

由于使用了新空间中所有象限，随机超平面hash的性能更好一些，在文本分类、聚类任务中表现更好。

2.5两种局部敏感哈希的python实现

GitHub地址:

https://github.com/lipengyuer/DataScience/blob/master/src/nlp/LSH/RandomProjectionLSH.pygithub.com

https://github.com/lipengyuer/DataScience/blob/master/src/nlp/LSH/RandomHyperplaneLSH.pygithub.com

3局部敏感哈希的杰出代表：simhash

“hash”是我们经常使用的一种对数据的映射操作，它会把特定类型的数据(如字符串)映射为另一种数据(比如内存地址)。“simhash”是一种将文本数据映射为固定长度的二进制编码的算法。当然了，由于基于simhash的文本相似度计算方法、文本去重方法名气比较大，大家经常以“simhash”代指“基于simhash编码的文本相似度计算方法”或者“基于simhash编码表示的文本去重方法”。这样混乱的称呼，特别容易引起混淆，因此这里约定几个提法：（1）simhash是一种将文本数据映射为定长二进制编码的hash算法，用NLP的说法就是一种文本表示模型；（2）基于simhash的文本相似度计算，就是用文本的simhash值作为特征向量，来计算文档之间的相似度或者距离；（3）基于simhash的文本去重，就是使用基于simhash表示来计算文本相似度，进而发现重复文档并删除。

3.1历史选择了simhash

在文本分类、聚类、相似度计算等等任务中，我们希望用一个定长的数值向量表示文本。这样我们才能用欧氏距离等方法计算文本的相似度。常见的文本表示模型有TF(Term Frequency)、TF-IDF（Term Frequency-Inverse Document Frequency）、句向量等等。

在海量文本去重场景下，上述几种模型都有一些不足:

（1）TF精度较差,即对“非常相似”到“相同”这个相似度范围的判断不是很敏感；受文本长度等因素影响较大，相似度阈值定起来比较麻烦。

(2)精度也比较差； TF-IDF要求首先遍历一遍所有文本来的得到IDF，计算量比较大；

(3)句向量主要关注的是语义，对字面的相似不太擅长；计算量比较大。

而simhash克服了以上几种算法的不足。

3.2从文本的词向量空间模型到simhash

在词向量空间模型中，我们把词语映射为一个独热编码(one-hot encoding)。假设词汇表为(我，是，中国人，农民，儿子)，大小为5，那么这几个词语的独热编码如表3-1。将文本分词后，把词语的独热编码按位累加，就得到了TF向量。比如“我是一个码农，是农民的儿子”，分词后得到“我/是/一个/码农/，/是/农民/的/儿子”，基于词语编码表，得到的TF向量就是(1,2,0,1,1)。

表3-1 词语的独热编码

高维度是TF的主要缺点。一般来说，我们的词汇是数以万计的，TF向量会比较长，导致下游任务计算量比较大。比如计算两篇文本的欧氏距离，我们需要执行数万次的减法、平方、加法等。

为此，Simhash从词语编码的降维入手，实现了对TF的降维。

3.3simhash的计算过程

Simhash是如何将文本映射为数值向量的呢？

首先，它基于hash算法将词语映射为较短的编码，然后使用随机超平面hash的做法得到最终的词语编码。然后，就像TF的计算一样，将每个词语的编码加起来。最后，采用随机超平面的离散化方法，得到文本的最终表示。

假设我们需要把S=“我爱北京天安门”这句话转换成长度为5的二进制编码。

3.3.1分词

按照一定的粒度切分文本，比如分词。S可以切分为”我/爱/北京/天安门”.

3.3.2将词语映射为定长二进制编码

将文本的每一个碎片，用一种hash算法映射为一定长度的二进制编码。如表3-2，是我假想的几个词语的编码值。

表3-2 S的词语的hash值

3.3.3将词语的二进制编码再转换一下

我们需要把词语二进制编码中的“0”一律转换为“-1”，得到词语的最终编码，如表3-3。将0转换为-1的目的，是将映射后的词语放置在整个空间中，而不是某一个象限，这样可以让数据点分布得更均匀一点。

注意，TF里，每个词语的权重比较粗暴，如果想升级一下，可以考虑TF-IDF。

与随机超平面hash相比，这里使用了一个“不随机”的超平面，将空间进行了分割。

表3-3 S的词语的新编码

3.3.4计算文档的初级编码

我们将句子中所有词语的编码加起来，就得到了句子的编码（0,0,0,2,2）。

3.3.5计算文档的最终编码

将句子编码的非正数元素转换为0，正数元素转换为1，就得到了句子的最终编码(0,0,0,1,1)——这就是句子的simhash编码。

3.4基于simhash编码计算文本距离

Simhash完成了文本的低纬度表示，接下来我们就可以进行文本相似度、文本分类等任务了。这里以文本相似度计算为例，展示simhash码的使用方式。

3.4.1海明距离

海明距离是simhash的经典搭档，用来在simhash码的基础上度量文本之间的距离或相似度。假设有两个等长（长度为K）的数据串：

二者的海明距离等于:

其中

假设文档A和文档B的simhash码分别为(1,1,0,1)和(1,0,0,1)，那么二者的海明距离就是0+1+0+0=1（感谢

victor diaowww.zhihu.com

的提醒，之前这里是”0+1+1+0=2″，是一个错误）。

海明距离的特点是，在实际应用中，只需要进行基本数据类型的相等判断和加法，计算速度非常快。

3.4.2用位运算对simhash升级

Simhash码是二进制编码，可以使用位运算来实现一些快速的操作。这是simhash高性能的一个重要来源。

3.5基于simhash计算文本距离的python实现

github地址是:

https://github.com/lipengyuer/DataScience/blob/master/src/nlp/LSH/simhash_v1.pygithub.com

https://github.com/lipengyuer/DataScience/blob/master/src/nlp/LSH/simhash_v2.pygithub.com

4基于simhash的文本去重框架

基于simhash的海量文本去重框架里同时涉及了搜索和聚类的关键技术，可以快速地修改为搜索和聚类工具。因此，这里用一个基于simhash 的文本去重框架展示simhash的应用方式。

假设我们需要对M篇文档进行去重。

4.1比较暴力的去重框架

最简单的方式，是计算每两篇文档之间的距离，然后对距离不超过3的文档对进行去重处理。这样的话，我们需要计算(M-1+0)*M/2词相似度，计算量非常大。

4.2使用倒查索引优化去重框架

我们可以使用倒查索引来降低计算量。以64位simhash编码表示的数据集为例，我们可以构建64个倒查索引，对应simhash码的64个维度；每个倒查索引只有两个key，即0和1，表示文本编码在这个维度上的取值；这样，我们就可以把所有的文档，按照simhash编码在各维度上的取值，放到各个倒查索引中。

在实际去重的时候，每遍历到一个不重复的文档，就把它添加到64个倒查索引中。

在考察一篇文档是否重复的时候，我们首先把64个倒查索引中，与当前文档编码匹配的部分召回，然后比对当前文档与召回文档的相似度，进而判断是否重复。这种查询方式比4.1所述的方式，需要比对的次数要少很多。

当然，这种倒查索引的key还是比较稠密，每次查询会召回比较多的文档。

4.3基于抽屉原理升级倒查索引

我们可以设计更稀疏的key，来获得更高的查询精度，进而进一步减少召回的文档数量。

4.3.1抽屉原理

我们可以用抽屉原理来对去重框架进行升级。

如图4-1，有3个抽屉、4个苹果。将4个苹果放到抽屉里，那么至少一个抽屉里，有2个苹果。当我们有X个抽屉、X+1个苹果，可以得到同样的结论，至少有一个抽屉里有2个苹果。这就是抽屉原理。

一般来说文本重复与否海明距离阈值是3，当两篇文档被判定相似，那么二者的simhash码最多有3个位置是不相等的(感谢

AndrewFuwww.zhihu.com

的提醒，原来是“相等”，现已改正)。换句话说，如果两篇文档的simhash 编码的海明距离小于等于3，我们认为二者是相似的。假设我们的simhash编码是64位，可以分为4组连续的数字。那么两篇相似文档的simhash编码中，至少有一个子串是完全相等的。换句话说，只有包含了文档A的4个子串中的一个的文档，才有可能与A相似。

4.3.2更稀疏的key

我们可以把simhash码切分为4个(数字可以变化)连续的子串，然后以子串为key取构建倒排索引。这时候，倒查索引的数量降到了4个。每个字串是一个16位的二进制编码，命中的文档数量相比4.2所述key更少。结果就是，查询的时候，召回的文档数量更少了。

4.4完整的去重框架

如图4-2和图4-3，分别是向倒查索引添加文档，和召回文本并排重的框架。

4.5文本去重框架的python实现