前言

作者发现很多PC页面都没有做移动端转发的功能，有时候想在移动端阅读都要先在电脑上登录微信或者QQ转发到手机上面，一次两次还好，多了就觉得很不方便了，尤其是开发调试的时候。于是作者想到了开发一款浏览器插件简化一下上面的操作。

先上一下折腾出的成果 Github传送门:

正题

浏览器插件是一种小型的用于定制浏览器体验的程序。通过插件，我们可以定制js爬虫、屏蔽网页广告，网页实时查词，修改http请求头，等等，能做的东西很多。只要你会HTML，JavaScript，CSS就可以动手开发浏览器插件了。

1、创建manifest.json。任何插件都必须要有这个文件，用来描述插件的元数据，插件的配置信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

{
    "name":"Qrcode",
    "description":"Url Qrcode Extension",
    "version":"1.0",// 版本version在打包完插件的时候，判断插件是否需要更新
    "manifest_version":2, 
	  "description":"当前页面的二维码",
    "browser_action":{// 浏览器右上角的图标
        "default_popup":"popup.html", // 弹出后运行的页面，相当于index.html
        "default_icon":"icon.png",
		"default_title":"生成页面二维码"
    },
	"icons":{ 
		"16":"icon.png",
		"48":"icon.png",
		"128":"icon.png"
    },
    "commands":{
        "_execute_browser_action":{
            "suggested_key":{ // 快捷键
                "default":"Ctrl+Shift+F",
                "mac":"MacCtrl+Shift+F"
            },
            "description":"Opens popup.html"
        }
    },
	"permissions": [ // 授权
        "background", 
        "tabs"
    ], 
    "background":{ // 后台运行
        "script":[
             "js/background.js" // 当前项目没有用到，因为不存在久驻后台的需求
         ]
    }
}

2、编写业务

里面内容比较简单，生成二维码和分享均用的三方插件。值得注意的是，html里面不能和js混写，这里涉及到一个权限问题。

3、运行调试

• 进入浏览器扩展管理

• 开发者模式打开，然后点击 “加载已解压的扩展程序” 将创建的插件目录导入进去，如果你只有crx文件，直接右键以压缩文件方式解压就可以看到全部代码。

• 成功后可以看到下面的画面

调试的跟普通网页调试差不多，右键点击弹出的扩展，点“审查元素”即可打开插件的开发工具，如图

4、打包发布

打包后会生成.crx文件，将生成的.crx项目文件直接拖入浏览器，也可以在扩展程序里面添加，Google对这个审核还是比较严格的，禁止未上架的插件拖曳使用，但是可以以开发者模式安装。 亲测360浏览器是可以直接拖曳的使用的。

总结

浏览器插件开发，具有很高的实用性，值得我们去学习和了解。本文是作者记录第一次学习制作插件开发的过程，内容只是作者所用到的部分，未能面面俱到，敬请谅解。

欢迎一起讨论与留言。

参考资料

• Browser Extensions
• 360浏览器应用开放平台

前言

有朋友最近遇到客户需求：他们出于安全考虑只能是从某一台电脑才能访问应用。以下是我所想到的几种实现方案思考：

• IP地址。 你所用的IP都是运营商自动随机分配的，基本上都是处在变化中的，要想固定IP，你需要支付高昂的网络费用购买专网服务保证IP不发生变化，且需要保证局域网内就你使用这个对外的IP地址。

• 客户端软件。提供配套的客户端软件与web应用实现通信，配合MAC地址唯一性，验证客户身份。web端QQ自动登录就是这么发现你本地登录了哪些QQ的，更多可以看我这篇文章QQ如何实现跨端通信的了解原理。

• SSL双向认证。生成客户证书，只让持有证书的客户访问。安装证书和安装桌面客户端是一样的考验客户的电脑操作水平。

当然，肯定还有其他更好的方案，欢迎大佬留言指点一二。

本篇文章主要是记录一下我是如何实现SSL双向认证这个方案的。ip方案没啥好说的，保证IP唯一即可。客户端软件方案我在QQ如何实现跨端通信的这篇文章有DEMO。

原理

• SSL单向认证

  

• ①客户端的浏览器向服务器传送客户端SSL协议的版本号，加密算法的种类，产生的随机数，以及其他服务器和客户端之间通讯所需要的各种信息。

• ②服务器向客户端传送SSL协议的版本号，加密算法的种类，随机数以及其他相关信息，同时服务器还将向客户端传送自己的证书。

• ③客户利用服务器传过来的信息验证服务器的合法性，服务器的合法性包括：证书是否过期，发行服务器证书的CA是否可靠，发行者证书的公钥能否正确解开服务器证书的”发行者的数字签名”，服务器证书上的域名是否和服务器的实际域名相匹配。如果合法性验证没有通过，通讯将断开;如果合法性验证通过，将继续进行第四步。

• ④用户端随机产生一个用于后面通讯的”对称密码”，然后用服务器的公钥(服务器的公钥从步骤②中的服务器的证书中获得)对其加密，然后将加密后的”预主密码”传给服务器。

• ⑤如果服务器要求客户的身份认证(在握手过程中为可选)，用户可以建立一个随机数然后对其进行数据签名，将这个含有签名的随机数和客户自己的证书以及加密过的”预主密码”一起传给服务器。

• ⑥如果服务器要求客户的身份认证，服务器必须检验客户证书和签名随机数的合法性，具体的合法性验证过程包括：客户的证书使用日期是否有效，为客户提供证书的CA是否可靠，发行CA 的公钥能否正确解开客户证书的发行CA的数字签名，检查客户的证书是否在证书废止列表(CRL)中。检验如果没有通过，通讯立刻中断;如果验证通过，服务器将用自己的私钥解开加密的”预主密码 “，然后执行一系列步骤来产生主通讯密码(客户端也将通过同样的方法产生相同的主通讯密码)。

• ⑦服务器和客户端用相同的主密码即”通话密码”，一个对称密钥用于SSL协议的安全数据通讯的加解密通讯。同时在SSL通讯过程中还要完成数据通讯的完整性，防止数据通讯中的任何变化。

• ⑧客户端向服务器端发出信息，指明后面的数据通讯将使用的步骤⑦中的主密码为对称密钥，同时通知服务器客户端的握手过程结束。

• ⑨服务器向客户端发出信息，指明后面的数据通讯将使用的步骤⑦中的主密码为对称密钥，同时通知客户端服务器端的握手过程结束。

• ⑩-SSL的握手部分结束，SSL安全通道的数据通讯开始，客户和服务器开始使用相同的对称密钥进行数据通讯，同时进行通讯完整性的检验。

• SSL双向认证

① 浏览器发送一个连接请求给安全服务器。

② 服务器将自己的证书，以及同证书相关的信息发送给客户浏览器。

③ 客户浏览器检查服务器送过来的证书是否是由自己信赖的CA中心（如沃通CA）所签发的。如果是，就继续执行协议;如果不是，客户浏览器就给客户一个警告消息：警告客户这个证书不是可以信赖的，询问客户是否需要继续。

④ 接着客户浏览器比较证书里的消息，例如域名和公钥，与服务器刚刚发送的相关消息是否一致，如果是一致的，客户浏览器认可这个服务器的合法身份。

⑤ 服务器要求客户发送客户自己的证书。收到后，服务器验证客户的证书，如果没有通过验证，拒绝连接;如果通过验证，服务器获得用户的公钥。

⑥ 客户浏览器告诉服务器自己所能够支持的通讯对称密码方案。

⑦ 服务器从客户发送过来的密码方案中，选择一种加密程度最高的密码方案，用客户的公钥加过密后通知浏览器。

⑧ 浏览器针对这个密码方案，选择一个通话密钥，接着用服务器的公钥加过密后发送给服务器。

⑨ 服务器接收到浏览器送过来的消息，用自己的私钥解密，获得通话密钥。

⑩ 服务器、浏览器接下来的通讯都是用对称密码方案，对称密钥是加过密的。

双向认证则是需要服务端与客户端提供身份认证，只能是服务端允许的客户能去访问，安全性相对于要高一些。

实现

网上有很多实现方法，个人觉得这篇文章说的最详细：传送门

因为我域名下面申请过一个https,所以下面是我省去生成服务器端证书直接生成客户端证书的步骤：

1
2
3
4
5
6
7
8
9
10
11
12

// 生成服务器crt, 用来验证client证书的, ca.key就是https证书那个
openssl req -new -x509 -days 3650 -key ca.key -out ca.crt 

// 生成客户端证书
openssl genrsa -des3 -out client.key 1024

openssl req -new -key client.key -out client.csr

openssl ca -policy policy_anything -in client.csr -cert ca.crt -keyfile ca.key -out client.crt -days 3650

// 生成浏览器证书安装文件
openssl pkcs12 -export -inkey client.key -in client.crt -out client.pfx

上面代码可以在linux上面执行，也可以在windows上面执行。linux不说了，windows用户主要安装了apache的可以在它bin目录下找到 openssl.exe文件。

生成好了就开始使用了

• 服务端

1
2
3
4
5
6
7
8
9
10

# server

listen 443 ssl;

ssl_certificate  /etc/pki/ca_linvo/server/server.crt;       #server公钥
ssl_certificate_key  /etc/pki/ca_linvo/server/server.key;   #server私钥

ssl_client_certificate   /etc/pki/ca_linvo/root/ca.crt;     # 根级证书公钥，用于验证各个二级client
ssl_verify_client on;                                       # 开启客户端ssl校验

• 客户端

双击 client.pfx 安装证书，安装时会提示输入生成证书时设置的密码。安装成功后，重启浏览器输入网址访问，浏览器可能会提示你选择证书，选择刚才安装的那个证书即可。 此时有些浏览器会提示用户该证书不受信任，地址不安全之类，这是因为我们的server证书是我们自己颁发的，而非真正的权威CA机构颁布，忽略它既可。当然你也可以像我一样去 x云 申请一个免费server证书用着。

