[转]ElasticSearch 查询的秘密

发表于 2019-07-29 更新于 2024-04-18 分类于 ElasticSearch
本文字数： 10k 阅读时长 ≈ 9 分钟

最近在参与一个基于Elasticsearch作为底层数据框架提供大数据量(亿级)的实时统计查询的方案设计工作，花了些时间学习Elasticsearch的基础理论知识，整理了一下，希望能对Elasticsearch感兴趣/想了解的同学有所帮助。同时也希望有发现内容不正确或者有疑问的地方，望指明，一起探讨，学习，进步。

介绍

Elasticsearch 是一个分布式可扩展的实时搜索和分析引擎.

Elasticsearch 是一个建立在全文搜索引擎 Apache Lucene(TM) 基础上的搜索引擎.
当然 Elasticsearch 并不仅仅是 Lucene 那么简单，它不仅包括了全文搜索功能，还可以进行以下工作:

分布式实时文件存储，并将每一个字段都编入索引，使其可以被搜索。
实时分析的分布式搜索引擎。
可以扩展到上百台服务器，处理PB级别的结构化或非结构化数据。

基本概念

先说Elasticsearch的文件存储，Elasticsearch是面向文档型数据库，一条数据在这里就是一个文档，用JSON作为文档序列化的格式，比如下面这条用户数据：

{
    "name" :     "John",
    "sex" :      "Male",
    "age" :      25,
    "birthDate": "1990/05/01",
    "about" :    "I love to go rock climbing",
    "interests": [ "sports", "music" ]
}

用MySQL这样的数据库存储就会容易想到建立一张User表，有balabala的字段等，在Elasticsearch里这就是一个文档，当然这个文档会属于一个User的类型，各种各样的类型存在于一个索引当中。这里有一份简易的将Elasticsearch和关系型数据术语对照表:

关系数据库 ⇒ 数据库 ⇒ 表 ⇒ 行 ⇒ 列(Columns)

Elasticsearch ⇒ 索引 ⇒ 类型 ⇒ 文档 ⇒ 字段(Fields)

一个 Elasticsearch 集群可以包含多个索引(数据库)，也就是说其中包含了很多类型(表)。这些类型中包含了很多的文档(行)，然后每个文档中又包含了很多的字段(列)。

Elasticsearch的交互，可以使用Java API，也可以直接使用HTTP的Restful API方式，比如我们打算插入一条记录，可以简单发送一个HTTP的请求：

PUT /megacorp/employee/1
{
    "name" :     "John",
    "sex" :      "Male",
    "age" :      25,
    "about" :    "I love to go rock climbing",
    "interests": [ "sports", "music" ]
}

更新，查询也是类似这样的操作，具体操作手册可以参见Elasticsearch权威指南

索引

Elasticsearch最关键的就是提供强大的索引能力了，其实InfoQ的这篇时间序列数据库的秘密(2)——索引写的非常好，我这里也是围绕这篇结合自己的理解进一步梳理下，也希望可以帮助大家更好的理解这篇文章。

Elasticsearch索引的精髓：

一切设计都是为了提高搜索的性能

另一层意思：为了提高搜索的性能，难免会牺牲某些其他方面，比如插入/更新，否则其他数据库不用混了:)

前面看到往Elasticsearch里插入一条记录，其实就是直接PUT一个json的对象，这个对象有多个fields，比如上面例子中的name, sex, age, about, interests，那么在插入这些数据到Elasticsearch的同时，Elasticsearch还默默的为这些字段建立索引–倒排索引，因为Elasticsearch最核心功能是搜索。

Elasticsearch默认会为每个字段根据value的类型分别建立索引，如果不想为某些字段建立索引或者不做分词分析的话，需要通过FieldMapping注明。

Elasticsearch是如何做到快速索引的

InfoQ那篇文章里说Elasticsearch使用的倒排索引比关系型数据库的B-Tree索引快，为什么呢？

什么是B-Tree索引?

上大学读书时老师教过我们，二叉树查找效率是logN，同时插入新的节点不必移动全部节点，所以用树型结构存储索引，能同时兼顾插入和查询的性能。

因此在这个基础上，再结合磁盘的读取特性(顺序读/随机读)，传统关系型数据库采用了B-Tree/B+Tree这样的数据结构：

为了提高查询的效率，减少磁盘寻道次数，将多个值作为一个数组通过连续区间存放，一次寻道读取多个数据，同时也降低树的高度。

什么是倒排索引?

继续上面的例子，假设有这么几条数据(为了简单，去掉about, interests这两个field):

ID	Name	Age	Sex
1	Kate	24	Female
2	John	24	Male
3	Bill	29	Male

ID是Elasticsearch自建的文档id，那么Elasticsearch建立的索引如下:

Name:

Term	Posting List
Kate	1
John	2
Bill	3

Age:

Term	Posting List
24	[1,2]
29	3

Sex:

Term	Posting List
Female	1
Male	[2,3]

Posting List

Elasticsearch分别为每个field都建立了一个倒排索引，Kate, John, 24, Female这些叫term，而[1,2]就是Posting List。Posting list就是一个int的数组，存储了所有符合某个term的文档id。

看到这里，不要认为就结束了，精彩的部分才刚开始…

通过posting list这种索引方式似乎可以很快进行查找，比如要找age=24的同学，爱回答问题的小明马上就举手回答：我知道，id是1，2的同学。但是，如果这里有上千万的记录呢？如果是想通过name来查找呢？

Term Dictionary

Elasticsearch为了能快速找到某个term，将所有的term排个序，二分法查找term，logN的查找效率，就像通过字典查找一样，这就是Term Dictionary。现在再看起来，似乎和传统数据库通过B-Tree的方式类似啊，为什么说比B-Tree的查询快呢？

Term Index

B-Tree通过减少磁盘寻道次数来提高查询性能，Elasticsearch也是采用同样的思路，直接通过内存查找term，不读磁盘，但是如果term太多，term dictionary也会很大，放内存不现实，于是有了Term Index，就像字典里的索引页一样，A开头的有哪些term，分别在哪页，可以理解term index是一颗树：

