willwcw – 第3页 – 王春伟的技术博客

你管这破玩意叫 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实现

github地址是:

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

5结语

Simhash的背后是局部敏感哈希；基于simhash的文本去重技术背后，是基于局部敏感哈希的海量数据检索技术。

simhash也可以看做是一种文本你的分布式表示方法。难得的是，这种方法是无监督的。当然了，simhash挖掘文本信息的能力没有word2vec这种模型强，simhash编码会限制分类、聚类模型的效果上限。一般来说，在低精度、高速度的场景下，可以试一下simhash。

这里对局部敏感哈希的理解方式，具有较强的个人风格，不一定适合所有的人。如果看不懂，那是我的表达方式导致的。可以参考这里的知识地图搜索套路，整理出属于自己的表达。

nginx负载均衡一则


#user nobody;
worker_processes 2;
events {
# 最大并发数
worker_connections 1024;
}
http{
# 待选服务器列表
upstream list{
#ip_hash;
server 172.17.30.1 fail_timeout=60s;
server 172.17.30.2;
server 172.17.30.3;
}

log_format main '$remote_addr - $remote_user [$time_local] &amp;quot;$request&amp;quot; '
'$status $body_bytes_sent &amp;quot;$http_referer&amp;quot; '
'&amp;quot;$http_user_agent&amp;quot; &amp;quot;$http_x_forwarded_for&amp;quot;'
'$upstream_addr '
'ups_resp_time: $upstream_response_time '
'request_time: $request_time';
#access_log logs/access.log main;
access_log /var/log/nginx/access.log main;

server{
# 监听端口
listen 80;
# 根目录下
location / {
# 选择哪个服务器列表
proxy_set_header X-Real-IP $remote_addr;
proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
proxy_set_header host $host;
proxy_pass http://list;
}

}

server{
# 监听端口
listen 443 ssl;
add_header X-Frame-Options SAMEORIGIN;
ssl_certificate cert/test.pem;
ssl_certificate_key cert/test.key;
ssl_session_timeout 5m;
ssl_ciphers ECDHE-RSA-AES128-GCM-SHA256:ECDHE:ECDH:AES:HIGH:!NULL:!aNULL:!MD5:!ADH:!RC4;
ssl_protocols TLSv1 TLSv1.1 TLSv1.2;
ssl_prefer_server_ciphers on;
# 根目录下
location / {
# 选择哪个服务器列表
proxy_set_header X-Real-IP $remote_addr;
proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
proxy_set_header host $host;
proxy_pass http://list;
}


}

Elasticsearch 7.X 安装并使用

ES 7目前安装相当简单，这里简单记录下步骤。

1，https://www.elastic.co/cn/downloads/elasticsearch 官网按照版本下载安装包，比如 LINUX X86_64 sha asc

2，解压后基本可以直接使用，但是这里需要简单配置下

vim elasticsearch.yml

开启network,path,cluster.nam node.name相关配置

3，启动/bin/elasticsearch

二同步数据

这里需要将历史数据同步，采用

https://github.com/elasticsearch-dump/elasticsearch-dump

即可，不过需要更新最新的nodejs，

npm i -g n

n latest

然后同步数据即可！

c++编译参数

代码文件
hello.h


#include <stdio.h>
#include <stdlib.h>

void hello();
void main();

hello.c


#include "hello.h"
void hello()
{
printf("this is in hello...\n");
}

void main()
{

printf("main \n");
}

一简单编译

gcc hello.c -o hello
直接经过了预处理、编译、汇编和链接

二分步拆解
1，预处理
gcc -E hello.c -o hello.i

预处理结果就是将stdio.h 文件中的内容插入到hello.c中了

2,编译
gcc -S hello.i -o hello.s
gcc的-S选项，表示在程序编译期间，在生成汇编代码后，停止，-o输出汇编代码文件。

3,汇编
gcc -c hello.s -o hello.o

4,链接
gcc hello.o -o test
gcc连接器是gas提供的，负责将程序的目标文件与所需的所有附加的目标文件连接起来，最终生成可执行文件。附加的目标文件包括静态连接库和动态连接库
三库文件链接

去掉原始文件main相关内容


#include "hello.h"
int main()
{
hello();
return 0;
}

1，生成库文件
gcc hello.c -shared -fPIC -o libhello.so
-shared选项说明编译成的文件为动态链接库，不使用该选项相当于可执行文件
-fPIC 表示编译为位置独立的代码，不用此选项的话编译后的代码是位置相关的。所以动态载入时是通过代码拷贝的方式来满足不同进程的需要，而不能达到真正代码段共享的目的
2,
gcc hello_b.c -L ./ -l hello -o hello
其中-L ./ 表示链接的文件在当前目录下
-lhello 代表链接的文件名 gcc会自动为其前面添加lib，在其后边添加.so 即libhello.so
3,设置lib库文件地址
export LD_LIBRARY_PATH=/home/work/code/gcc/:$LD_LIBRARY_PATH

scp免密码操作

在一些脚本中scp需要免密操作，这就需要机器通过rsa进行相互授权。

一，client端

1）生成密钥：ssh-keygen -t rsa

2）拷贝密钥 cat ~/.ssh/id_rsa.pub

二，server端

将刚刚拷贝的密钥直接放在~/.ssh/authorized_keys 即可，这样client端访问server就需要密码了，非常简单

VARCHAR(M)最多能存储的数据

我们知道对于VARCHAR(M)类型的列最多可以占用65535个字节。其中的M代表该类型最多存储的字符数量，如果我们使用ascii字符集的话，一个字符就代表一个字节，我们看看VARCHAR(65535)是否可用: mysql> CREATE TABLE varchar_size_demo(

-> c VARCHAR(65535)

-> ) CHARSET=ascii ROW_FORMAT=Compact;
ERROR 1118 (42000): Row size too large. The maximum row size for the used table type, not counting BLOBs, is 65535. This includes storage overhead, check the manual. You have to change som mysql>

从报错信息里可以看出，MySQL对一条记录占用的最大存储空间是有限制的，除了BLOB或者TEXT类型的列之外，其他所有的列(不包括隐藏列和记录头信息)占用的字节长度加起来不能超过65535个字节。所以MySQL服务器建议我们把存储类型改为TEXT或者BLOB的类型。这个65535个字节除了列本身的数据之外，还包括一些其他的数据(storage overhead)，比如说我们为了存储一个VARCHAR(M)类型的列，其实需要占用3部分存储空间:

真实数据
真实数据占用字节的长度
NULL值标识，如果该列有NOT NULL属性则可以没有这部分存储空间

如果该VARCHAR类型的列没有NOT NULL属性，那最多只能存储65532个字节的数据，因为真实数据的长度可能占用2个字节，NULL值标识需要占用1个字节:

CREATE TABLE varchar_size_demo( c VARCHAR(65532)

) CHARSET=ascii ROW_FORMAT=Compact; Query OK, 0 rows affected (0.02 sec)

如果VARCHAR类型的列有NOT NULL属性，那最多只能存储65533个字节的数据，因为真实数据的长度可能占用2个字节，不需要NULL值标识:

mysql> DROP TABLE varchar_size_demo; Query OK, 0 rows affected (0.01 sec)

CREATE TABLE varchar_size_demo( c VARCHAR(65533) NOT NULL

) CHARSET=ascii ROW_FORMAT=Compact; Query OK, 0 rows affected (0.02 sec)

如果VARCHAR(M)类型的列使用的不是ascii字符集，那会怎么样呢?来看一下:

mysql> DROP TABLE varchar_size_demo; Query OK, 0 rows affected (0.00 sec)

CREATE TABLE varchar_size_demo( c VARCHAR(65532)

) CHARSET=gbk ROW_FORMAT=Compact;
ERROR 1074 (42000): Column length too big for column ‘c’ (max = 32767); use BLOB or TEXT instead

CREATE TABLE varchar_size_demo( c VARCHAR(65532)

) CHARSET=utf8 ROW_FORMAT=Compact;
ERROR 1074 (42000): Column length too big for column ‘c’ (max = 21845); use BLOB or TEXT instead

从执行结果中可以看出，如果VARCHAR(M)类型的列使用的不是ascii字符集，那M的最大取值取决于该字符集表示一个字符最多需要的字节数。在列的值允许为NULL的情况下，gbk字符集表示一个字符最多需要2个字节，那在该字符集下，M的最大取值就是32766(也就是:65532/2)，也就是说最多能存储32766个字符;utf8字符集表示一个字符最多需要3个字节，那在该字符集下，M的最大取值就是21844，就是说最多能存储21844(也就是:65532/3)个字符。

小贴士: 上述所言在列的值允许为NULL的情况下，gbk字符集下M的最大取值就是32766，utf8字符集下M的最大取值就是21844，这都是在表中只有一个字段的情况下说的，一定要记住一个行中的所有列(不包括隐藏列和记录头信息)占用的字节长度加起来不能超过65535个字节!

Elasticsearch 如何做到快速检索 – 倒排索引的秘密

“All problems in computer science can be solved by another level of indirection.”

– David J. Wheeler

“计算机世界就是 trade-off 的艺术”

摘抄了一篇比较好的，上面图和方法在很多博客都被引用，但是相对组织的较好。

一、前言

最近接触的几个项目都使用到了 Elasticsearch (以下简称 ES ) 来存储数据和对数据进行搜索分析，就对 ES 进行了一些学习。本文整理自我自己的一次技术分享。

本文不会关注 ES 里面的分布式技术、相关 API 的使用，而是专注分享下 ”ES 如何快速检索“ 这个主题上面。这个也是我在学习之前对 ES 最感兴趣的部分。

本文大致包括以下内容：

关于搜索
- 传统关系型数据库和 ES 的差别
- 搜索引擎原理
细究倒排索引
- 倒排索引具体是个什么样子的（posting list -> term dic -> term index）
- 关于 postings list 的一些巧技（FOR、Roaring Bitmaps）
- 如何快速做联合查询？

二、关于搜索

先设想一个关于搜索的场景，假设我们要搜索一首诗句内容中带“前”字的古诗，

用传统关系型数据库和 ES 实现会有什么差别？

如果用像 MySQL 这样的 RDBMS 来存储古诗的话，我们应该会去使用这样的 SQL 去查询

select name from poems where content like "%前%";
复制代码

这种我们称为顺序扫描法，需要遍历所有的记录进行匹配。

不但效率低，而且不符合我们搜索时的期望，比如我们在搜索“ABCD”这样的关键词时，通常还希望看到”A”,”AB”,”CD”,“ABC”的搜索结果。

于是乎就有了专业的搜索引擎，比如我们今天的主角 — ES。

搜索引擎原理

搜索引擎的搜索原理简单概括的话可以分为这么几步，

内容爬取，停顿词过滤

比如一些无用的像”的”，“了”之类的语气词/连接词
内容分词，提取关键词
根据关键词建立倒排索引
用户输入关键词进行搜索

这里我们就引出了一个概念，也是我们今天的要剖析的重点 – 倒排索引。也是 ES 的核心知识点。

如果你了解 ES 应该知道，ES 可以说是对 Lucene 的一个封装，里面关于倒排索引的实现就是通过 lucene 这个 jar 包提供的 API 实现的，所以下面讲的关于倒排索引的内容实际上都是 lucene 里面的内容。

三、倒排索引

首先我们还不能忘了我们之前提的搜索需求，先看下建立倒排索引之后，我们上述的查询需求会变成什么样子，

这样我们一输入“前”，借助倒排索引就可以直接定位到符合查询条件的古诗。

当然这只是一个很大白话的形式来描述倒排索引的简要工作原理。在 ES 中，这个倒排索引是具体是个什么样的，怎么存储的等等，这些才是倒排索引的精华内容。

1. 几个概念

在进入下文之前，先描述几个前置概念。

term

关键词这个东西是我自己的讲法，在 ES 中，关键词被称为 term。

postings list

还是用上面的例子，{静夜思, 望庐山瀑布}是 “前” 这个 term 所对应列表。在 ES 中，这些被描述为所有包含特定 term 文档的 id 的集合。由于整型数字 integer 可以被高效压缩的特质，integer 是最适合放在 postings list 作为文档的唯一标识的，ES 会对这些存入的文档进行处理，转化成一个唯一的整型 id。

再说下这个 id 的范围，在存储数据的时候，在每一个 shard 里面，ES 会将数据存入不同的 segment，这是一个比 shard 更小的分片单位，这些 segment 会定期合并。在每一个 segment 里面都会保存最多 2^31 个文档，每个文档被分配一个唯一的 id，从0到(2^31)-1。

相关的名词都是 ES 官方文档给的描述，后面参考材料中都可以找到出处。

2. 索引内部结构

上面所描述的倒排索引，仅仅是一个很粗糙的模型。真的要在实际生产中使用，当然还差的很远。

在实际生产场景中，比如 ES 最常用的日志分析，日志内容进行分词之后，可以得到多少的 term？

那么如何快速的在海量 term 中查询到对应的 term 呢？遍历一遍显然是不现实的。

term dictionary

于是乎就有了 term dictionary，ES 为了能快速查找到 term，将所有的 term 排了一个序，二分法查找。是不是感觉有点眼熟，这不就是 MySQL 的索引方式的，直接用 B+树建立索引词典指向被索引的数据。

term index

但是问题又来了，你觉得 Term Dictionary 应该放在哪里？肯定是放在内存里面吧？磁盘 io 那么慢。就像 MySQL 索引就是存在内存里面了。

但是如果把整个 term dictionary 放在内存里面会有什么后果呢？

内存爆了…

别忘了，ES 默认可是会对全部 text 字段进行索引，必然会消耗巨大的内存，为此 ES 针对索引进行了深度的优化。在保证执行效率的同时，尽量缩减内存空间的占用。

于是乎就有了 term index。

Term index 从数据结构上分类算是一个“Trie 树”，也就是我们常说的字典树。这是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。

这棵树不会包含所有的 term，它包含的是 term 的一些前缀（这也是字典树的使用场景，公共前缀）。通过 term index 可以快速地定位到 term dictionary 的某个 offset，然后从这个位置再往后顺序查找。就想右边这个图所表示的。（怎么样，像不像我们查英文字典，我们定位 S 开头的第一个单词，或者定位到 Sh 开头的第一个单词，然后再往后顺序查询）

lucene 在这里还做了两点优化，一是 term dictionary 在磁盘上面是分 block 保存的，一个 block 内部利用公共前缀压缩，比如都是 Ab 开头的单词就可以把 Ab 省去。二是 term index 在内存中是以 FST（finite state transducers）的数据结构保存的。

FST 有两个优点：

空间占用小。通过对词典中单词前缀和后缀的重复利用，压缩了存储空间
查询速度快。O(len(str)) 的查询时间复杂度。

FST 的理论比较复杂，本文不细讲

延伸阅读：https://www.shenyanchao.cn/blog/2018/12/04/lucene-fst/

OK，现在我们能得到 lucene 倒排索引大致是个什么样子的了。

四、关于 postings list 的一些巧技

在实际使用中，postings list 还需要解决几个痛点，

postings list 如果不进行压缩，会非常占用磁盘空间，
联合查询下，如何快速求交并集（intersections and unions）

对于如何压缩，可能会有人觉得没有必要，”posting list 不是已经只存储文档 id 了吗？还需要压缩？”，但是如果在 posting list 有百万个 doc id 的情况，压缩就显得很有必要了。（比如按照朝代查询古诗？），至于为啥需要求交并集，ES 是专门用来搜索的，肯定会有很多联合查询的需求吧（AND、OR）。

按照上面的思路，我们先将如何压缩。

1. 压缩

Frame of Reference

在 lucene 中，要求 postings lists 都要是有序的整形数组。这样就带来了一个很好的好处，可以通过增量编码（delta-encode）这种方式进行压缩。

比如现在有 id 列表 [73, 300, 302, 332, 343, 372]，转化成每一个 id 相对于前一个 id 的增量值（第一个 id 的前一个 id 默认是 0，增量就是它自己）列表是[73, 227, 2, 30, 11, 29]。在这个新的列表里面，所有的 id 都是小于 255 的，所以每个 id 只需要一个字节存储。

实际上 ES 会做的更加精细，

它会把所有的文档分成很多个 block，每个 block 正好包含 256 个文档，然后单独对每个文档进行增量编码，计算出存储这个 block 里面所有文档最多需要多少位来保存每个 id，并且把这个位数作为头信息（header）放在每个 block 的前面。这个技术叫 Frame of Reference。

上图也是来自于 ES 官方博客中的一个示例（假设每个 block 只有 3 个文件而不是 256）。

FOR 的步骤可以总结为：

进过最后的位压缩之后，整型数组的类型从固定大小 (8,16,32,64 位)4 种类型,扩展到了[1-64] 位共 64 种类型。

通过以上的方式可以极大的节省 posting list 的空间消耗，提高查询性能。不过 ES 为了提高 filter 过滤器查询的性能，还做了更多的工作，那就是缓存。

Roaring Bitmaps (for filter cache)

在 ES 中，可以使用 filters 来优化查询，filter 查询只处理文档是否匹配与否，不涉及文档评分操作，查询的结果可以被缓存。

对于 filter 查询，es 提供了 filter cache 这种特殊的缓存，filter cache 用来存储 filters 得到的结果集。缓存 filters 不需要太多的内存，它只保留一种信息，即哪些文档与 filter 相匹配。同时它可以由其它的查询复用，极大地提升了查询的性能。

我们上面提到的 Frame Of Reference 压缩算法对于 postings list 来说效果很好，但对于需要存储在内存中的 filter cache 等不太合适。

filter cache 会存储那些经常使用的数据，针对 filter 的缓存就是为了加速处理效率，对压缩算法要求更高。

对于这类 postings list，ES 采用不一样的压缩方式。那么让我们一步步来。

首先我们知道 postings list 是 Integer 数组，具有压缩空间。

假设有这么一个数组，我们第一个压缩的思路是什么？用位的方式来表示，每个文档对应其中的一位，也就是我们常说的位图，bitmap。

它经常被作为索引用在数据库、查询引擎和搜索引擎中，并且位操作（如 and 求交集、or 求并集）之间可以并行，效率更好。

但是，位图有个很明显的缺点，不管业务中实际的元素基数有多少，它占用的内存空间都恒定不变。也就是说不适用于稀疏存储。业内对于稀疏位图也有很多成熟的压缩方案，lucene 采用的就是roaring bitmaps。

我这里用简单的方式描述一下这个压缩过程是怎么样，

将 doc id 拆成高 16 位，低 16 位。对高位进行聚合 (以高位做 key，value 为有相同高位的所有低位数组)，根据低位的数据量 (不同高位聚合出的低位数组长度不相同)，使用不同的 container(数据结构) 存储。

len<4096 ArrayContainer 直接存值
len>=4096 BitmapContainer 使用 bitmap 存储

分界线的来源：value 的最大总数是为2^16=65536. 假设以 bitmap 方式存储需要 65536bit=8kb,而直接存值的方式，一个值 2 byte，4K 个总共需要2byte*4K=8kb。所以当 value 总量 <4k 时,使用直接存值的方式更节省空间。

空间压缩主要体现在:

高位聚合 (假设数据中有 100w 个高位相同的值,原先需要 100w2byte,现在只要 12byte)
低位压缩

缺点就在于位操作的速度相对于原生的 bitmap 会有影响。

这就是 trade-off 呀。平衡的艺术。

2. 联合查询

讲完了压缩，我们再来讲讲联合查询。

先讲简单的，如果查询有 filter cache，那就是直接拿 filter cache 来做计算，也就是说位图来做 AND 或者 OR 的计算。

如果查询的 filter 没有缓存，那么就用 skip list 的方式去遍历磁盘上的 postings list。

以上是三个 posting list。我们现在需要把它们用 AND 的关系合并，得出 posting list 的交集。首先选择最短的 posting list，逐个在另外两个 posting list 中查找看是否存在，最后得到交集的结果。遍历的过程可以跳过一些元素，比如我们遍历到绿色的 13 的时候，就可以跳过蓝色的 3 了，因为 3 比 13 要小。

用 skip list 还会带来一个好处，还记得前面说的吗，postings list 在磁盘里面是采用 FOR 的编码方式存储的

会把所有的文档分成很多个 block，每个 block 正好包含 256 个文档，然后单独对每个文档进行增量编码，计算出存储这个 block 里面所有文档最多需要多少位来保存每个 id，并且把这个位数作为头信息（header）放在每个 block 的前面。

因为这个 FOR 的编码是有解压缩成本的。利用 skip list，除了跳过了遍历的成本，也跳过了解压缩这些压缩过的 block 的过程，从而节省了 cpu。

五、总结

下面我们来做一个技术总结（感觉有点王刚老师的味道😂）

为了能够快速定位到目标文档，ES 使用倒排索引技术来优化搜索速度，虽然空间消耗比较大，但是搜索性能提高十分显著。
为了能够在数量巨大的 terms 中快速定位到某一个 term，同时节约对内存的使用和减少磁盘 io 的读取，lucene 使用 “term index -> term dictionary -> postings list” 的倒排索引结构，通过 FST 压缩放入内存，进一步提高搜索效率。
为了减少 postings list 的磁盘消耗，lucene 使用了 FOR（Frame of Reference）技术压缩，带来的压缩效果十分明显。
ES 的 filter 语句采用了 Roaring Bitmap 技术来缓存搜索结果，保证高频 filter 查询速度的同时降低存储空间消耗。
在联合查询时，在有 filter cache 的情况下，会直接利用位图的原生特性快速求交并集得到联合查询结果，否则使用 skip list 对多个 postings list 求交并集，跳过遍历成本并且节省部分数据的解压缩 cpu 成本

Elasticsearch 的索引思路

将磁盘里的东西尽量搬进内存，减少磁盘随机读取次数 (同时也利用磁盘顺序读特性)，结合各种压缩算法，用及其苛刻的态度使用内存。

所以，对于使用 Elasticsearch 进行索引时需要注意:

不需要索引的字段，一定要明确定义出来，因为默认是自动建索引的
同样的道理，对于 String 类型的字段，不需要 analysis 的也需要明确定义出来，因为默认也是会 analysis 的
选择有规律的 ID 很重要，随机性太大的 ID(比如 Java 的 UUID) 不利于查询

最后说一下，技术选型永远伴随着业务场景的考量，每种数据库都有自己要解决的问题（或者说擅长的领域），对应的就有自己的数据结构，而不同的使用场景和数据结构，需要用不同的索引，才能起到最大化加快查询的目的。

这篇文章讲的虽是 Lucene 如何实现倒排索引，如何精打细算每一块内存、磁盘空间、如何用诡谲的位运算加快处理速度，但往高处思考，再类比一下 MySQL，你就会发现，虽然都是索引，但是实现起来，截然不同。笼统的来说，b-tree 索引是为写入优化的索引结构。当我们不需要支持快速的更新的时候，可以用预先排序等方式换取更小的存储空间，更快的检索速度等好处，其代价就是更新慢，就像 ES。

希望本篇文章能给你带来一些收获~

参考文档

https://www.elastic.co/cn/blog/frame-of-reference-and-roaring-bitmaps
https://www.elastic.co/cn/blog/found-elasticsearch-from-the-bottom-up
http://blog.mikemccandless.com/2014/05/choosing-fast-unique-identifier-uuid.html
https://www.infoq.cn/article/database-timestamp-02
https://zhuanlan.zhihu.com/p/137574234

作者：Richard_Yi
链接：https://juejin.im/post/6889020742366920712
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

The traffic analogy

So you’re saying the ideal load is 1.00?

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

Multicore vs. multiprocessor

Bringing It Home

More servers? Or faster code?

More Reading

More on Linux Performance

一、 相似图片检测步骤：

二、dHash计算

Step1. 缩放图片

Step2. 灰度化

Step3. 差异计算

Step4. 转换为hash值

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

Github：

参考文档：

-1为什么这么长

0引言

0.1我要降维

0.2我要搜索

0.3我需要去重

0.4我要局部敏感哈希

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

1.1向量点积的含义

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

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

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

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

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

2.2黑白分明的hash

2.3随机投影hash的用途

2.4随机超平面hash

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

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

3.1历史选择了simhash

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

3.3simhash的计算过程

3.3.1分词

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

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

3.3.4计算文档的初级编码

3.3.5计算文档的最终编码

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

3.4.1海明距离

3.4.2用位运算对simhash升级

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

4基于simhash的文本去重框架

4.1比较暴力的去重框架

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

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

4.3.1抽屉原理

4.3.2更稀疏的key

4.4完整的去重框架

4.5文本去重框架的python实现

5结语

摘抄了一篇比较好的，上面图和方法在很多博客都被引用，但是相对组织的较好。

一、前言

二、关于搜索

搜索引擎原理

三、倒排索引

1. 几个概念

term

postings list

2. 索引内部结构

term dictionary

term index

四、关于 postings list 的一些巧技

1. 压缩

Frame of Reference

Roaring Bitmaps (for filter cache)

2. 联合查询

五、总结

Elasticsearch 的索引思路

参考文档

一、相似图片检测步骤：

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