• 测试

总结

SSL单向验证过程中，客户端会验证自己访问的服务器端，服务器端对客户端不做验证。如果服务器端验证客户端，则需要开启服务器端验证，这就是双向验证。

问题

如何用redis存储统计1亿用户一年内的登录情况，并快速检索任意时间窗口内的活跃用户数量？

分析

Redis 是一个内存数据库，采用单线程和事件驱动的机制来处理网络请求。实际生产的QPS和TPS单台都能达到 3~4 w，读写性能非常棒,用来存储一些对核心业务弱影响的用户状态信息还是非常不错的。

对于这个问题，有2个重要的点需要考虑：

• 如何选择合适的数据类型来存储 1 亿用户的数据？
  用普通的字符串来存储肯定不行。经查一个最简单的kv的内存占用，发现为48byte。假设每个用户每天登录需要占据1对kv的话，那一亿就是$(48*100000000)/1024/1024/1024=4.47G$，这还只是是一天的量。

• 如何满足搜索？
  redis 是一个键值对的内存结构，只能根据 key 来进行定位 value 值，无法做到像 elasticsearch 那样对文档进行倒排索引快速全文检索。

方案一：Bitmap

在 redis 2.2.0 版本之后，新增了一个位图数据，它不是一种数据结构。实际上它就是一个字符串结构，只不过 value 是一个二进制数据，每一位只能是 0 或者 1 。redis 单独对 bitmap 提供了一套命令，可以对任意一位进行设置和读取。

bitmap 的核心命令：

SETBIT

语法： SETBIT key offset value

例如：

1
2
3

setbit abc 5 1 ----> 00001

setbit abc 2 1 ----> 00101

GETBIT

语法：GETBIT key offset

例如：

1
2
3

getbit abc 5 ----> 1

getbit abc 1 ----> 0

bitmap 的其他命令还有 bitcount，bitcount，bitpos，bitop 等命令，都是对位的操作。

因为 bitmap 的每一位只占据 1bit 的空间 ，所以利用这个特性我们可以把每一天作为 key，value 为 1 亿用户的活跃度状态。假设一个用户一天内只要登录了一次就算活跃。活跃我们就记为 1，不活跃我们就记为 0 。把用户 Id 作为偏移量(offset)。这样我们一个 key 就可以存储 1 亿用户的活跃状态。

我们再来算下，这样一个位图结构的值对象占据多少空间。每一个位是 1bit，一亿用户就是一亿 bit 。8bit=1Byte

$100000000/8/1024/1024=11.92M$

我用测试工程往一个 key 里通过 lua 塞进了 1 亿个 bit，然后用 rdb tools 统计这个可以需要消耗 12M 的内存空间，这完全符合要求，而且 redis 可以集群部署来进行扩容存储。我们也可以用位图压缩算法对 bitmap 进行压缩存储，例如： WAH，EWAH，Roaring Bitmaps。

我们把每一天 1 亿用户的登录状态都用 bitmap 的形式存进了 redis，那要获取某一天 id 为 88000 的用户是否活跃，直接使用命令：

GETBIT 2020-01-01 88000 [时间复杂度为 O(1)]

如果要统计某一天的所有的活跃用户数，使用bitcount命令，bitcount 可以统计 1 的个数，也就是活跃用户数：

BITCOUNT 2020-01-01 [时间复杂度为 O(N)]

如果要统计某一段时间内的活跃用户数，需要用到 bitop 命令。这个命令提供四种位运算，AND(与)，(OR)或，XOR(亦或)，NOT(非)。我们可以对某一段时间内的所有 key 进行OR(或)操作，或操作出来的位图是 0 的就代表这段时间内一次都没有登录的用户。那只要我们求出 1 的个数就可以了。以下例子求出了 2020-01-01 到 2020-01-05 这段时间内的活跃用户数:

BITCOUNT OR result 2020-01-01 2020-01-02 2020-01-03 2020-01-04 2020-01-05 [时间复杂度为 O(N)]

从时间复杂度上说，无论是统计某一天，还是统计一段时间, 在实际测试中基本上都是秒出的，符合我们的预期。

bitmap 可以很好的满足一些需要记录大量而简单信息的场景，所占空间十分小，通常来说使用场景分 2 类：

• 某一业务对象的横向扩展，key 为某一个业务对象的 id，比如记录某一个终端的功能开关，1 代表开，0 代表关。基本可以无限扩展，可以记录 2^32 个位信息。不过这种用法由于 key 上带有了业务对象的 id，导致了 key 的存储空间大于了 value 的存储空间，从空间使用角度上来看有一定的优化空间。

• 某一业务的纵向扩展，key 为某一个业务，把每一个业务对象的 id 作为偏移量记录到位上。这道面试题的例子就是用此法来进行解决。十分巧妙的利用了用户的 id 作为偏移量来找到相对应的值。当业务对象数量超过 2^32 时（约等于 42 亿），还可以分片存储。

方案二：HyperLogLog

redis 从 2.8.9 之后增加了 HyperLogLog 数据结构。这个数据结构，根据 redis 的官网介绍，这是一个概率数据结构，用来估算数据的基数。能通过牺牲准确率来减少内存空间的消耗。

我们先来看看 HyperLogLog 的方法：

PFADD 添加一个元素，如果重复，只算作一个

PFCOUNT 返回元素数量的近似值

PFMERGE 将多个 HyperLogLog 合并为一个 HyperLogLog

这很好理解，是不是。那我们就来看看同样是存储一亿用户的活跃度，HyperLogLog 数据结构需要多少空间。是不是比 bitmap 更加省空间呢。

我通过测试工程往 HyperLogLog 里 PFADD 了一亿个元素，通过 rdb tools 工具统计了这个 key 只需要 14392 Bytes，也就是 14KB 的空间。bitmap 存储一亿需要 12M，而 HyperLogLog 只需要 14K 的空间。这是一个很惊人的结果。
接下来我又放了 1000w 数据，统计出来还是 14k 。也就是说，无论你放多少数据进去，都是 14K 。

查了文档，发现 HyperLogLog 是一种概率性数据结构，在标准误差 0.81%的前提下，能够统计 ${2}^{64}$ 个数据。所以 HyperLogLog 适合在比如统计日活月活此类的对精度要不不高的场景。

HyperLogLog 使用概率算法来统计集合的近似基数，而它算法的最本源则是伯努利过程。

伯努利过程：简单来说，伯努利过程就是一个抛硬币实验的过程。抛一枚正常硬币，落地可能是正面，也可能是反面，二者的概率都是 $\frac{1}{2}$ 。伯努利过程就是一直抛硬币，直到落地时出现正面位置，并记录下抛掷次数 k 。比如说，抛一次硬币就出现正面了，此时 k 为 1; 第一次抛硬币是反面，则继续抛，直到第三次才出现正面，此时 k 为 3 。 对于 n 次伯努利过程，我们会得到 n 个出现正面的投掷次数值 $k_1$, $k_2$ … $k_n$ , 其中这里的最大值是 $k_{max}$ 。根据一顿数学推导，我们可以得出一个结论：${2}^{k_{max}}$来作为 n 的估计值。也就是说你可以根据最大投掷次数近似的推算出进行了几次伯努利过程。

虽然 HyperLogLog 数据类型不是精确统计,只适用于对精度要求不高的场景，而且这种类型无法得出每个用户的活跃度信息。

总结

对于文章开头所提到的问题，用 Bitmap 和 HyperLogLog 都可以解决。

全文检索是人们每天都在使用的工具之一。如果你曾经在google上搜索过“golang使用情况”或试图在电子商务网站上找到“室内无线摄像头”，你都会使用某种全文检索。

全文检索（FTS）是一种在文档集合中搜索文本的技术。文档可以引用网页、报纸文章、电子邮件或其他任何结构文本。

今天我们要建造我们自己的FTS引擎。在这篇文章的最后，我们将能够在不到一毫秒的时间内搜索数百万个文档。我们将从简单的搜索查询开始，比如“给我包含单词cat的所有文档”，然后扩展引擎以支持更复杂的布尔查询。

注：最著名的FTS引擎是Lucene（以及在此基础上构建的 Elasticsearch 和 Solr ）。

为什么选择FTS

在我们开始编写代码之前，您可能会问：“我们不能只使用grep，或者使用一个循环来检查每个文档是否包含我要查找的单词？” 是的，我们可以，但这并不是最好的方式。

语料库

点击下载 dumps.wikimedia.org 语料。

语料的格式如下：

1
2
3

<title>Wikipedia: Kit-Cat Klock</title>
<url>https://en.wikipedia.org/wiki/Kit-Cat_Klock</url>
<abstract>The Kit-Cat Klock is an art deco novelty wall clock shaped like a grinning cat with cartoon eyes that swivel in time with its pendulum tail.</abstract>

加载文档

首先，我们需要加载上一步下载的文档。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import (
    "encoding/xml"
    "os"
)

type document struct {
    Title string `xml:"title"`
    URL   string `xml:"url"`
    Text  string `xml:"abstract"`
    ID    int
}

func loadDocuments(path string) ([]document, error) {
    f, err := os.Open(path)
    if err != nil {
        return nil, err
    }
    defer f.Close()

    dec := xml.NewDecoder(f)
    dump := struct {
        Documents []document `xml:"doc"`
    }{}
    if err := dec.Decode(&dump); err != nil {
        return nil, err
    }

    docs := dump.Documents
    for i := range docs {
        docs[i].ID = i
    }
    return docs, nil
}

每个加载的文档都会被分配一个唯一的标识符。为了简单起见，第一个加载的文档分配ID=0，第二个ID=1，依此类推。

常规搜索测试

关键词搜索

现在我们已经将所有文档加载到内存中，我们可以尝试找到关于猫的文档。首先，让我们遍历所有文档并检查它们是否包含子字符串cat：