这棵树不会包含所有的term，它包含的是term的一些前缀。通过term index可以快速地定位到term dictionary的某个offset，然后从这个位置再往后顺序查找。

所以term index不需要存下所有的term，而仅仅是他们的一些前缀与Term Dictionary的block之间的映射关系，再结合FST(Finite State Transducers)的压缩技术，可以使term index缓存到内存中。从term index查到对应的term dictionary的block位置之后，再去磁盘上找term，大大减少了磁盘随机读的次数。

这时候爱提问的小明又举手了:”那个FST是神马东东啊?”

一看就知道小明是一个上大学读书的时候跟我一样不认真听课的孩子，数据结构老师一定讲过什么是FST。但没办法，我也忘了，这里再补下课：

FSTs are finite-state machines that map a term (byte sequence) to an arbitrary output.

假设我们现在要将mop, moth, pop, star, stop and top(term index里的term前缀)映射到序号：0，1，2，3，4，5(term dictionary的block位置)。最简单的做法就是定义个Map<String, Integer>，大家找到自己的位置对应入座就好了，但从内存占用少的角度想想，有没有更优的办法呢？答案就是：FST(理论依据在此，但我相信99%的人不会认真看完的)

⭕️表示一种状态

–>表示状态的变化过程，上面的字母/数字表示状态变化和权重

将单词分成单个字母通过⭕️和–>表示出来，0权重不显示。如果⭕️后面出现分支，就标记权重，最后整条路径上的权重加起来就是这个单词对应的序号。

FSTs are finite-state machines that map a term (byte sequence) to an arbitrary output.

FST以字节的方式存储所有的term，这种压缩方式可以有效的缩减存储空间，使得term index足以放进内存，但这种方式也会导致查找时需要更多的CPU资源。

后面的更精彩，看累了的同学可以喝杯咖啡……

http://examples.mikemccandless.com/fst.py
Amazon DynamoDB
Cassandra
Elasticsearch
Hive
MongoDB
MySQL
PostgreSQL
SQLite

压缩技巧

Elasticsearch里除了上面说到用FST压缩term index外，对posting list也有压缩技巧。
小明喝完咖啡又举手了:”posting list不是已经只存储文档id了吗？还需要压缩？”

嗯，我们再看回最开始的例子，如果Elasticsearch需要对同学的性别进行索引(这时传统关系型数据库已经哭晕在厕所……)，会怎样？如果有上千万个同学，而世界上只有男/女这样两个性别，每个posting list都会有至少百万个文档id。
Elasticsearch是如何有效的对这些文档id压缩的呢？

Frame Of Reference

增量编码压缩，将大数变小数，按字节存储

首先，Elasticsearch要求posting list是有序的(为了提高搜索的性能，再任性的要求也得满足)，这样做的一个好处是方便压缩，看下面这个图例：

如果数学不是体育老师教的话，还是比较容易看出来这种压缩技巧的。

原理就是通过增量，将原来的大数变成小数仅存储增量值，再精打细算按bit排好队，最后通过字节存储，而不是大大咧咧的尽管是2也是用int(4个字节)来存储。

Roaring bitmaps

说到Roaring bitmaps，就必须先从bitmap说起。Bitmap是一种数据结构，假设有某个posting list：

[1,3,4,7,10]

对应的bitmap就是：

[1,0,1,1,0,0,1,0,0,1]

非常直观，用0/1表示某个值是否存在，比如10这个值就对应第10位，对应的bit值是1，这样用一个字节就可以代表8个文档id，旧版本(5.0之前)的Lucene就是用这样的方式来压缩的，但这样的压缩方式仍然不够高效，如果有1亿个文档，那么需要12.5MB的存储空间，这仅仅是对应一个索引字段(我们往往会有很多个索引字段)。于是有人想出了Roaring bitmaps这样更高效的数据结构。

Bitmap的缺点是存储空间随着文档个数线性增长，Roaring bitmaps需要打破这个魔咒就一定要用到某些指数特性：

将posting list按照65535为界限分块，比如第一块所包含的文档id范围在0 ~ 65535之间，第二块的id范围是65536 ~ 131071，以此类推。再用<商，余数>的组合表示每一组id，这样每组里的id范围都在0 ~ 65535内了，剩下的就好办了，既然每组id不会变得无限大，那么我们就可以通过最有效的方式对这里的id存储。

细心的小明这时候又举手了:”为什么是以65535为界限?”

程序员的世界里除了1024外，65535也是一个经典值，因为它=2^16-1，正好是用2个字节能表示的最大数，一个short的存储单位，注意到上图里的最后一行“If a block has more than 4096 values, encode as a bit set, and otherwise as a simple array using 2 bytes per value”，如果是大块，用节省点用bitset存，小块就豪爽点，2个字节我也不计较了，用一个short[]存着方便。

那为什么用4096来区分采用数组还是bitmap的阀值呢？

这个是从内存大小考虑的，当block块里元素超过4096后，用bitmap更省空间：
采用bitmap需要的空间是恒定的: 65536/8 = 8192bytes
而如果采用short[]，所需的空间是: 2*N(N为数组元素个数)
小明手指一掐N=4096刚好是边界:

联合索引

上面说了半天都是单field索引，如果多个field索引的联合查询，倒排索引如何满足快速查询的要求呢？

利用跳表(Skip list)的数据结构快速做“与”运算，或者
利用上面提到的bitset按位“与”

先看看跳表的数据结构：

将一个有序链表level0，挑出其中几个元素到level1及level2，每个level越往上，选出来的指针元素越少，查找时依次从高level往低查找，比如55，先找到level2的31，再找到level1的47，最后找到55，一共3次查找，查找效率和2叉树的效率相当，但也是用了一定的空间冗余来换取的。

假设有下面三个posting list需要联合索引：

如果使用跳表，对最短的posting list中的每个id，逐个在另外两个posting list中查找看是否存在，最后得到交集的结果。

如果使用bitset，就很直观了，直接按位与，得到的结果就是最后的交集。

总结和思考

Elasticsearch的索引思路:

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

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

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

看一下filebeat收集日志后，elasticsearch自动生成的id，如图：

关于最后一点，个人认为有多个因素:

其中一个(也许不是最重要的)因素: 上面看到的压缩算法，都是对Posting list里的大量ID进行压缩的，那如果ID是顺序的，或者是有公共前缀等具有一定规律性的ID，压缩比会比较高；

另外一个因素: 可能是最影响查询性能的，应该是最后通过Posting list里的ID到磁盘中查找Document信息的那步，因为Elasticsearch是分Segment存储的，根据ID这个大范围的Term定位到Segment的效率直接影响了最后查询的性能，如果ID是有规律的，可以快速跳过不包含该ID的Segment，从而减少不必要的磁盘读次数，具体可以参考这篇如何选择一个高效的全局ID方案(评论也很精彩)

后续再结合实际开发及调优工作分享更多内容，敬请期待！

拓展

倒排索引：ES倒排索引底层原理及FST算法的实现过程

字典树：Trie（Prefix Tree）原理

一直以来，数据结构的“小”而“快”是每个追求更好性能的developer孜孜不倦追求的目标，所谓“快”即检索速度快，“小”即通用最小化算法。上一节我们介绍了倒排表的数据压缩原理和过程，自本节开始，我们分几部分详细介绍一下Lucene中对倒排索引Term DIctionary以及Term Index的数据压缩和优化算法。

我们已经了解到，Term Dictionary是字典序非重复的 K-V 结构的，而通常搜索引擎级别的倒排索引，Term Dictionary 动辄以“亿”起步，这势必要求我们在做数据存储时对其数据结构有极其高的要求。以图4-1为例，假设途中英汉词典片段就是我们要存储的词项字典，为了遵循“通用最小化算法”对其进行数据压缩，我们就必须要考虑如何以最小的代价换区最高的效率。通过观察不难发现，无论任何一个Term，无外乎由26个英文字母组成，这也就意味越多的词项就会造成的越多的数据“重复”。这里所说的重复指的是词项之间会有很多个公共部分，如“abandon”和“abandonment”就共享了公共前缀“abandonment”。我们是否可以像Java开发过程中对代码的封装那样，重复利用这一部分公共内容呢？答案是肯定的！Lucene在存储这种有重复字符的数据的时候，只会存储一次，也就是哪怕有一亿个以abandon为前缀的词项，“abandom”这个前缀也只会存储一次。这里就用到了一种我们经常用到的一种数据结构：Trie即字典树，也叫前缀树（Prefix Tree）。下面我们以Term Dictionary：（msb、msbtech、msn、wltech）为例，演示一下Trie是如何存储Term Dictionary的。

如上图4-2所示，我们按照每个Term一步来演示Trie是如何存储Term Dictionary的。图中我们以圆形标识节点，箭头代表节点的出度，出度存储了当前节点对应的字符。当输入词项“msb”的时候，如果图中第一步所示，图中以加粗的圆圈标识当前节点是一个终止节点。当输入第二个词项“msbtech”的时候，复用了“msb”，当输入“msn”的时候，节点2添加了第二个出度，至此我们已经实现了对重复关键字的复用。但是问题也就随之而来了，当最后一个Term输入的时候，节点0产生了第二个出度。

FST的构建原理

细心的你应该已经发现了，在使用字典树存储Term Dictionary的案例中，字符“tech”也属于重复部分，但是未被合理复用，导致了空间浪费。为了解决这个问题，Lucene采用了另一种数据结构：FST（Finite State Transducer），即“有限状态转换机”。FST是本章内容难点，也是倒排索引的核心数据结构。

通常我们在计算机的语言中标示一件事物，都会通过某种数学模型来描述。假如现在我们要描述一件事：张三一天的所有活动。这里我们采用了一种叫做FSM（Finite State Machine）的抽象模型，如图5-1所示，这种模型使用原型的节点标示某个“状态”，状态之间可以互相转换，但是转换过程是无向的。比如睡觉醒了可以去工作，工作累了可以去玩手机；或者工作中想去上厕所等等。在这个模型中，标示状态的节点是有限多个的，但状态的转换的情况是无限多的，同一时刻只能处于某一个状态，并且状态的转换是无序切循环的。

显然这种模型并不适用于描述Term Dictionary这样的数据结构，但是我们之所以提他，是为了方便读者理解这种具化事务抽象化描述的方式。虽然FSM并不适合，但是在他的基础上演化出了FSA（Finite State Acceptor）,我们仍然以图 4-2 中的Term Dictionary数据为例，演示一下FSA是如何在Trie的基础上进行优化的。

如上图5-2所示，相较于FSM，FSA增加了Entry和Final的概念，也就是由状态转换的不确定性变为了确定，由闭环变为了单向有序，这一点和Trie是类似的，但是不同的是，FSA的Final节点是唯一的，也是因为这个原因，FSA在录入和Trie相同的Term Dictionary数据的时候，从第三步开始才表现出了区别，即尾部复用。如果在第三步的时候还不太明显，那第四步中就可以清楚的看到FSA在后缀的处理上更加高效。

至此，FSA已经满足了对Term Dictionary数据高效存储的基本要求，但是仍然不满足的一个问题就是，FSA无法存储key-value的数据类型，所以FST在此基础上为每一个出度添加了一个output属性，用来表示每个term的value值。下面以Term Dictionary：（msb/10、msbtech/5、msn/2、wltech/8、wth/16）为例，演示一下FST的构建原理，斜线后面的数字代表每个term的输出值。

通用最小化算法的应用面非常广泛，这里其实也是遵循了这样的规则。可复用的不仅仅Term的字符，输出值之所以被存储了最靠前的位置上，目的也是为了让更多的Term复用，如果输出值产生了冲突，再去处理冲突问题，最终生成最小化FST。

如上图5-3所示，当第一个term:msb被写入FST中，其输出值被保存在了其第一个节点的出度上，在数据从FST中读取的时候，计算其每个节点对应的出度的输出值以及终止节点的final output值的累加和，从而得出输出值，此时msb的输出值就是10+0+0+0=10，但是这里我用0来标识没有输出值，但实际情况没有输出值就是空而不是0，这里写0只是为了方便你去理解，这一点是需要注意的。