1
2
3
4
5
6
7
8
9

func search(docs []document, term string) []document {
    var r []document
    for _, doc := range docs {
        if strings.Contains(doc.Text, term) {
            r = append(r, doc)
        }
    }
    return r
}

在我的笔记本电脑上，搜索需要 103ms, 还不错。 如果您抽查了输出中的一些文档， 您可能会注意到该函数与caterpillar和category匹配，但cat与大写字母C不匹配。这不是我想要的。

在继续之前，我们需要解决两个问题：

• 使搜索不区分大小写（因此Cat也匹配）。

• 匹配单词边界而不是子字符串（因此caterpiller和communication不匹配）。

正则表达式搜索

一个快速想到并允许实现这两个需求的解决方案是正则表达式。

例如：(?i)\bcat\b

• (?i) 大小写不敏感

• \b 匹配单词边界（一边是单词字符，另一边不是单词字符的位置）

1
2
3
4
5
6
7
8
9
10

func search(docs []document, term string) []document {
    re := regexp.MustCompile(`(?i)\b` + term + `\b`) // Don't do this in production, it's a security risk. term needs to be sanitized.
    var r []document
    for _, doc := range docs {
        if re.MatchString(doc.Text) {
            r = append(r, doc)
        }
    }
    return r
}

呃，搜索花了2秒多。如您所见，即使有60万个文档，事情也开始变得缓慢。虽然该方法易于实现，但它的扩展性并不好。随着数据集越来越大，我们需要扫描越来越多的文档。该算法的时间复杂度是线性的, 需要扫描的文档数等于文档总数。如果我们有600万份文档，而不是60万份，搜索需要20秒。所以我们还需要优化。

反向索引

为了使搜索查询更快，我们将对文本进行预处理并预先建立索引。

FTS的核心是一种称为反向索引的数据结构, 将文档中的每个单词与包含该单词的文档相关联。

例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

documents = {
    1: "a donut on a glass plate",
    2: "only the donut",
    3: "listen to the drum machine",
}

index = {
    "a": [1],
    "donut": [1, 2],
    "on": [1],
    "glass": [1],
    "plate": [1],
    "only": [2],
    "the": [2, 3],
    "listen": [3],
    "to": [3],
    "drum": [3],
    "machine": [3],
}

下面是一个倒排索引的真实例子。书名索引书中一个术语引用页码的索引：

文本分析

在开始构建索引之前，我们需要将原始文本分解为一个适合索引和搜索的单词（标记）列表。

文本分析器由一个分词器器和多个过滤器组成。

分词器

分词器是文本分析的第一步。它的工作是将文本转换为标记列表。我们的实现在单词边界上拆分文本并删除标点符号：

1
2
3
4
5
6

func tokenize(text string) []string {
    return strings.FieldsFunc(text, func(r rune) bool {
        // Split on any character that is not a letter or a number.
        return !unicode.IsLetter(r) && !unicode.IsNumber(r)
    })
}

1
2
3

> tokenize("A donut on a glass plate. Only the donuts.")

["A", "donut", "on", "a", "glass", "plate", "Only", "the", "donuts"]

过滤器

在大多数情况下，仅仅将文本转换为标记列表是不够的。为了使文本更易于索引和搜索，我们需要进行额外的规范化。

大小写过滤

为了使搜索不区分大小写，小写过滤器将标记转换为小写。cAt、Cat和caT规范化为cat。 稍后，当我们查询索引时，我们也会降低搜索词的大小写。这将使搜索词cAt能与文本cAt匹配。

1
2
3
4
5
6
7

func lowercaseFilter(tokens []string) []string {
    r := make([]string, len(tokens))
    for i, token := range tokens {
        r[i] = strings.ToLower(token)
    }
    return r
}

1
2
3

> lowercaseFilter([]string{"A", "donut", "on", "a", "glass", "plate", "Only", "the", "donuts"})

["a", "donut", "on", "a", "glass", "plate", "only", "the", "donuts"]

去除停止语

几乎所有的英语文本都包含了像a，I，the或be这样的常用词。这样的话叫做停止语。我们将删除它们，因为几乎所有文档都会匹配停止字。
没有“官方”的停止语列表。我们把OEC rank前10名排除在外。请根据需要添加：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

var stopwords = map[string]struct{}{ // I wish Go had built-in sets.
    "a": {}, "and": {}, "be": {}, "have": {}, "i": {},
    "in": {}, "of": {}, "that": {}, "the": {}, "to": {},
}

func stopwordFilter(tokens []string) []string {
    r := make([]string, 0, len(tokens))
    for _, token := range tokens {
        if _, ok := stopwords[token]; !ok {
            r = append(r, token)
        }
    }
    return r
}

1
2
3

> stopwordFilter([]string{"a", "donut", "on", "a", "glass", "plate", "only", "the", "donuts"})

["donut", "on", "glass", "plate", "only", "donuts"]

去除多形词

由于语法规则，文档可能包含同一单词的不同形式。词干分析将单词简化为基本形式。例如，fishing、fished和fisher 可以简化为 fish 。

实现词干分析器是一项非常重要的任务，这篇文章不讨论它。我们将使用现有的模块之一

1
2
3
4
5
6
7
8
9

import snowballeng "github.com/kljensen/snowball/english"

func stemmerFilter(tokens []string) []string {
    r := make([]string, len(tokens))
    for i, token := range tokens {
        r[i] = snowballeng.Stem(token, false)
    }
    return r
}

1
2
3

> stemmerFilter([]string{"donut", "on", "glass", "plate", "only", "donuts"})

["donut", "on", "glass", "plate", "only", "donut"]

注: 词干并不总是一个有效的词。例如，airline 和 airlin。

合并

1
2
3
4
5
6
7

func analyze(text string) []string {
    tokens := tokenize(text)
    tokens = lowercaseFilter(tokens)
    tokens = stopwordFilter(tokens)
    tokens = stemmerFilter(tokens)
    return tokens
}

分词器和过滤器将句子转换成一个标记列表：

1
2
3

> analyze("A donut on a glass plate. Only the donuts.")

["donut", "on", "glass", "plate", "only", "donut"]

创建索引

回到反向索引, 它将文档中的每个单词映射到文档id。map是存储映射的一个很好选择。map中的键是一个令牌（字符串），值是一个文档ID列表：

1

type index map[string][]int

建立索引包括分析文档并将其ID添加到映射关系中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

func (idx index) add(docs []document) {
    for _, doc := range docs {
        for _, token := range analyze(doc.Text) {
            ids := idx[token]
            if ids != nil && ids[len(ids)-1] == doc.ID {
                // Don't add same ID twice.
                continue
            }
            idx[token] = append(ids, doc.ID)
        }
    }
}

func main() {
    idx := make(index)
    idx.add([]document{{ID: 1, Text: "A donut on a glass plate. Only the donuts."}})
    idx.add([]document{{ID: 2, Text: "donut is a donut"}})
    fmt.Println(idx)
}

1

map[donut:[1 2] glass:[1] is:[2] on:[1] only:[1] plate:[1]]

索引检索

要查询索引，我们将应用用于索引的相同标记器和过滤器：

1
2
3
4
5
6
7
8
9

func (idx index) search(text string) [][]int {
    var r [][]int
    for _, token := range analyze(text) {
        if ids, ok := idx[token]; ok {
            r = append(r, ids)
        }
    }
    return r
}

1
2
3

> idx.search("Small wild cat")