当第二个term:msbteach被写入的时候，其输出值5与msb的输出值10发生了冲突，这时，通用最小化算法法则再次发挥了功效。数字虽然不能像字符那样以前缀作为复用手段，但是数字是可以累加的，10可以拆成两个数字5，这样10和5就产生了公共部分，即5，所以这个时候m的输出值就需要改成5，那另一个5就需要找一个合适的位置，然而把它存放在任何一个节点的出度上似乎都会影响msbtech的计算结果，为了避免这个问题，可以把这个多出来的属于msb的输出值存入msb的final节点的final output中，节点的final output只会在当前出度是输入值的最后一个字符并且出度的target指向的是final节点的时候，才会参与计算。因此此时的msb和msbtech就各自把输出值存入了合适的位置，互不影响而且做到了“通用最小化”原则。

输入第三个term:msn，节点2产生了第二个出度：n，2 < 5，根据”通用最小化”法则，2和5有公共部分：2，5倍拆分成了2和3，此时公共前缀为“ms”，前面以“ms”为前缀的所有term都讲重新计算出度output，此时3需要满足：不能存放在公共前缀“ms”上，并且也不能在第二条出度“n”上，因此只能存放在出度b上，因为b在当前节点2第一条出度的链路上是最靠前的位置。这里FST和Trie最大的区别就是FST不仅使用了公共前缀，而且还计算了公共后缀，“msn”的最终节点会指向节点7，和节点6的出度h共享终止节点。

其实到这里还不能很好的提现“公共后缀”，但是输入wltech的时候，此时就产生了公共后缀“tech”，节点2的出度b和节点8的出度t共同指向了节点3。

输入最后一个term:wth，公共前缀为w，公共后缀为h，最终生成的FST如上图5-4所示。

摘自:https://blog.csdn.net/wlei0618/article/details/125846561

为什么Elasticsearch比MySQL的检索快？

对比MySQL的B+Tree索引原理，可以发现：

Lucene的Term index和Term Dictionary其实对应的就是MySQL的B+Tree的功能，为关键字key提供索引。Lucene的inverted index可以比MySQL的b-tree检索更快。
Term index在内存中是以FST（finite state transducers）的形式保存的，其特点是非常节省内存。所以Lucene搜索一个关键字key的速度是非常快的，而MySQL的B+Tree需要读磁盘比较。
Term dictionary在磁盘上是以分block的方式保存的，一个block内部利用公共前缀压缩，比如都是Ab开头的单词就可以把Ab省去。这样Term dictionary可以比B-tree更节约磁盘空间。
Lucene对不同的数据类型采用了不同的索引方式，上面分析是针对field为字符串的，比如针对int，有TrieIntField类型，针对经纬度，就可以用GeoHash编码。
在 MySQL中给两个字段独立建立的索引无法联合起来使用，必须对联合查询的场景建立复合索引，而Lucene可以任何AND或者OR组合使用索引进行检索。

摘自：https://www.cnblogs.com/luxiaoxun/p/5452502.html

倒排检索加速_工业界如何利用跳表、哈希表、位图进行加速?

倒排检索加速_工业界如何利用跳表、哈希表、位图进行加速？

这里其实就是多字段检索比MySQL快的原因;
es通过FST找到倒排索引的位置获取文档id列表,再通过跳表等来快速合并文档列表。

其实FST、跳表合并这些都是Lucene实现的

原文

Elasticsearch 读书笔记

[转]Epoll 的本质是什么？

发表于 2019-05-24 更新于 2021-09-10 分类于 Linux
本文字数： 6.8k 阅读时长 ≈ 6 分钟

从事服务端开发，少不了要接触网络编程。epoll 作为 Linux 下高性能网络服务器的必备技术至关重要，nginx、Redis、Skynet 和大部分游戏服务器都使用到这一多路复用技术。

epoll 很重要，但是 epoll 与 select 的区别是什么呢？epoll 高效的原因是什么？

网上虽然也有不少讲解 epoll的文章，但要么是过于浅显，或者陷入源码解析，很少能有通俗易懂的。笔者于是决定编写此文，让缺乏专业背景知识的读者也能够明白 epoll 的原理。

文章核心思想是：要让读者清晰明白 epoll 为什么性能好。

本文会从网卡接收数据的流程讲起，串联起 CPU 中断、操作系统进程调度等知识；再一步步分析阻塞接收数据、select 到 epoll 的进化过程；最后探究 epoll 的实现细节。

一、从网卡接收数据说起

下边是一个典型的计算机结构图，计算机由 CPU、存储器（内存）与网络接口等部件组成，了解 epoll 本质的第一步，要从硬件的角度看计算机怎样接收网络数据。

计算机结构图（图片来源：Linux内核完全注释之微型计算机组成结构）

下图展示了网卡接收数据的过程。

在 ① 阶段，网卡收到网线传来的数据；
经过 ② 阶段的硬件电路的传输；
最终 ③ 阶段将数据写入到内存中的某个地址上。

这个过程涉及到 DMA 传输、IO 通路选择等硬件有关的知识，但我们只需知道：网卡会把接收到的数据写入内存。

网卡接收数据的过程

通过硬件传输，网卡接收的数据存放到内存中，操作系统就可以去读取它们。

二、如何知道接收了数据？

了解 epoll 本质的第二步，要从 CPU 的角度来看数据接收。理解这个问题，要先了解一个概念——中断。

计算机执行程序时，会有优先级的需求。比如，当计算机收到断电信号时，它应立即去保存数据，保存数据的程序具有较高的优先级（电容可以保存少许电量，供 CPU 运行很短的一小段时间）。

一般而言，由硬件产生的信号需要 CPU 立马做出回应，不然数据可能就丢失了，所以它的优先级很高。CPU 理应中断掉正在执行的程序，去做出响应；当 CPU 完成对硬件的响应后，再重新执行用户程序。中断的过程如下图，它和函数调用差不多，只不过函数调用是事先定好位置，而中断的位置由“信号”决定。

中断程序调用