[[24, 173, 303, ...], [98, 173, 765, ...], [[24, 51, 173, ...]]

最后，我们可以找到所有提到猫的文件。搜索60万个文档所用时间不到1毫秒（18微秒）！

使用反向索引时，搜索查询的时间复杂度与搜索词的数量成线性关系。在上面的示例查询中，除了分析输入文本外，search只需执行三次map查找。

Boolean检索

上一节中的查询为每个令牌返回一个分离的文档列表。当我们在搜索框中输入small wild cat时，我们通常期望找到的是同时包含small、wild和cat的结果列表。下一步是计算列表之间的集合交集。这样我们将得到一个匹配所有令牌的文档列表。

幸运的是，反向索引中的id是按升序插入的。由于ID是排序的，所以可以在线性时间内计算两个列表之间的交集。intersection函数同时迭代两个列表，并收集两个列表中存在的ID：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

func intersection(a []int, b []int) []int {
    maxLen := len(a)
    if len(b) > maxLen {
        maxLen = len(b)
    }
    r := make([]int, 0, maxLen)
    var i, j int
    for i < len(a) && j < len(b) {
        if a[i] < b[j] {
            i++
        } else if a[i] > b[j] {
            j++
        } else {
            r = append(r, a[i])
            i++
            j++
        }
    }
    return r
}

更新的文本分析给定的查询文本、查找标记并计算ID列表之间的集合交集：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

func (idx index) search(text string) []int {
    var r []int
    for _, token := range analyze(text) {
        if ids, ok := idx[token]; ok {
            if r == nil {
                r = ids
            } else {
                r = intersection(r, ids)
            }
        } else {
            // Token doesn't exist.
            return nil
        }
    }
    return r
}

wikipedia dump 同时包含匹配 small、wild和cat的两个文档：

1
2
3
4

> idx.search("Small wild cat")

130764  The wildcat is a species complex comprising two small wild cat species, the European wildcat (Felis silvestris) and the African wildcat (F. lybica).
131692  Catopuma is a genus containing two Asian small wild cat species, the Asian golden cat (C. temminckii) and the bay cat.

搜索顺利完成。

总结

我们刚刚建立了一个全文搜索引擎。尽管它简单，它可以为更先进的项目奠定坚实的基础。

文中没有提到很多可以显著提高性能和使搜索引擎更人性化的东西。以下是一些进一步改进的想法：

• 扩展布尔查询以支持 OR 和 NOT ;

• 在磁盘上存储索引：

  • 每次重新启动应用程序时重建索引可能需要一段时间;

  • 大索引可能无法放入内存;

• 尝试使用内存和CPU高效的数据格式来存储文档ID集;

• 支持索引多个文档字段;

• 按相关性对结果排序;

参考

lets-build-a-full-text-search-engine - krylysov

网上能搜到的中文内容，根本不算无缝升级，既然敢叫无缝升级，那就是真的不关机，不中断服务，并且还能保证出问题能100%退回原来的版本。

一、获取原来的编译参数

使用命令

1

php -i | grep configure

把 ‘’ 去掉就是原来的编译参数

1

./configure  --prefix=/usr/local/php --with-config-file-path=/usr/local/php/etc --enable-inline-optimization --disable-debug --disable-rpath --enable-shared --enable-opcache --enable-fpm --with-fpm-user=www --with-fpm-group=www --with-mysqli=mysqlnd --with-pdo-mysql=mysqlnd --with-gettext --enable-mbstring --with-iconv --with-mcrypt --with-mhash --with-openssl --enable-bcmath --enable-soap --with-libxml-dir --enable-pcntl --enable-shmop --enable-sysvmsg --enable-sysvsem --enable-sysvshm --enable-sockets --with-curl --with-zlib --enable-zip --with-bz2 --with-readline --with-gd --enable-gd-native-ttf --enable-gd-jis-conv

更改其中安装目录防止与现有版本冲突

1

--prefix=/usr/local/php/ --with-config-file-path=/usr/local/php/etc/

现在改成

1

--prefix=/usr/local/php7.3/ --with-config-file-path=/usr/local/php7.3/etc/

然后就生成 Makefile 文件， make && make install 这里没什么好说的。

二、复制配置文件

1
2
3
4
5
6

mv PHP7.3安装目录/etc/php-fpm.conf.default        PHP7.3安装目录/etc/php-fpm.conf

mv PHP7.3源码目录/php.ini-development             PHP7.3安装目录/etc/php.ini

mv PHP7.3安装目录/etc/php-fpm.d/www.conf.default  PHP7.3安装目录/etc/php-fpm.d/www.conf

三、修改新的配置文件

1. php.ini 里面的扩展库路径，否则将会抛出警告，扩展不可用

2. php-fpm.conf 里面的 include=/usr/local/php7.3/etc/php-fpm.d/*.conf

3. www.conf 里面的 listen

   1 2 3

   ;listen = 127.0.0.1:9000 ;原 listen = 127.0.0.1:9001 ;新

新旧版本各监听不同端口。

四、启动新的 php-fpm

1

/usr/local/php7.3/sbin/php-fpm

此时两个版本将共同存在

五、测试新的 php-fpm

打开你的 nginx 配置文件，找到

1
2
3
4
5
6

 location ~ \.php$ {
	fastcgi_pass   127.0.0.1:9001; # 改成新的端口
	fastcgi_index  index.php; 
	fastcgi_param  SCRIPT_FILENAME $document_root$fastcgi_script_name;
	include        fastcgi_params;
}

修改成新的监听地址, 重新载入 nginx 配置文件

1

nginx -s reload

测试网站没有问题就关掉旧版本的 php-fpm，有问题就修改 nginx 配置文件，使用旧的 php-fpm。

六、总结

大家可能也看出来了，这种升级方式事实上就是主机上安装多版本PHP，然后进行php-fpm的切换而已。这种方式不仅适用于PHP，其他如mysql,redis等均可适用。但是需要注意各个版本之间的代码差别，防止因版本改变而产生语法错误。

方案一： Mysql

通过球面两点距离公式

$ AB = R * \arccos{( \cos{wA} * \cos{wB} * \cos{jB-jA} + \sin{wA}*\sin{wB})}$
其中 A（jA,wA）和B（jB，wB）,推导过程见这里

对于大部分已经使用MySQL的应用来说，使用这种方案没有任何迁移和部署成本，但使用SQL语句进行查询的缺点也显而易见，每条SQL的计算量都会非常大，性能将会是严重的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

# 创建表
CREATE TABLE address (
	id INT (11) AUTO_INCREMENT,
	name CHAR (80) NOT NULL,
	lat CHAR (10),
	lng CHAR (10),
	PRIMARY KEY (id)
);

# 插入测试数据
INSERT INTO address(name,lat,lng) VALUES
 ('成都', 30.659673,104.068433)
,('绵阳', 31.473909,104.680961)
,('泸州', 28.876403,105.450251) 
,('德阳', 31.134847,104.408441);

# 查询
SELECT
    id,name, (
      6371 * acos (    # 3959是地球半径的英里，6371是地球半径的千米
      cos ( radians(30.452034) )
      * cos( radians( lat ) )
      * cos( radians( lng ) - radians(106.644153) )
      + sin ( radians(30.452034) )
      * sin( radians( lat ) )
    )
) AS distance
FROM address
ORDER BY distance
LIMIT 0 , 20;

# 或通过 st_distance_sphere 函数计算
SELECT 
  name,
	round( st_distance_sphere ( point ( 106.644153, 30.452034 ), point ( lng, lat ))/ 1000, 2 ) AS distance 
FROM address 
ORDER BY distance ASC 

/**
 * 查询结果

 3	泸州	209.7647687926011
 2	绵阳	218.97099731812352
 4	德阳	226.64161541779157
 1	成都	247.70751793832144

 */

通过空间存储(spatial)

MySQL的空间扩展（MySQL Spatial Extensions），它允许在MySQL中直接处理、保存和分析地理位置相关的信息，但是需要手动排序（请忽略distance字段）。文档可见这里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

# 创建表
CREATE TABLE address (
	id INT (11) AUTO_INCREMENT,
	name CHAR (80) NOT NULL,
	point POINT NOT NULL,
	PRIMARY KEY (id)
);
# 创建索引
ALTER TABLE address ADD SPATIAL INDEX(point);

# 插入测试数据
INSERT INTO address(name,point,lat,lng) VALUES
 ('成都', GeomFromText('POINT(30.659673 104.068433)'))
,('绵阳', GeomFromText('POINT(31.473909 104.680961)'))
,('泸州', GeomFromText('POINT(28.876403 105.450251)')) 
,('德阳', GeomFromText('POINT(31.134847 104.408441)'));

# 查询： 查找坐标(30.452034,106.644153)附近 220 公里内的城市
SELECT  id,name,(
          6371 * acos (    # 3959是地球半径的英里，6371是地球半径的千米
          cos ( radians(30.452034) )
          * cos( radians( lat ) )
          * cos( radians( lng ) - radians(106.644153) )
          + sin ( radians(30.452034) )
          * sin( radians( lat ) )
        )
    ) AS distance # 仅供结果可视，非必须
    FROM    address
    WHERE   MBRContains (
                LineString(
                        Point (
                                30.452034 + 220 / ( 111.1 / COS(RADIANS(30.452034))), // 1弧度 = 111.1
                                106.644153 + 220 / 111.1
                          ),
                        Point (
                                30.452034 - 220 / ( 111.1 / COS(RADIANS(30.452034))),
                                106.644153 - 220 / 111.1
                        ) 
                ), point)

/**
 * 查询结果

 2	绵阳	218.97099731812352
 3	泸州	209.7647687926011
 
 */

通过Geohash算法

GeoHash是一种地址编码，通过切分地图区域为小方块（切分次数越多，精度越高），它能把二维的经纬度编码成一维的字符串。也就是说，理论上geohash字符串表示的并不是一个点，而是一个矩形区域，只要矩形区域足够小，达到所需精度即可。（MongoDB的索引也是基于geohash）

如：wm3yr31d252414ux就是目前我所在的位置，降低一些精度，就会是wm3yr31d2524，再降低一些精度，就会是wm3yr。

所以这样一来，我们就可以在MySQL中用LIKE ‘wm3yr%’来限定区域范围查询目标点，并且可以对结果集做缓存。更不会因为微小的经纬度变化而无法用上数据库的Query Cache。

这种方案的优点显而易见，仅用一个字符串保存经纬度信息，并且精度由字符串从头到尾的长度决定，可以方便索引。

但这种方案的缺点是：从geohash的编码算法中可以看出，靠近每个方块边界两侧的点虽然十分接近，但所属的编码会完全不同。实际应用中，虽然可以通过去搜索环绕当前方块周围的8个方块来解决该问题，但一下子将原来只需要1次SQL查询变成了需要查询9次，这样不仅增大了查询量，也将原本简单的方案复杂化了。除此之外，这个方案也无法直接得到距离，需要程序协助进行后续的排序计算。

geohash的编码算法

成都永丰立交经纬度(30.63578,104.031601)

1)、纬度范围(-90, 90)平分成两个区间(-90, 0)、(0, 90)， 如果目标纬度位于前一个区间，则编码为0，否则编码为1。

由于30.625265属于(0, 90)，所以取编码为1。

然后再将(0, 90)分成 (0, 45), (45, 90)两个区间，而39.92324位于(0, 45)，所以编码为0

然后再将(0, 45)分成 (0, 22.5), (22.5, 45)两个区间，而39.92324位于(22.5, 45)，所以编码为1

依次类推可得永丰立交纬度编码为101010111001001000100101101010。

2)、经度也用同样的算法，对(-180, 180)依次细分，(-180，0)、(0,180) 得出编码110010011111101001100000000000

3)、合并经纬度编码，从高到低，先取一位经度，再取一位纬度；得出结果 111001001100011111101011100011000010110000010001010001000100

4)、用0-9、b-z（去掉a, i, l, o）这32个字母进行base32编码，得到(30.63578,104.031601)的编码为wm3yr31d2524。

11100 10011 00011 11110 10111 00011 00001 01100 00010 00101 00010 00100 => wm3yr31d2524

算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167

<?php
class GeoHash
{
    /**
     * Base32编码映射关系
     */
    const DIGITS = ['0', '1', '2', '3', '4', '5', '6', '7', '8',
        '9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n', 'p',
        'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'];

    /**
     * 精确度，值越大越精准, 建议此处使用5的倍数
     */
    const MAX = 40;

    /**
     * GeoHash encode
     * @param $lat
     * @param $lng
     * @return string
     */
    public static function encode($lat, $lng)
    {
        return self::base32_encode(self::combine(self::dec2bit($lat, -90, 90), self::dec2bit($lng, -180, 180)));
    }

    /**
     * GeoHash decode
     * @param $val
     * @return array
     */
    public static function decode($val)
    {
        $encode = self::base32_decode($val);
        list($elat, $elng) = self::spilt($encode);
        return [self::bit2dec($elat, -90, 90), self::bit2dec($elng, -180, 180)];
    }

    /**
     * 将十进制转换成二进制经纬度
     * @param float $v 十进制经纬度
     * @param float $l 左阈值
     * @param float $r 右阈值
     * @return string
     */
    private static function dec2bit($v, $l, $r)
    {
        $s = '';
        $max = self::MAX;
        while ($max--) {
            $mid = ($l + $r) / 2;
            $d = $mid > $v ? 0 : 1;
            if ($d) {
                $l = $mid;
            } else {
                $r = $mid;
            }
            $s .= $d;
        }
        return $s;
    }

    /**
     * 经纬度编码值合并
     * @param int $elat 二进制维度
     * @param int $elng 二进制经度
     * @return string
     */
    private static function combine($elat, $elng)
    {
        $c = '';
        $max = self::MAX;
        for ($i = 0; $i < $max; $i++) {
            $c .= $elng[$i] . $elat[$i];
        }
        return $c;
    }


    /**
     * base32编码
     * @param string $s 合并后的经纬度
     * @return string
     */
    private static function base32_encode($s)
    {
        $r = '';
        for ($i = 0; $i < strlen($s); $i += 5) {
            $sub = str_pad(substr($s, $i, 5), 5, 0, STR_PAD_RIGHT);
            $num = base_convert($sub,2,10);
            $r .= self::DIGITS[$num];
        }
        return $r;
    }

    /**
     * base32解码
     * @param string $s GeoHash.encode的值
     * @return string
     */
    private static function base32_decode($s)
    {
        $r = '';
        for ($i = 0; $i < strlen($s); $i++) {
            $v = array_search($s[$i], self::DIGITS);
            $b = str_pad(base_convert($v, 10, 2), 5, 0, STR_PAD_LEFT);
            $r .= $b;
        }
        return $r;
    }

    /**
     * 经纬度拆分
     * @param string $s 将合并的经纬度拆出来
     * @return array
     */
    private static function spilt($s)
    {
        $lat = '';
        $lng = '';
        for ($i = 0; $i < strlen($s); $i += 2) {
            $lng .= $s[$i];
            $lat .= $s[$i + 1];
        }
        return [$lat, $lng];
    }

    /**
     * 二进制转换成十进制经纬度
     * @param float $s 二进制经纬度
     * @param float $l 左阈值
     * @param float $r 右阈值
     * @return float|int|string
     */
    private static function bit2dec($s, $l, $r)
    {
        $k = '';
        $mid = ($l + $r) / 2;
        for ($i = 0; $i < strlen($s); $i++) {
            if ($s[$i]) {
                $l = $mid;
            } else {
                $r = $mid;
            }
            $mid = ($l + $r) / 2;
            $k = $mid;
        }
        return $k;
    }
}

/**
 * Testing
 */
$lat = 30.63578;
$lng = 104.031601;
var_dump("初始值: $lat,$lng");
var_dump("编码后: " . ($s = GeoHash::encode($lat, $lng)));
var_dump("解码后: " . (implode(',', GeoHash::decode($s))));


/**
 * 输出
string(30) "初始值: 30.63578,104.031601"
string(27) "编码后: wm3yr31d252414ux"
string(41) "解码后: 30.63577999993,104.03160100012"
*/

方案二： MongoDB

MongoDB原生支持地理位置索引，可以直接用于位置距离计算和查询。

另外，它也是如今最流行的NoSQL数据库之一，除了能够很好地支持地理位置计算之外，还拥有诸如面向集合存储、模式自由、高性能、支持复杂查询、支持完全索引等等特性。查询结果默认将会由近到远排序，而且查询结果也包含目标点对象、距离目标点的距离等信息。由于geoNear是MongoDB原生支持的查询函数，所以性能上也做到了高度的优化，完全可以应付生产环境的压力。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

# 插入数据
db.location.insert({
      "xian":"成都",
      "sheng":"四川",
      "center":{ "type":"Point","coordinates":[104.068433,30.659673]}
});
db.location.insert({
      "xian":"绵阳",
      "sheng":"四川",
      "center":{ "type":"Point","coordinates":[104.680961,31.473909]}
});
db.location.insert({
      "xian":"泸州",
      "sheng":"四川",
      "center":{ "type":"Point","coordinates":[105.450251,28.876403]}
});
db.location.insert({
      "xian":"德阳",
      "sheng":"四川",
      "center":{ "type":"Point","coordinates":[104.408441,31.134847]}
});
 
# 创建 2dsphere索引
db.location.createIndex({"center":"2dsphere"}); # 或 db.location.ensureIndex( { center : "2dsphere" } )

# 查询: 这种方法可以返回的由近及远的点，但是不能获取距离，支持分页查询
db.location.find({
  center:{
     $near:{
       $geometry:{
          type:"Point",
          coordinates:[106.644153,30.452034]
       },
       $maxDistance: 500000 
     }
  }
}).limit(3);
/** 查询结果
{ "_id" : ObjectId("5f1e4e971a9a5bb3e50e17d3"), "xian" : "泸州", "sheng" : "四川", "center" : { "type" : "Point", "coordinates" : [ 105.450251, 28.876403 ] } }
{ "_id" : ObjectId("5f1e4e971a9a5bb3e50e17d2"), "xian" : "绵阳", "sheng" : "四川", "center" : { "type" : "Point", "coordinates" : [ 104.680961, 31.473909 ] } }
{ "_id" : ObjectId("5f1e4e991a9a5bb3e50e17d4"), "xian" : "德阳", "sheng" : "四川", "center" : { "type" : "Point", "coordinates" : [ 104.408441, 31.134847 ] } }
**/

#查询：这种方法更加灵活，可以返回距离，还可以指定查询条件等,但是不可以分页

db.runCommand( {
   geoNear: "location" ,
   near: { 
      type: "Point" , 
      coordinates: [106.644153,30.452034]
    } ,
   spherical: true,
   limit:3
});

/** 查询结果
{
        "results" : [
                {
                        "dis" : 209998.53583992278,// 距离查询点距离，单位：米
                        "obj" : {
                                "_id" : ObjectId("5f1e4e971a9a5bb3e50e17d3"),
                                "xian" : "泸州",
                                "sheng" : "四川",
                                "center" : {
                                        "type" : "Point",
                                        "coordinates" : [
                                                105.450251,
                                                28.876403
                                        ]
                                }
                        }
                },
                {
                        "dis" : 219215.02401424237,
                        "obj" : {
                                "_id" : ObjectId("5f1e4e971a9a5bb3e50e17d2"),
                                "xian" : "绵阳",
                                "sheng" : "四川",
                                "center" : {
                                        "type" : "Point",
                                        "coordinates" : [
                                                104.680961,
                                                31.473909
                                        ]
                                }
                        }
                },
                {
                        "dis" : 226894.19044046788,
                        "obj" : {
                                "_id" : ObjectId("5f1e4e991a9a5bb3e50e17d4"),
                                "xian" : "德阳",
                                "sheng" : "四川",
                                "center" : {
                                        "type" : "Point",
                                        "coordinates" : [
                                                104.408441,
                                                31.134847
                                        ]
                                }
                        }
                }
        ],
        "stats" : {
                "nscanned" : 5,
                "objectsLoaded" : 4,
                "avgDistance" : 218702.58343154436,
                "maxDistance" : 226894.19044046788,
                "time" : 0
        },
        "ok" : 1
}**/

方案三： Redis

自 Redis 3.2版 开始，Redis基于geohash和有序集合提供了地理位置相关功能。

Redis Geo模块的6个指令用途说明：

https://www.redis.net.cn/

http://redisdoc.com/script/eval.html

1）GEOADD：将给定的位置对象（纬度、经度、名字）添加到指定的key；

2）GEOPOS：从key里面返回所有给定位置对象的位置（经度和纬度）；

3）GEODIST：返回两个给定位置之间的距离；

4）GEOHASH：返回一个或多个位置对象的Geohash表示；

5）GEORADIUS：以给定的经纬度为中心，返回目标集合中与中心的距离不超过给定最大距离的所有位置对象；

6）GEORADIUSBYMEMBER：以给定的位置对象为中心，返回与其距离不超过给定最大距离的所有位置对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 插入数据
GEOADD city 104.068433 30.659673 成都
GEOADD city 104.680961 31.473909 绵阳
GEOADD city 105.450251 28.876403 泸州
GEOADD city 104.408441 31.134847 德阳

# 查询 300公里内的城市 
GEORADIUS city 106.644153 30.452034 300 km withdist asc
1) 1) "泸州"
   2) "209.8239"
2) 1) "绵阳"
   2) "219.0328"
3) 1) "德阳"
   2) "226.7054"
4) 1) "成都"
   2) "247.7777"

注意：

1
2
3
4
5

通过Redis源码分析可以看出，Redis内部使用有序集合(zset)保存位置对象，有序集合中每个元素都是一个带位置的对象，元素的score值为其经纬度对应的52位的geohash值：
1) double类型精度为52位；
2) geohash是以base32的方式编码，52bits最高可存储10位geohash值，对应地理区域大小为0.6*0.6米的格子。换句话说经Redis geo转换过的位置理论上会有约0.3*1.414=0.424米的误差。
3) 用 GEORADIUS 实现【查找附近的人】功能，时间复杂度为：O(N+log(M))。其中N为九宫格范围内的位置元素数量（要算距离）, M是指定层级格子的数量,log(M)是跳表结构中找到每个格子首元素的时间复杂度（这个过程一般会进行9次）