以键盘为例，当用户按下键盘某个按键时，键盘会给 CPU 的中断引脚发出一个高电平，CPU能够捕获这个信号，然后执行键盘中断程序。下图展示了各种硬件通过中断与 CPU 交互的过程。

CPU 中断（图片来源：net.pku.edu.cn）

现在可以回答“如何知道接收了数据？”这个问题了：当网卡把数据写入到内存后，网卡向 CPU 发出一个中断信号，操作系统便能得知有新数据到来，再通过网卡中断程序去处理数据。

三、进程阻塞为什么不占用 CPU 资源？

了解 epoll 本质的第三步，要从操作系统进程调度的角度来看数据接收。阻塞是进程调度的关键一环，指的是进程在等待某事件（如接收到网络数据）发生之前的等待状态，recv、select 和 epoll 都是阻塞方法。下边分析一下进程阻塞为什么不占用 CPU 资源？

为简单起见，我们从普通的 recv 接收开始分析，先看看下面代码：

//创建socket
int s = socket(AF_INET, SOCK_STREAM, 0);   
//绑定
bind(s, ...)
//监听
listen(s, ...)
//接受客户端连接
int c = accept(s, ...)
//接收客户端数据
recv(c, ...);
//将数据打印出来
printf(...)

这是一段最基础的网络编程代码，先新建 socket 对象，依次调用 bind、listen 与 accept，最后调用 recv 接收数据。recv 是个阻塞方法，当程序运行到 recv 时，它会一直等待，直到接收到数据才往下执行。

那么阻塞的原理是什么？

工作队列

操作系统为了支持多任务，实现了进程调度的功能，会把进程分为“运行”和“等待”等几种状态。运行状态是进程获得 CPU 使用权，正在执行代码的状态；等待状态是阻塞状态，比如上述程序运行到 recv 时，程序会从运行状态变为等待状态，接收到数据后又变回运行状态。操作系统会分时执行各个运行状态的进程，由于速度很快，看上去就像是同时执行多个任务。

下图的计算机中运行着 A、B 与 C 三个进程，其中进程 A 执行着上述基础网络程序，一开始，这 3 个进程都被操作系统的工作队列所引用，处于运行状态，会分时执行。

工作队列中有 A、B 和 C 三个进程

等待队列

当进程 A 执行到创建 socket 的语句时，操作系统会创建一个由文件系统管理的 socket 对象（如下图）。这个 socket 对象包含了发送缓冲区、接收缓冲区与等待队列等成员。等待队列是个非常重要的结构，它指向所有需要等待该 socket 事件的进程。

创建 socket

当程序执行到 recv 时，操作系统会将进程 A 从工作队列移动到该 socket 的等待队列中（如下图）。由于工作队列只剩下了进程 B 和 C，依据进程调度，CPU 会轮流执行这两个进程的程序，不会执行进程 A 的程序。所以进程 A 被阻塞，不会往下执行代码，也不会占用 CPU 资源。

socket 的等待队列

注：操作系统添加等待队列只是添加了对这个“等待中”进程的引用，以便在接收到数据时获取进程对象、将其唤醒，而非直接将进程管理纳入自己之下。上图为了方便说明，直接将进程挂到等待队列之下。

唤醒进程

当 socket 接收到数据后，操作系统将该 socket 队列上的进程重新放回到工作队列，该进程变成运行状态，继续执行代码。同时由于 socket 的接收缓冲区已经有了数据，recv 可以返回接收到的数据。

四、内核接收网络数据全过程

这一步，贯穿网卡、中断与进程调度的知识，叙述阻塞 recv 下，内核接收数据的全过程。

如下图所示，进程在 recv 阻塞期间，计算机收到了对端传送的数据（步骤①），数据经由网卡传送到内存（步骤②），然后网卡通过中断信号通知 CPU 有数据到达，CPU 执行中断程序（步骤③）。

此处的中断程序主要有两项功能，先将网络数据写入到对应 socket 的接收缓冲区里面（步骤④），再唤醒进程 A（步骤⑤），重新将进程 A 放入工作队列中。

内核接收数据全过程

唤醒进程的过程如下图所示：

唤醒进程

以上是内核接收数据全过程，这里我们可能会思考两个问题：

其一，操作系统如何知道网络数据对应于哪个 socket？
其二，如何同时监视多个 socket 的数据？

第一个问题：因为一个 socket 对应着一个端口号，而网络数据包中包含了 ip 和端口的信息，内核可以通过端口号找到对应的 socket。当然，为了提高处理速度，操作系统会维护端口号到 socket 的索引结构，以快速读取。

第二个问题是多路复用的重中之重，也正是本文后半部分的重点。

五、同时监视多个 socket 的简单方法

服务端需要管理多个客户端连接，而 recv 只能监视单个 socket，这种矛盾下，人们开始寻找监视多个 socket 的方法。epoll的要义就是高效地监视多个 socket。

从历史发展角度看，必然先出现一种不太高效的方法，人们再加以改进，正如 select 之于 epoll。

先理解不太高效的 select，才能够更好地理解 epoll 的本质。

假如能够预先传入一个 socket 列表，如果列表中的 socket 都没有数据，挂起进程，直到有一个 socket 收到数据，唤醒进程。这种方法很直接，也是 select 的设计思想。

为方便理解，我们先复习 select 的用法。在下边的代码中，先准备一个数组 fds，让 fds 存放着所有需要监视的 socket。然后调用 select，如果 fds 中的所有 socket 都没有数据，select 会阻塞，直到有一个 socket 接收到数据，select 返回，唤醒进程。用户可以遍历 fds，通过 FD_ISSET 判断具体哪个 socket 收到数据，然后做出处理。

int s = socket(AF_INET, SOCK_STREAM, 0);  
bind(s, ...);
listen(s, ...);
int fds[] =  存放需要监听的socket;
while(1){
    int n = select(..., fds, ...)
    for(int i=0; i < fds.count; i++){
        if(FD_ISSET(fds[i], ...)){
            //fds[i]的数据处理
        }
    }}

select 的流程