附录：两点距离算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
  * 获取两点间的距离
  * @param float $latitude1 纬度1
  * @param float $longitude1 经度1
  * @param float $latitude2 纬度2
  * @param float $longitude2 经度2
  * @param string $unit 单位: Km/Mi
  * @return false|float
  */
 function getDistanceBetweenPointsNew($latitude1, $longitude1, $latitude2, $longitude2, $unit = 'Mi')
 {
     $theta = $longitude1 - $longitude2;
     $distance = (sin(deg2rad($latitude1)) * sin(deg2rad($latitude2))) + (cos(deg2rad($latitude1)) * cos(deg2rad($latitude2)) * cos(deg2rad($theta)));
     $distance = acos($distance);
     $distance = rad2deg($distance);
     $distance = $distance * 60 * 1.1515;
     switch (strtolower($unit)) {
         case 'mi':
             break;
         case 'km' :
             $distance = $distance * 1.609344;
     }
     return (round($distance, 2));
 }

基础知识

事务

所谓事务(Transaction) ，是指作为单个逻辑工作单元执行的一系列操作。事务必须满足ACID原则(原子性、一致性、隔离性和持久性)。简单来说事务其实就是打包一组操作（或者命令）作为一个整体，在事务处理时将顺序执行这些操作，并返回结果，如果其中任何一个环节出错，所有的操作将被回滚。

事务的四大特性(ACID)：

• 原子性 事务是数据库的逻辑工作单位，事务中包含的各操作要么都做，要么都不做
• 一致性 事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态。因此当数据库只包含成功事务提交的结果时，就说数据库处于一致性状态。如果数据库系统 运行中发生故障，有些事务尚未完成就被迫中断，这些未完成事务对数据库所做的修改有一部分已写入物理数据库，这时数据库就处于一种不正确的状态，或者说是 不一致的状态。
• 隔离性 一个事务的执行不能其它事务干扰。即一个事务内部的操作及使用的数据对其它并发事务是隔离的，并发执行的各个事务之间不能互相干扰。
• 持续性 也称永久性，指一个事务一旦提交，它对数据库中的数据的改变就应该是永久性的。接下来的其它操作或故障不应该对其执行结果有任何影响。

锁

当程序中可能出现并发的情况时，就需要通过一定的手段来保证在并发情况下数据的准确性，通过这种手段保证了当前用户和其他用户一起操作时，所得到的结果和他单独操作时的结果是一样的。这种手段就叫做并发控制。并发控制的目的是保证一个用户的工作不会对另一个用户的工作产生不合理的影响。

常说的并发控制，一般都和数据库管理系统（DBMS）有关。在DBMS中的并发控制的任务，是确保在多个事务同时存取数据库中同一数据时，不破坏事务的隔离性和统一性以及数据库的统一性。

锁（LOCKING）便是最常用的并发控制机构，是防止其他事务访问指定的资源控制、实现并发控制的一种主要手段。

实现并发控制的主要手段大致可以分为乐观并发控制和悲观并发控制两种。

悲观锁(Pessimistic Lock)

当要对数据库中的一条数据进行修改的时候，为了避免同时被其他人修改，最好的办法就是直接对该数据进行加锁以防止并发。这种借助数据库锁机制，在修改数据之前先锁定，再修改的方式被称之为悲观并发控制【又名“悲观锁”，Pessimistic Concurrency Control，缩写“PCC”】。悲观锁有两种模式：

• 共享锁【Shared lock】又称为读锁，简称S锁。顾名思义，共享锁就是多个事务对于同一数据可以共享一把锁，都能访问到数据，但是只能读不能修改。

• 排他锁【Exclusive lock】又称为写锁，简称X锁。顾名思义，排他锁就是不能与其他锁并存，如果一个事务获取了一个数据行的排他锁，其他事务就不能再获取该行的其他锁，包括共享锁和排他锁，但是获取排他锁的事务是可以对数据行读取和修改。

悲观并发控制实际上是“先取锁再访问”的保守策略，为数据处理的安全提供了保证。

但是在效率方面，处理加锁的机制会让数据库产生额外的开销，还有增加产生死锁的机会。另外还会降低并行性，一个事务如果锁定了某行数据，其他事务就必须等待该事务处理完才可以处理那行数据。

举例(MySql-Innodb)：

1
2
3
4
5
6
7
8
9
10

//0.开启事务
begin
//1.查询商品库存信息
select quantity from items where id=1 for update;
//2.修改库存
update item set quantity=2 where id=1;
//3.提交事务
commit; 

// 以上，在对id = 1的记录修改前，先通过for update的方式进行加锁，然后再进行修改

上面提到，使用select…for update会把数据给锁住，不过需要注意一些锁的级别，MySQL InnoDB默认行级锁。行级锁都是基于索引的，如果一条SQL语句用不到索引是不会使用行级锁的，会使用表级锁把整张表锁住，这点需要注意

乐观锁(Optimistic Locking)

乐观锁是相对悲观锁而言的，乐观锁假设数据一般情况下不会造成冲突，所以在数据进行提交更新的时候，才会正式对数据的冲突与否进行检测，如果发现冲突了，则返回给用户错误的信息，让用户决定如何去做。

相对于悲观锁，在对数据库进行处理的时候，乐观锁并不会使用数据库提供的锁机制。一般的实现乐观锁的方式就是记录数据版本。

乐观并发控制相信事务之间的数据竞争(data race)的概率是比较小的，因此尽可能直接做下去，直到提交的时候才去锁定，所以不会产生任何锁和死锁。

示例(MySql-Innodb):

1
2
3
4
5
6

//查询商品库存信息，quantity = 3
select quantity from items where id=1;
// 修改商品库存为2
update items set quantity=2 where id=1 and quantity=3;

// 以上，在更新之前，先查询一下库存表中当前库存数(quantity)，然后在做update的时候，以库存数作为一个修改条件。当提交更新的时候，判断数据库表对应记录的当前库存数与第一次取出来的库存数进行比对，如果数据库表当前库存数与第一次取出来的库存数相等，则予以更新，否则认为是过期数据。

Redis事务

在Redis中实现事务主要依靠一下5个命令来实现：

• MULTI 标记一个事务块的开始。
• EXEC 执行所有事务块内的命令。
• DISCARD 取消事务，放弃执行事务块内的所有命令。
• WATCH key [key …] 监视一个(或多个) key ，如果在事务执行之前这个(或这些) key 被其他命令所改动，那么事务将被打断。
• UNWATCH 取消 WATCH 命令对所有 key 的监视。

Redis事务从开始到结束通常会通过三个阶段: 事务开始 -> 命令入队 -> 事务执行

开启事务

放弃事务

编译时错误（入队前就能检测出来）

从 Redis 2.6.5 开始，服务器会对命令入队失败的情况进行记录，并在客户端调用 EXEC 命令时，拒绝执行并自动放弃这个事务

运行时错误（入队前不能检测出来）

即使事务中有某个/某些命令在执行时产生了错误， 事务中的其他命令仍然会继续执行

WATCH监控

WATCH指令，类似乐观锁，事务提交时，如果Key的值已被别的客户端改变，整个事务队列都不会被执行

应用

服务器访问并发比较大，无效访问频繁，比如说频繁请求接口，爬虫频繁访问服务器，抢购瞬时请求过大，我们需要限流(对访问来源计数，超过设定次数，设置过期时间，提醒访问频繁，稍后再试)处理。

1
2
3
4
5
6
7
8
9
10
11
12
13

limits=500   #设置1秒内限制次数50
if EXISTS userid
    return '访问频繁，锁定时间剩余（ttl userid）秒'
if userid_count_time > limits
   exprice userid,3600
   return '访问频繁，稍后再试'
else 
   MUlTI
   incr userid_count_time          # 对用户每秒的请求进行原子递增计数
   exprice userid_count_time , 60
   EXEC

//使用事务的目的是避免执行错误中断，userid_count_time持久化到磁盘，高并发下这个很有必要

Redis事务和Mysql事务区别

了解更多：https://redis.io/topics/transactions

警告
本文只做研究用途，切勿用作其他非法用途，可参考破坏计算机信息系统罪。 运行文中代码可能对你的计算机造成一定损害(卡死)，请慎重运行。

Fork炸弹（fork bomb）在计算机领域中是一种利用系统调用fork（或其他等效的方式）进行的拒绝服务攻击(DOS)。fork炸弹以极快的速度创建大量进程（进程数呈以2为底数的指数增长趋势），并以此消耗系统分配予进程的可用空间使进程表饱和，而系统在进程表饱和后就无法运行新程序，除非进程表中的某一进程终止，它可以利用在windows/linux等系统。

linux系统

POC

1

:(){ :|:& };:

注解

Windows系统

POC

1

%0|%0|%0

将上面代码存为 .bat 文件，双击即可运行.

注释

预防

一个防止其严重影响系统的方法就是限定一个用户能够创建的进程数的上限，在Linux系统上，可以通过ulimit这个指令达到相应的效果。

更多查看：https://en.wikipedia.org/wiki/Fork_bomb

我们知道JS语言是串行执行、阻塞式、事件驱动的，那么它又是怎么支持并发处理数据的呢？

“单线程”语言

在浏览器实现中，每个单页都是一个独立进程，其中包含了JS引擎、GUI界面渲染、事件触发、定时触发器、异步HTTP请求等多个线程。

进程（Process）是操作系统CPU等资源分配的最小单位，是程序的执行实体，是线程的容器。
线程（Thread）是操作系统能够进行运算调度的最小单位，一条线程指的是进程中一个单一顺序的控制流。

因此我们可以说JS是”单线程”式的语言，代码只能按照单一顺序进行串行执行，并在执行完成前阻塞其他代码。

JS数据结构

如上图所示为JS的几种重要数据结构：

• 栈（Stack）：用于JS的函数嵌套调用，后进先出，直到栈被清空。
• 堆（Heap）：用于存储大块数据的内存区域，如对象。
• 队列（Queue）：用于事件循环机制，先进先出，直到队列为空。

事件循环

我们的经验告诉我们JS是可以并发执行的，比如定时任务、并发AJAX请求，那这些是怎么完成的呢？其实这些都是JS在用单线程模拟多线程完成的。

如上图所示，JS串行执行主线程任务，当遇到异步任务如定时器时，将其放入事件队列中，在主线程任务执行完毕后，再去事件队列中遍历取出队首任务进行执行，直至队列为空。

全部执行完成后，会有主监控进程，持续检测队列是否为空，如果不为空，则继续事件循环。

setTimeout定时任务

定时任务setTimeout(fn, timeout)会先被交给浏览器的定时器模块，等延迟时间到了，再将事件放入到事件队列里，等主线程执行结束后，如果队列中没有其他任务，则会被立即处理，而如果还有没有执行完成的任务，则需要等前面的任务都执行完成才会被执行。因此setTimeout的第2个参数是最少延迟时间，而非等待时间。

当我们预期到一个操作会很繁重耗时又不想阻塞主线程的执行时，会使用立即执行任务：

1

setTimeout(fn, 0);

特殊场景1：最小延迟为1ms

然而考虑这么一段代码会怎么执行：

1
2
3
4
5
6

setTimeout(()=>{console.log(5)},5)
setTimeout(()=>{console.log(4)},4)
setTimeout(()=>{console.log(3)},3)
setTimeout(()=>{console.log(2)},2)
setTimeout(()=>{console.log(1)},1)
setTimeout(()=>{console.log(0)},0)

了解完事件队列机制，你的答案应该是0,1,2,3,4,5，然而答案却是1,0,2,3,4,5，这个是因为浏览器的实现机制是最小间隔为1ms。

1
2
3
4

// https://github.com/nodejs/node/blob/v8.9.4/lib/timers.js#L456

if (!(after >= 1 && after <= TIMEOUT_MAX))
  after = 1; // schedule on next tick, follows browser behavior

浏览器以32位bit来存储延时，如果大于 2^32-1 ms(24.8天)，导致溢出会立刻执行。

特殊场景2：最小延迟为4ms

定时器的嵌套调用超过4层时，会导致最小间隔为4ms：

1
2
3
4
5
6
7

var i=0;
function cb() {
    console.log(i, new Date().getMilliseconds());
    if (i < 20) setTimeout(cb, 0);
    i++;
}
setTimeout(cb, 0);

可以看到前4层也不是标准的立刻执行，在第4层后间隔明显变大到4ms以上：

1
2
3
4
5
6
7

0 667
1 669
2 670
3 672
4 676
5 681
6 685

Timers can be nested; after five such nested timers, however, the interval is forced to be at least four milliseconds.

特殊场景3：浏览器节流

为了优化后台tab的加载占用资源，浏览器对后台未激活的页面中定时器延迟限制为1s。
对追踪型脚本，如谷歌分析等，在当前页面，依然是4ms的延时限制，而后台tabs为10s。

setInterval定时任务

此时，我们会知道，setInterval会在每个定时器延时时间到了后，将一个新的事件fn放入事件队列，如果前面的任务执行太久，我们会看到连续的fn事件被执行而感觉不到时间预设间隔。

因此，我们要尽量避免使用setInterval，改用setTimeout来模拟循环定时任务。

睡眠函数

JS一直缺少休眠的语法，借助ES6新的语法，我们可以模拟这个功能，但是同样的这个方法因为借助了setTimeout也不能保证准确的睡眠延时：

1
2
3
4
5
6
7
8
9

function sleep(ms) {
  return new Promise(resolve => {
    setTimeout(resolve, ms);
  })
}
// 使用
async function test() {
    await sleep(3000);
}

async await机制

async函数是Generator函数的语法糖，提供更方便的调用和语义，上面的使用可以替换为：

1
2
3
4
5
6

function* test() {
    yield sleep(3000);
}
// 使用
var g = test();
test.next();

但是调用使用更加复杂，因此一般我们使用async函数即可。但JS时如何实现睡眠函数的呢，其实就是提供一种执行时的中间状态暂停，然后将控制权移交出去，等控制权再次交回时，从上次的断点处继续执行。因此营造了一种睡眠的假象，其实JS主线程还可以在执行其他的任务。

Generator函数调用后会返回一个内部指针，指向多个异步任务的暂停点，当调用next函数时，从上一个暂停点开始执行。

协程

协程（coroutine）是指多个线程互相协作，完成异步任务的一种多任务异步执行的解决方案。他的运行流程：

• 协程A开始执行
• 协程A执行到一半，进入暂停，执行权转移到协程B
• 协程B在执行一段时间后，将执行权交换给A
• 协程A恢复执行

可以看到这也就是Generator函数的实现方案。

宏任务和微任务

一个JS的任务可以定义为：在标准执行机制中，即将被调度执行的所有代码块。

我们上面介绍了JS如何使用单线程完成异步多任务调用，但我们知道JS的异步任务分很多种，如setTimeout定时器、Promise异步回调任务等，它们的执行优先级又一样吗？

答案是不。JS在异步任务上有更细致的划分，它分为两种：

• 宏任务（macrotask)包含：

  • 执行的一段JS代码块，如控制台、script元素中包含的内容。
  • 事件绑定的回调函数，如点击事件。
  • 定时器创建的回调，如setTimeout和setInterval。

• 微任务（microtask）包含：

  • Promise对象的thenable函数。
  • Nodejs中的process.nextTick函数。
  • JS专用的queueMicrotask()函数。

宏任务和微任务都有自身的事件循环机制，也拥有独立的事件队列（Event Queue），都会按照队列的顺序依次执行。但宏任务和微任务主要有两点区别：

1. 宏任务执行完成，在控制权交还给主线程执行其他宏任务之前，会将微任务队列中的所有任务执行完成。
2. 微任务创建的新的微任务，会在下一个宏任务执行之前被继续遍历执行，直到微任务队列为空。

浏览器的进程和线程

浏览器是多进程式的，每个页面和插件都是一个独立的进程，这样可以保证单页面崩溃或者插件崩溃不会影响到其他页面和浏览器整体的稳定运行。

它主要包括：

1. 主进程：负责浏览器界面显示和管理，如前进、后退，新增、关闭，网络资源的下载和管理。
2. 第三方插件进程：当启用插件时，每个插件独立一个进程。
3. GPU进程：全局唯一，用于3D图形绘制。
4. Renderer渲染进程：每个页面一个进程，互不影响，执行事件处理、脚本执行、页面渲染。

单页面线程

浏览器的单个页面就是一个进程，指的就是Renderer进程，而进程中又包含有多个线程用于处理不同的任务，主要包括：

1. GUI渲染线程：负责HTML和CSS的构建成DOM树，渲染页面，比如重绘。
2. JS引擎线程：JS内核，如Chrome的V8引擎，负责解析执行JS代码。
3. 事件触发线程：如点击等事件存在绑定回调时，触发后会被放入宏任务事件队列。
4. 定时触发器线程：setTimeout和setInterval的定时计数器，在时间到达后放入宏任务事件队列。
5. 异步HTTP请求线程：XMLHTTPRequest请求后新开一个线程，等待状态改变后，如果存在回调函数，就将其放入宏任务队列。

需要注意的是，GUI渲染进程和JS引擎进程互斥，两者只会同时执行一个。主要的原因是为了节流，因为JS的执行会可能多次改变页面，页面的改变也会多次调用JS，如resize。因此浏览器采用的策略是交替执行，每个宏任务执行完成后，执行GUI渲染，然后执行下一个宏任务。

Webworker线程

因为JS只有一个引擎线程，同时和GUI渲染线程互斥，因此在繁重任务执行时会导致页面卡住，所以在HTML5中支持了Webworker，它用于向浏览器申请一个新的子线程执行任务，并通过postMessage API来和worker线程通信。所以我们在繁重任务执行时，可以选择新开一个Worker线程来执行，并在执行结束后通信给主线程，这样不会影响页面的正常渲染和使用。

总结

1. JS是单线程、阻塞式执行语言。
2. JS通过事件循环机制来完成异步任务并发执行。
3. JS将任务细分为宏任务和微任务来提供执行优先级。
4. 浏览器单页面为一个进程，包含的JS引擎线程和GUI渲染线程互斥，可以通过新开Web Worker线程来完成繁重的计算任务。

最后给大家出一个考题，可以猜下执行的输出结果来验证学习成果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

function sleep(ms) {
    console.log('before first microtask init');
    new Promise(resolve => {
        console.log('first microtask');
        resolve()
    })
    .then(() => {console.log('finish first microtask')});
    console.log('after first microtask init');
    return new Promise(resolve => {
          console.log('second microtask');
        setTimeout(resolve, ms);
    });
}
setTimeout(async () => {
    console.log('start task');
    await sleep(3000);
    console.log('end task');
}, 0);
setTimeout(() => console.log('add event'), 0);
console.log('main thread');

输出为：

1
2
3
4
5
6
7
8
9

main thread
start task
before first microtask init
first microtask
after first microtask init
second microtask
finish first microtask
add event
end task

参考资料

• 这一次，彻底弄懂 JavaScript 执行机制
• 并发模型与事件循环
• JavaScript 定时器与执行机制解析
• timers-and-user-prompts
• Web API 接口参考- window.setTimeout
• Generator 函数的异步应用
• 从浏览器多进程到JS单线程，JS运行机制最全面的一次梳理

Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。通常应用在一些需要快速判断某个元素是否属于集合，但是并不严格要求100%正确的场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。

集合表示和元素查询