select 的实现思路很直接，假如程序同时监视如下图的 sock1、sock2 和 sock3 三个 socket，那么在调用 select 之后，操作系统把进程 A 分别加入这三个 socket 的等待队列中。

操作系统把进程 A 分别加入这三个 socket 的等待队列中

当任何一个 socket 收到数据后，中断程序将唤起进程。下图展示了 sock2 接收到了数据的处理流程：

注：recv 和 select 的中断回调可以设置成不同的内容。

sock2 接收到了数据，中断程序唤起进程 A

所谓唤起进程，就是将进程从所有的等待队列中移除，加入到工作队列里面，如下图所示：

将进程 A 从所有等待队列中移除，再加入到工作队列里面

经由这些步骤，当进程 A 被唤醒后，它知道至少有一个 socket 接收了数据。程序只需遍历一遍 socket 列表，就可以得到就绪的 socket。

这种简单方式行之有效，在几乎所有操作系统都有对应的实现。

但是简单的方法往往有缺点，主要是：

其一，每次调用 select 都需要将进程加入到所有监视 socket 的等待队列，每次唤醒都需要从每个队列中移除。这里涉及了两次遍历，而且每次都要将整个 fds 列表传递给内核，有一定的开销。正是因为遍历操作开销大，出于效率的考量，才会规定 select 的最大监视数量，默认只能监视 1024 个 socket。

其二，进程被唤醒后，程序并不知道哪些 socket 收到数据，还需要遍历一次。

那么，有没有减少遍历的方法？有没有保存就绪 socket 的方法？这两个问题便是 epoll 技术要解决的。

补充说明：本节只解释了 select 的一种情形。当程序调用 select 时，内核会先遍历一遍 socket，如果有一个以上的 socket 接收缓冲区有数据，那么 select 直接返回，不会阻塞。这也是为什么 select 的返回值有可能大于 1 的原因之一。如果没有 socket 有数据，进程才会阻塞。

六、epoll 的设计思路

epoll 是在 select 出现 N 多年后才被发明的，是 select 和 poll（poll 和 select 基本一样，有少量改进）的增强版本。epoll 通过以下一些措施来改进效率：

措施一：功能分离

select 低效的原因之一是将“维护等待队列”和“阻塞进程”两个步骤合二为一。如下图所示，每次调用 select 都需要这两步操作，然而大多数应用场景中，需要监视的 socket 相对固定，并不需要每次都修改。epoll 将这两个操作分开，先用 epoll_ctl 维护等待队列，再调用 epoll_wait 阻塞进程。显而易见地，效率就能得到提升。

相比 select，epoll 拆分了功能

为方便理解后续的内容，我们先了解一下 epoll 的用法。如下的代码中，先用 epoll_create 创建一个 epoll 对象 epfd，再通过 epoll_ctl 将需要监视的 socket 添加到 epfd 中，最后调用 epoll_wait 等待数据：

int s = socket(AF_INET, SOCK_STREAM, 0);   
bind(s, ...)
listen(s, ...)

int epfd = epoll_create(...);
epoll_ctl(epfd, ...); //将所有需要监听的socket添加到epfd中

while(1){
    int n = epoll_wait(...)
    for(接收到数据的socket){
        //处理
    }
}

功能分离，使得 epoll 有了优化的可能。

措施二：就绪列表

select 低效的另一个原因在于程序不知道哪些 socket 收到数据，只能一个个遍历。如果内核维护一个“就绪列表”，引用收到数据的 socket，就能避免遍历。如下图所示，计算机共有三个 socket，收到数据的 sock2 和 sock3 被就绪列表 rdlist 所引用。当进程被唤醒后，只要获取 rdlist 的内容，就能够知道哪些 socket 收到数据。

就绪列表示意图

七、epoll 的原理与工作流程

本节会以示例和图表来讲解 epoll 的原理和工作流程。

创建 epoll 对象

如下图所示，当某个进程调用 epoll_create 方法时，内核会创建一个 eventpoll 对象（也就是程序中 epfd 所代表的对象）。eventpoll 对象也是文件系统中的一员，和 socket 一样，它也会有等待队列。

内核创建 eventpoll 对象

创建一个代表该 epoll 的 eventpoll 对象是必须的，因为内核要维护“就绪列表”等数据，“就绪列表”可以作为 eventpoll 的成员。

维护监视列表

创建 epoll 对象后，可以用 epoll_ctl 添加或删除所要监听的 socket。以添加 socket 为例，如下图，如果通过 epoll_ctl 添加 sock1、sock2 和 sock3 的监视，内核会将 eventpoll 添加到这三个 socket 的等待队列中。

添加所要监听的 socket

当 socket 收到数据后，中断程序会操作 eventpoll 对象，而不是直接操作进程。

接收数据

当 socket 收到数据后，中断程序会给 eventpoll 的“就绪列表”添加 socket 引用。如下图展示的是 sock2 和 sock3 收到数据后，中断程序让 rdlist 引用这两个 socket。

给就绪列表添加引用

eventpoll 对象相当于 socket 和进程之间的中介，socket 的数据接收并不直接影响进程，而是通过改变 eventpoll 的就绪列表来改变进程状态。

当程序执行到 epoll_wait 时，如果 rdlist 已经引用了 socket，那么 epoll_wait 直接返回，如果 rdlist 为空，阻塞进程。

阻塞和唤醒进程

假设计算机中正在运行进程 A 和进程 B，在某时刻进程 A 运行到了 epoll_wait 语句。如下图所示，内核会将进程 A 放入 eventpoll 的等待队列中，阻塞进程。

epoll_wait 阻塞进程

当 socket 接收到数据，中断程序一方面修改 rdlist，另一方面唤醒 eventpoll 等待队列中的进程，进程 A 再次进入运行状态（如下图）。也因为 rdlist 的存在，进程 A 可以知道哪些 socket 发生了变化。

epoll 唤醒进程

八、epoll 的实现细节

至此，相信读者对 epoll 的本质已经有一定的了解。但我们还需要知道 eventpoll 的数据结构是什么样子？

此外，就绪队列应该应使用什么数据结构？eventpoll 应使用什么数据结构来管理通过 epoll_ctl 添加或删除的 socket？