下面我们具体来看Bloom Filter是如何用位数组表示集合的。初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0。

为了表达$S=\{x1, x2,…,xn\}$这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到$\{1,…,m\}$的范围中。对任意一个元素$x$，第i个哈希函数映射的位置$hi(x)$就会被置为$1（1≤i≤k）$。注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位）。

在判断y是否属于这个集合时，我们对y应用k次哈希函数，如果所有$hi(y)$的位置都是$1（1≤i≤k）$，那么我们就认为y是集合中的元素，否则就认为y不是集合中的元素。下图中y1就不是集合中的元素。y2或者属于这个集合，或者刚好是一个false positive。

错误率估计

前面我们已经提到了，Bloom Filter在判断一个元素是否属于它表示的集合时会有一定的错误率（false positive rate），下面我们就来估计错误率的大小。在估计之前为了简化模型，我们假设$kn<m$且各个哈希函数是完全随机的。当集合$S=\{x1, x2,…,xn\}$的所有元素都被k个哈希函数映射到m位的位数组中时，这个位数组中某一位还是0的概率是：

$ p'=(1-\frac{1}{m})^{kn} ≈ e^{-\frac{kn}{m}} $

其中$\frac{1}{m}$表示任意一个哈希函数选中这一位的概率（前提是哈希函数是完全随机的），$(1-\frac{1}{m})$表示哈希一次没有选中这一位的概率。要把$S$完全映射到位数组中，需要做$kn$次哈希。某一位还是$0$意味着$kn$次哈希都没有选中它，因此这个概率就是$(1-\frac{1}{m})^{kn}$。令 $p’=e^{-\frac{kn}{m}}$是为了简化运算，这里用到了计算e时常用的近似：

$\lim_{x \to \infty}(1-\frac{1}{x})^{-x} = e $

令ρ为位数组中0的比例，则ρ的数学期望$E(ρ)= p’$。在ρ已知的情况下，要求的错误率（false positive rate）为：

$ (1-ρ)^k ≈ (1-p')^k ≈ (1-p)^k $

$(1-ρ)$为位数组中1的比例，$(1-ρ)^k$就表示k次哈希都刚好选中1的区域，即false positive rate。上式中第二步近似在前面已经提到了，现在来看第一步近似。$p’$只是$ρ$的数学期望，在实际中$ρ$的值有可能偏离它的数学期望值。M. Mitzenmacher 已经证明[2] ，位数组中0的比例非常集中地分布在它的数学期望值的附近。因此，第一步的近似得以成立。分别将$p$和$p’$代入上式中，得：

$ f' = (1-(1-\frac{1}{m})^{kn})^k = (1-p')^k $

$ f = (1-e^{-\frac{kn}{m}})^k = (1-p)^k $

相比$p’$ 和$f’$，使用$p$和$f$通常在分析中更为方便。

最优的哈希函数个数

既然Bloom Filter要靠多个哈希函数将集合映射到位数组中，那么应该选择几个哈希函数才能使元素查询时的错误率降到最低呢？这里有两个互斥的理由：如果哈希函数的个数多，那么在对一个不属于集合的元素进行查询时得到0的概率就大；但另一方面，如果哈希函数的个数少，那么位数组中的0就多。为了得到最优的哈希函数个数，我们需要根据上一小节中的错误率公式进行计算。

先用$p$和$f$进行计算。注意到$f = e^{k\ln(1-e^{-\frac{kn}{m}})}$，我们令$g = k\ln(1-e^{-\frac{kn}{m}})$，只要让g取到最小，f自然也取到最小。由于$ p = e^{-\frac{kn}{m}}$，我们可以将g写成

$ g = -\frac{m}{n}\ln(p)\ln(1-p) $

根据对称性法则可以很容易看出当$p = \frac{1}{2}$，也就是$k = ln(2)\frac{m}{n}$时，g取得最小值。在这种情况下，最小错误率f等于$\frac{1}{2}k ≈ (0.6185)\frac{m}{n}$。另外，注意到p是位数组中某一位仍是0的概率，所以$p = \frac{1}{2}$对应着位数组中0和1各一半。换句话说，要想保持错误率低，最好让位数组有一半还空着。

需要强调的一点是，$p = \frac{1}{2}$时错误率最小这个结果并不依赖于近似值$p$和$f$。同样对于$f’ = e^{k\ln(1 − (1 − \frac{1}{m})^{kn})}$，$g’ = k\ln(1 − (1 − \frac{1}{m})^{kn})$，$p’ = (1 − \frac{1}{m})^{kn}$，我们可以将$g’$写成

$ g' = \frac{1}{n\ln(1-\frac{1}{m})}\ln(p')\ln(1-p') $

同样根据对称性法则可以得到当$p’ = \frac{1}{2}$时，$g’$取得最小值。

位数组的大小

下面我们来看看，在不超过一定错误率的情况下，Bloom Filter至少需要多少位才能表示全集中任意n个元素的集合。假设全集中共有u个元素，允许的最大错误率为є，下面我们来求位数组的位数m。

假设$X$为全集中任取n个元素的集合，$F(X)$是表示$X$的位数组。那么对于集合$X$中任意一个元素x，在$s = F(X)$中查询x都能得到肯定的结果，即s能够接受x。显然，由于Bloom Filter引入了错误，s能够接受的不仅仅是X中的元素，它还能够$є (u - n)$个false positive。因此，对于一个确定的位数组来说，它能够接受总共$n + є (u - n)$个元素。在$n + є (u - n)$个元素中，s真正表示的只有其中n个，所以一个确定的位数组可以表示

个集合。m位的位数组共有2m个不同的组合，进而可以推出，m位的位数组可以表示

个集合。全集中n个元素的集合总共有

个，因此要让m位的位数组能够表示所有n个元素的集合，必须有

即：

上式中的近似前提是n和єu相比很小，这也是实际情况中常常发生的。根据上式，我们得出结论：在错误率不大于є的情况下，m至少要等于$n\log2(1/є)$才能表示任意n个元素的集合。

上一小节中我们曾算出当$k = \ln2· \frac{m}{n}$时错误率f最小，这时$f = \frac{1}{2}k = \frac{\frac{1}{2}m\ln2}{n}$。现在令$f≤є$，可以推出

这个结果比前面我们算得的下界$n\log2(1/є)$大了$\log2 e ≈ 1.44$倍。这说明在哈希函数的个数取到最优时，要让错误率不超过є，m至少需要取到最小值的1.44倍。

算法实现

下面给出一个简单的Bloom Filter的实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

import java.util.BitSet;
import java.util.Random;

/** Very basic implementation of *Bloom Filter*.
 * Things to improve further.
 * 1. Save it on disk to make it distributed.
 * 2. add additional constructor to take in false positive rate and calculate other parameters.
 * */
public class BloomFilter<T> {
	
  int howManyHashFunctions =1;
  /**How many elements are expected at max*/
  int totalExpectedElements ; 
  /**How many elements in filter at any point in time*/
  int totalCurrentElements ;
  /**How many bits per  element needs to be set**/
  int bitsPerElement ;
  BitSet dataDictionaryBitSet;
	
  public BloomFilter(int howManyHashFunctions,  int totalExpectedElements, int bitsPerElement){
		this.howManyHashFunctions =howManyHashFunctions;
		this.totalExpectedElements =totalExpectedElements;
		this.bitsPerElement=bitsPerElement;
		dataDictionaryBitSet = new BitSet(bitsPerElement * totalExpectedElements);
	}
  
  /** Adding data in *Bloom Filter*. This will remember that this data was added.
   * @param data : The data which needs to be added in *Bloom Filter***/
  
	public void add(T data) {
		int[] hashCodes = generateMultipleHash(data );
		for (int index =0 ; index<hashCodes.length;++index) dataDictionaryBitSet.set(hashCodes[index]);
		++totalCurrentElements;
	}
	/**Find out if given data was previously added into filter. 
	 * @param data : The data which needs to be checked if it was previously added.
	 * **/
	public boolean exists(T data) {
 		int[] hashCodes = generateMultipleHash(data   );
		boolean exists = false;
		for (int index =0 ; index<hashCodes.length;++index) {
			if (dataDictionaryBitSet.get(hashCodes[index])) exists = true; 
			else {
				exists = false; 
				break;
			}
		}
		return exists;
	}
	
	/** Return how many element it has remembered. **/
	public int size(){
		return totalCurrentElements;
	}
	
    /** generate multiple hash codes
     * @param data the data which needs to be
     * @return array with positive hashes with hash values from 0 to size of bit set array  size
     */
    public  int[] generateMultipleHash(T data ) {
        int[] positions = new int[howManyHashFunctions];
        Random r = new Random(data.hashCode());
        for (int i = 0; i < howManyHashFunctions; i++) {
            positions[i] = r.nextInt(dataDictionaryBitSet.size());
        }
        return positions;
    }

}

总结

在计算机科学中，我们常常会碰到时间换空间或者空间换时间的情况，即为了达到某一个方面的最优而牺牲另一个方面。Bloom Filter在时间空间这两个因素之外又引入了另一个因素：错误率。在使用Bloom Filter判断一个元素是否属于某个集合时，会有一定的错误率。也就是说，有可能把不属于这个集合的元素误认为属于这个集合（False Positive），但不会把属于这个集合的元素误认为不属于这个集合（False Negative）。在增加了错误率这个因素之后，Bloom Filter通过允许少量的错误来节省大量的存储空间。

自从Burton Bloom在70年代提出Bloom Filter之后，Bloom Filter就被广泛用于拼写检查和数据库系统中。近一二十年，伴随着网络的普及和发展，Bloom Filter在网络领域获得了新生，各种Bloom Filter变种和新的应用不断出现。可以预见，随着网络应用的不断深入，新的变种和应用将会继续出现，Bloom Filter必将获得更大的发展。

参考文献

• Pei Cao. Bloom Filters - the math.

• Wikipedia. Bloom Filter.