如下图所示，eventpoll 包含了 lock、mtx、wq（等待队列）与 rdlist 等成员，其中 rdlist 和 rbr 是我们所关心的。

epoll 原理示意图，图片来源：《深入理解Nginx：模块开发与架构解析(第二版)》，陶辉

就绪列表的数据结构

就绪列表引用着就绪的 socket，所以它应能够快速的插入数据。

程序可能随时调用 epoll_ctl 添加监视 socket，也可能随时删除。当删除时，若该 socket 已经存放在就绪列表中，它也应该被移除。所以就绪列表应是一种能够快速插入和删除的数据结构。

双向链表就是这样一种数据结构，epoll 使用双向链表来实现就绪队列（对应上图的 rdllist）。

索引结构

既然 epoll 将“维护监视队列”和“进程阻塞”分离，也意味着需要有个数据结构来保存监视的 socket，至少要方便地添加和移除，还要便于搜索，以避免重复添加。红黑树是一种自平衡二叉查找树，搜索、插入和删除时间复杂度都是O(log(N))，效率较好，epoll 使用了红黑树作为索引结构（对应上图的 rbr）。

注：因为操作系统要兼顾多种功能，以及由更多需要保存的数据，rdlist 并非直接引用 socket，而是通过 epitem 间接引用，红黑树的节点也是 epitem 对象。同样，文件系统也并非直接引用着 socket。为方便理解，本文中省略了一些间接结构。

九、小结

epoll 在 select 和 poll 的基础上引入了 eventpoll 作为中间层，使用了先进的数据结构，是一种高效的多路复用技术。这里也以表格形式简单对比一下 select、poll 与 epoll，结束此文。希望读者能有所收获。

原文地址：https://my.oschina.net/editorial-story/blog/3052308

Java 原子操作的实现原理

发表于 2019-03-27 更新于 2019-10-17 分类于 JDK
本文字数： 4.9k 阅读时长 ≈ 4 分钟

本文整理自《Java并发编程的艺术》第二章作者：方腾飞　魏鹏　程晓明

阅读全文 »

[转]阿里分布式事务解决方案 Fescar 解析

发表于 2019-03-01 更新于 2024-04-18 分类于 Architecture
本文字数： 7.4k 阅读时长 ≈ 7 分钟

通过Fescar（Seata）了解分布式事务框架设计思路

阅读全文 »

查看MySQL InnoDB 表索引的高度

发表于 2019-02-18 更新于 2024-04-18 分类于 MySQL
本文字数： 7.8k 阅读时长 ≈ 7 分钟

在看《MySQL技术内幕：InnoDB存储引擎》B+树索引章节中看到这么一句话：

但是B+索引在数据库中有一个特点就是高扇出性，因此在数据库中，B+树的高度一般都在2-4层，也就是说查找某一键值的行记录时最多只需要2-4次IO。因为当前一般的机械磁盘每秒至少可以做100次IO，2-4次的IO意味着查询时间只需要0.02-0.04秒。

那么，当一个表很大的时候，索引还是是2-4层吗？那么这时搜索子节点会不会很慢？

下面通过user库中的uc_users表，来验证一下。

表结构如下：

CREATE TABLE `uc_users` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `username` varchar(40) DEFAULT NULL COMMENT 'username (login principal)',
  `connection_id` bigint(20) DEFAULT NULL COMMENT 'username (login principal)',
  `email` varchar(254) DEFAULT NULL COMMENT 'email (login principal)',
  `email_verified` tinyint(1) NOT NULL DEFAULT '0',
  `phone_number` varchar(20) DEFAULT NULL COMMENT 'mobile phone number (login principal?)',
  `phone_verified` tinyint(1) NOT NULL DEFAULT '0',
  `display_name` varchar(40) DEFAULT NULL COMMENT 'name for displaying',
  `nickname` varchar(40) DEFAULT NULL COMMENT 'nickname',
  `given_name` varchar(40) DEFAULT NULL COMMENT 'given name or first name',
  `family_name` varchar(40) DEFAULT NULL COMMENT 'family name or surname',
  `middle_name` varchar(40) DEFAULT NULL COMMENT 'middle name',
  `avatar_url` varchar(2000) DEFAULT NULL COMMENT 'avatar image url',
  `password` varchar(255) DEFAULT NULL COMMENT 'password hash (login credential)',
  `password_strength` int(11) DEFAULT NULL COMMENT 'password strength',
  `enabled` tinyint(1) NOT NULL DEFAULT '1',
  `locked` tinyint(1) NOT NULL DEFAULT '0',
  `type` smallint(6) NOT NULL COMMENT 'type (for lite-auth)',
  `source` varchar(100) DEFAULT NULL COMMENT 'where user come from',
  `last_login_at` timestamp NULL DEFAULT NULL,
  `gender` varchar(10) DEFAULT NULL,
  `birth_date` varchar(10) DEFAULT NULL,
  `zone_info` varchar(20) DEFAULT NULL,
  `locale` varchar(20) DEFAULT NULL,
  `website` varchar(2000) DEFAULT NULL,
  `address` varchar(1000) DEFAULT NULL,
  `metadata` varchar(5000) DEFAULT NULL,
  `created_at` timestamp NULL DEFAULT NULL,
  `updated_at` timestamp NULL DEFAULT NULL,
  `external_source` varchar(255) DEFAULT NULL,
  `external_id` varchar(255) DEFAULT NULL,
  `reg_client_id` varchar(128) DEFAULT NULL,
  `version` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `index_phone_number` (`phone_number`),
  KEY `index_email` (`email`),
  KEY `index_username` (`username`),
  KEY `index_created_at` (`created_at`),
  KEY `index_updated_at` (`updated_at`)
) ENGINE=InnoDB AUTO_INCREMENT=2022228456 DEFAULT CHARSET=utf8 COMMENT='user table';

索引信息如下：

数据量：5968 8046

查看index level 通过innodb_ruby查看。
具体语法参见：https://github.com/jeremycole/innodb_ruby/wiki

方法一

1、登陆MySQL对应机器，找到MySQL数据存放位置

1	ps -ef \| grep MySQL

2、找到ibdata文件位置

3、执行如下命令

1	innodb_space -s ibdata1 -T user/uc_users space-indexes

执行结果如下：

id：表示此索引的ID。
name：索引的名称，PRIMARY代表的就是聚集索引，因为InnoDB表是聚集索引组织表，行记录就是聚集索引；idx_c就是辅助索引的名称。
root：索引中根节点的page号，可以看出聚集索引的Root节点是第3号page（前0、1、2号Page已经被使用），辅助索引的根节点是第4、5、6、7、8个page。
fseg：page的说明，internal表示非叶子节点或属于根节点，leaf表示叶子节点（也就是数据页）。
used：索引使用了多少个page，可以看出聚集索引的非叶子节点使用了1819个page，叶子节点使用了1112265个page。
allocated：索引分配了多少个page，可以看出聚集索引的非叶子节点分配了2522个page，叶子节点分配了1271136个page。
fill_factor：索引的填充度，used/allocated表示填充度，也就是实际使用的大小百分比。

现在我们知道了Root节点页后，就可以使用innodb_ruby的另外一个功能，打印页结构信息，需要了解InnoDB页结构。

1
2
3

# 这里查看是索引中根节点的page号为3的索引信息 即主键索引id列
# 从返回结果中可以看到index_id=>55
innodb_space -s ibdata1 -T user/uc_users -p 3 page-dump

执行结果如下：

[root@uoc-db2 MySQL3306]# innodb_space -s ibdata1 -T user/uc_users -p 3 page-dump
#<Innodb::Page::Index:0x00000002dc04b8>:

fil header:
{:checksum=>2973709054,
 :offset=>3,
 :prev=>nil,
 :next=>nil,
 :lsn=>47538913608,
 :type=>:INDEX,
 :flush_lsn=>0,
 :space_id=>31}

fil trailer:
{:checksum=>2973709054, :lsn_low32=>294273352}

page header:
{:n_dir_slots=>2,
 :heap_top=>225,
 :garbage_offset=>192,
 :garbage_size=>42,
 :last_insert_offset=>0,
 :direction=>:left,
 :n_direction=>1,
 :n_recs=>3,
 :max_trx_id=>0,
 :level=>3,
 :index_id=>55,
 :n_heap=>7,
 :format=>:compact}

fseg header:
{:leaf=>
  <Innodb::Inode space=<Innodb::Space file="user/uc_users.ibd", page_size=16384, pages=2044416>, fseg=2>,
 :internal=>
  <Innodb::Inode space=<Innodb::Space file="user/uc_users.ibd", page_size=16384, pages=2044416>, fseg=1>}

sizes:
  header           120
  trailer            8
  directory          4
  free           16189
  used             195
  record            63
  per record     21.00

page directory:
[99, 112]

system records:
{:offset=>99,
 :header=>
  {:next=>129,
   :type=>:infimum,
   :heap_number=>0,
   :n_owned=>1,
   :min_rec=>false,
   :deleted=>false,
   :length=>5},
 :next=>129,
 :data=>"infimum\x00",
 :length=>8}
{:offset=>112,
 :header=>
  {:next=>112,
   :type=>:supremum,
   :heap_number=>1,
   :n_owned=>4,
   :min_rec=>false,
   :deleted=>false,
   :length=>5},
 :next=>112,
 :data=>"supremum",
 :length=>8}

garbage records:
{:format=>:compact,
 :offset=>192,
 :header=>
  {:next=>171,
   :type=>:node_pointer,
   :heap_number=>5,
   :n_owned=>0,
   :min_rec=>false,
   :deleted=>false,
   :nulls=>[],
   :lengths=>{},
   :externs=>[],
   :length=>5},
 :next=>171,
 :type=>:clustered,
 :key=>[{:name=>"id", :type=>"BIGINT", :value=>2002372990}],
 :row=>[],
 :sys=>[],
 :child_page_number=>1206485,
 :length=>12}

{:format=>:compact,
 :offset=>171,
 :header=>
  {:next=>171,
   :type=>:node_pointer,
   :heap_number=>4,
   :n_owned=>0,
   :min_rec=>false,
   :deleted=>false,
   :nulls=>[],
   :lengths=>{},
   :externs=>[],
   :length=>5},
 :next=>171,
 :type=>:clustered,
 :key=>[{:name=>"id", :type=>"BIGINT", :value=>55861094}],
 :row=>[],
 :sys=>[],
 :child_page_number=>948104,
 :length=>12}


records:
{:format=>:compact,
 :offset=>129,
 :header=>
  {:next=>150,
   :type=>:node_pointer,
   :heap_number=>2,
   :n_owned=>0,
   :min_rec=>true,
   :deleted=>false,
   :nulls=>[],
   :lengths=>{},
   :externs=>[],
   :length=>5},
 :next=>150,
 :type=>:clustered,
 :key=>[{:name=>"id", :type=>"BIGINT", :value=>1}],
 :row=>[],
 :sys=>[],
 :child_page_number=>375704,
 :length=>12}

{:format=>:compact,
 :offset=>150,
 :header=>
  {:next=>213,
   :type=>:node_pointer,
   :heap_number=>3,
   :n_owned=>0,
   :min_rec=>false,
   :deleted=>false,
   :nulls=>[],
   :lengths=>{},
   :externs=>[],
   :length=>5},
 :next=>213,
 :type=>:clustered,
 :key=>[{:name=>"id", :type=>"BIGINT", :value=>47377252}],
 :row=>[],
 :sys=>[],
 :child_page_number=>948104,
 :length=>12}

{:format=>:compact,
 :offset=>213,
 :header=>
  {:next=>112,
   :type=>:node_pointer,
   :heap_number=>6,
   :n_owned=>0,
   :min_rec=>false,
   :deleted=>false,
   :nulls=>[],
   :lengths=>{},
   :externs=>[],
   :length=>5},
 :next=>112,
 :type=>:clustered,
 :key=>[{:name=>"id", :type=>"BIGINT", :value=>68265101}],
 :row=>[],
 :sys=>[],
 :child_page_number=>1644800,
 :length=>12}