Hi,欢迎来到 卡瓦邦噶! 我叫 laixintao,我有一种特别的幽默感。我的梦想是让网络变得更加开放、自由和快速。这个博客发布我的一些想法,编程相关的文章,以及书、电影、游戏和音乐。

声明:本博客内容仅代表本人观点,和我的雇主无关。本站所有内容未加说明均为原创,一经发布自动进入公共领域,本人放弃所有权利。

Use the Index, Luke! 笔记1

这篇文章是我读 https://use-the-index-luke.com/ 第一章的笔记。这对开发者来说是一本不错的教材,读起来也非常轻松,在捕蛇者说的节目中也推荐过。我阅读的时候会做一些简略的笔记,逐步分享在博客上。

SQL 写起来就像英语(比 Python 更像)。SQL 只要求你描述你想要的数据,而不要求你关心数据库如何把这些数据库查出来。在这方面,这个语言的抽象很好。但是涉及到性能,这种抽象就不完美了。写 SQL 的人必须了解一些数据库的工作原理才能写出性能比较好的 SQL 语句。

影响数据库性能最关键的因素是数据库的索引,而要建立合适的索引,不是运维或者 DBA 的职责,而是开发者的。因为建立索引需要的最关键的信息是查数据的“路径”,这些信息正好开发是最熟悉的。

这本书就是面向开发的索引教程。不涉及其他数据库的复杂知识。


1. 索引

索引在数据库中,跟 table 中的数据是分开的,重复的数据。假如删掉索引,也不会丢失任何数据。类似一些专业书籍最后面的名词索引,会单独占用很多页,但是没有额外的信息,只是加速读者的查阅速度。

但是索引还要比“附录”复杂的多,因为附录不需要更新,只需要下一次印刷重新排版就好了。但是索引要面临和数据共同更新、增加、删除,并且保持一致。还需要解决中间部分的空间放不下新的索引的问题。

数据库一般结合两种数据结构:双向链表,加一个树,来解决这个问题。

索引要解决的根本问题是,提供一种有序的数据,这样查找起来更快。

如果使用连续的数组的话,那么插入数据的时候,需要顺序移动后面所有的元素。太慢了,这是无法接受的。所以这里数据库维护的是一个“逻辑顺序”。实际存储的索引在内存中并不是连续的,但是一个节点指向下一个节点,保持了一个逻辑上的顺序。

每个节点都保存了上一个节点和下一个节点的位置,这样数据库可以向前或向后查找。这个数据结构叫做双向链表(doubly linked list)这样每次插入和更新数据的时候,只要修改前后节点的指向就好了。

数据库将这些节点存放在文件系统的 block 中,这也是文件系统读写的最小单位。在一个 block 中存储尽可能多的 block。这样,索引就有两层,要找一个特定的索引,首先要找到它在哪个 block,然后读出来这个 block,找到这个 block 中的索引。

B-Tree(省略)

这部分对我是已知内容,所以忽略了,读者如果有兴趣可以去搜索一下相关的资料,比较丰富的。


2. 使用索引也可能很慢

即使使用索引,也可能查询很慢。有些人说重建索引可以解决问题,但长期来看并没有用。为什么使用了索引还可能很慢呢?原因有以下几点:

  1. 存在多个相同的值。这个时候会有多个 B-Tree 的叶子节点是相等的,为了确保找到其他叶子节点符合查询条件的数据,还要遍历把这些叶子节点都遍历一遍。所以除了 Tree 遍历的时间,还有顺着叶子节点找到最终的叶子节点的时间;
  2. 找到索引之后,还要去表中查找数据。这些数据散落在磁盘的不同地方,读比较耗时;

所以通过索引查找数据实际上是分 3 步:

  1. 遍历树;
  2. 顺着命中的叶子节点找相邻的叶子节点;
  3. 拿到索引中保存的数据的问题,读数据;

很多人认为,如果命中索引,查询还很慢,一定是由于索引腐坏了。实际上不是这样的。

甚至有时候,命中索引的情况可能比 TABLE SCAN 还要慢。举个例子,假如有一个人名的数据库,对 Lastname 建立索引,但是 Lastname 相同的人很多。在下面这个 SQL 中,TABLE SCAN 可能比按照索引查询还要慢。

因为在索引查找的过程中,虽然 Tree 遍历很快,但是还要遍历一个 Linked List,找到所有的符合 lastname = "Pinkman" 的数据,然后将这些 ROW 全部都读出来,依次判断它们是否符合另一个条件 firstname = "Jesse"。相比于 TABLE SCAN,这两个操作都很耗时,而且 TABLE SCAN 虽然扫的数据量要大一些,但它是顺序读的,硬盘顺序读更快,而且可以利用一些 Kernel 的 read ahead 的技术。注意 TABLE SCAN 比 INDEX RANGE SCAN 快的条件并不是数据量有多少,而是索引中相等的值有多少。

很多数据库提供命令,可以查看索引的使用方式。比如 Oracle:

  1. INDEX UNIQUE SCAN:只遍历数,用于检查数据是否已经存在;
  2. INDEX RANGE SCAN:遍历树+遍历相邻叶子节点;
  3. TABLE ACCESS BY INDEX ROWID:根据索引中的 ROWID 读出数据(完整的3步)。

3. 什么时候会使用索引

当使用 INDEX UNIQUE SCAN 的时候,一般不会出现 slow query。因为要找的数据只会命中一条,不会需要遍历叶子节点,Table Access  也只需要一次。

串联索引(Concatenated Indexes,某些地方可能翻译成联合索引,但是联合这个词丢失了“必须按顺序”这个关键的信息,所以 Concatenated Index 这个词可能比 esmulti-column, composite or combined index 更合适)

如果一个索引有相同的值,那么如果要作为主键的话,就要和其他列一起,作为串联索引了。

什么时候会通过串联索引查询,什么时候不会,这个细节必须要明白。

串联索引也只是一个索引,以两列的串联索引为例,与单列索引不同的是,如果第一列的值相同,就会使用第二列索引排列这些第一列相同的索引。类似于一本书的目录同一个章节下的小结。你可以按照章节、小结两列一起搜索,也可以搜索某一章的所有小结。但是不能在没有章节的情况下直接搜索小结。即,不能使用串联索引后面的列进行搜索。这样不会走到串联索引,而是会扫全表。

所以在建立索引的时候要根据查询场景,建立联合索引的时候,列的顺序很重要,将需要单独查询的 Column 放到前面。

同样的,如果建立 3 列的串联索引,那么以下三种情况可以走索引,其他的不可以:

  1. 根据第一列查询;
  2. 根据第一列和第二列查询;
  3. 根据三列查询;

虽然串联索引可以带来更好的性能,但是第一列重复数据不多的情况下,尽可能使用单列的索引。因为这样可以1)节省空间;2)使数据的增加,修改,删除更快。因为索引也需要空间来存储,并且每次数据更新都需要更新索引。

但是,并不一定是有索引可用,就会用。上面我们说过,在某些情况下,使用索引可能要比不使用索引更慢。

数据库会有一个专门的组件,叫做“优化器”,当有很多选择的时候,优化器会决定选择哪一种。优化器有两种,一种给所有的可用查询方案进行评分(Cost-based optimizers, CBO);另一种通过固定的、提前设定的规则决定使用哪种方案(Rule-based optimizers, RBO)。第二种不灵活,很少用了。在前面提到的这种 TABLE SCAN 可能比 INDEX RANGE SCAN 更快的情况,优化器会使用表的统计数据(关键的数据比如 row 的量级,index tree 的深度等),来决定方案。如果在某种情况下没有统计数据的话,优化器会使用默认数据。如果提供了准确的统计数据,优化器通常会工作的很好。Oracle 数据库在新建索引之后,不会自动更新统计数据,最好手动更新一下。


4. 口吞玻璃而不伤身体

使用索引可以提高查询速度,但是有一些限制,比如必须大小写准确。

这里提供一种既可以使用索引,又可以大小写不敏感的方法。

数据库之所以无法使用索引,是因为如下的查询函数对它来说是和黑盒。

它看到的是这样:

而且它的索引是基于比较字符串建立的大小写敏感的索引,所以无法在索引树中进行忽略大小写的遍历。

解决方法非常简单,我们建立索引的时候,使用大写简历索引即可。这种索引叫做基于函数的索引,function-based index (FBI).

如果优化器发现索引的字段一模一样的出现在了查询语句中,就会使用索引。

MySQL 和 SQL Server 不支持 FBI,但是有另一种方法,就是增加一个字段,对这个字段建索引。

除了 UPPER 这种函数,你还可以使用其他的函数建索引,甚至可以使用用户自己定义的函数。但是通过 FBI 的原理,很显然可以联想到,你所使用的函数必须在任何情况下执行都得到相同的结果。因为 FBI 的原理不过是用同样的函数处理查询条件,和索引数据,相当于基于一个 mapping 索引了 mapping 之后的数据。下面是一个反例,其余用一个用了外部变量(时间)的函数做 FBI。

这样的问题是,随着时间增加,人的年龄会变,但是索引好的数据不会变。

数据最终会腐烂。

不要 Over indexing!

第一次听说 FBI 的人,可能倾向于索引 Everything。每一个索引都不是零成本的,都需要维护。尽量优化索引和查询路径,使一种索引能够尽可能用于很多查询。

5. Parameterized Queries

这个东西简单来说,就是我们在执行 SQL 的时候,我们并不是直接告诉数据库我们要执行的 SQL。而是先告诉数据库我们要执行的语句是什么,再告诉数据库这个语句中某些变量是什么。一般 ORM 会这么做,因为 ORM 都是在执行相同的 SQL 语句,只不过每次执行的语句中的一些变量不同。

比如下面这个例子:

我们告诉数据库 Statement 是什么,但是里面有一个 ? 作为占位符(也可以是其他的字符)。然后再通过一个函数告诉它每一个位置的 ? 分别是什么。

这么做有两个好处:

  1. 防止 SQL 注入。你无法使用一个 ; 结束当前的 SQL 然后再插入恶意的 SQL,无论这个地方填上什么都会作为一个“参数”;
  2. 加速选择执行方案。如果每次都是执行相同的语句,只是中间有一些值不同。那么数据库每次都会选择相同的执行方案,这节省了每次都要选择执行方案的时间;

但是这也不是完全免费的。前面说过有些情况下,使用索引可能更慢。要选择最佳的执行计划,需要根据表中重复数据的分布决定。如果使用 Bind parameters 的话,因为数据库是根据 ? 占位符的 SQL 语句来选择执行计划的,考虑下面这样的 SQL:

如果 subsidiary_id 重复的很多的话,使用 TABLE SCAN 会快一些,如果重复很少的话,使用索引会快一些。这个时候数据库并不知道这个 ? 会是什么,也就无法选择执行计划。这时数据库会假设这个分布是均匀的,每次通过索引会得到相同数量的 ROW,从而选择一种查询计划。

和编译器类比的话,bind variables 就像是代码中的变量,直接写的 SQL 就像是常量。编译器可以对常量进行优化,甚至在编译的时候将它们计算好。但是变量,直到程序运行之后,编译器都不知道这个值是什么,也就无法做针对的优化。

简单来说,对一个 SQL 语句使用固定的查询计划可以减少评估查询计划的时间。对每个 SQL 都评估查询计划,可以总是使用最优的查询计划。举个例子,TODO List 中,大部分数据都是 Done 的状态,小部分数据是 Todo 的状态。所以查找 Done 的数据用 TABLE SCAN,查询 Todo 的数据使用索引,是比较合适的。所以开发者应该是最了解数据获取方式的角色。


6. Range 查找

上文中已经提到,INDEX RANGE SCAN 的瓶颈在于要遍历叶子节点,要提高性能,就要让需要遍历的叶子节点越少越好。即索引中相等的值越少越好。

考虑下面的 SQL:

假设我们对搜索的这两列( date_of_birth & subsidiary_id )建立索引的话,怎么建才能让查询更快呢?

这里的顺序很重要。假如是 date_of_birth & subsidiary_id 这样的顺序的话,那么查询先使用第一列 date_of_birth 的索引过滤出来一些 ROW,然后再这些 ROW 中寻找合适的 subsidiary_id。这个时候,第二列 subsidiary_id 是无法用上的,因为我们前面已经说过,只有在第一列的数据相同的时候,才会使用第二列索引。对于 date_of_birth 不同的这些 ROW 来说,subsidiary_id 的索引用不上。这个时候会有很大一个范围的  TABLE SCAN 了。但是如果我们建立的顺序是 subsidiary_id & date_of_birth 呢?由于第一列的 WHERE 条件是 =,那么在进行后面的 WHERE 条件的时候,即使还是有很多 ROW,但是这些 ROW 的第一列索引都是相同的,所以我们在选择第二列的数据的时候依然可以命中 date_of_birth 的索引。

简单来说,就是建立多列索引的时候,将需要用 = 查询的列的索引放在最左侧,RANGE 搜索的列往后放。

LIKE 查询

LIKE 可能使用索引,也可能不使用,通配符的位置很重要。

因为索引是按照字符串对比来建立的,所以很显然,% 并不能用于索引匹配。简单来说,% 之前的内容会通过索引 access,% 开始就不会了。

比如下面这个例子:

Postgres 的查询计划如下:

% 开始就要 RANGE SCAN 了,所以 % 放的越往后越好。

% 不同的几个位置的查询对比:

如果 % 在很前面,要 INDEX RANGE SCAN 一大部分数据的话,那就没有 TABLE SCAN 快了。所以优化器要决定是否走索引。

当使用上文提到的 Bind Parameters 的时候,就比较麻烦了。因为优化器并不知道传进来的 LIKE 参数,% 在什么地方。大多数数据库在这种情况下都假设 % 不会出现在开头的地方,从而使用索引。如果需要全文查询的话,只能不使用 Bind Parameters,自己拼接 SQL 查询了。但是这样优化器的成本要高一些,并且用户需要自己防止 SQL 注入。但是 Postgres 数据库除外,Postgres 假设 % 会出现在前面,从而不使用索引。所以如果是 PG 的话,要走索引才需要拼接 SQL。不同的数据库有不同的行为,这个时候用执行计划确认一下最靠谱。

Index Merge

某些情况下,无论怎么建立索引都避免不了  RANGE SCAN,比如下面这个查询:

如果数据分布是平局的,那么对这两列建立索引的话,总是避免不要 RANGE SCAN 一大部分的数据。

这种情况其实分别对这两列建立索引更好。数据库会分别用两列的索引查出数据,然后将两个结果合并,这样就避免了大量的读表。

7. 部分索引

Postgres 和 Oracle 支持部分索引,这样有什么好处呢?

考虑实现一个任务队列,最常用的操作是从队列中取出未处理过的任务,而处理过的任务很少需要读。

因为这两个 WHERE 条件都是 = ,所以在这里索引的顺序无所谓。如果我们这样建立索引,是可以通过索引查询的。

考虑到我们要查询的目标行是 processed = 'N' 的,而这个表中大部分的数据都是已经处理过的,都不是我们要找的。那能否只对这部分数据建立索引呢?

这样只索引了一部分数据,查询未处理过的数据才会用到这个索引。另外注意到我们索引的字段也改变了,之前要索引 (receiver, processed) 两个字段,现在只索引 receiver 一个字段。因为索引本身已经包含一个信息:“使用索引查找的都是 processed = 'N' 的,这个字段也就不需要保存了。

综上,部分索引从两个维度节省了空间:

  1. 索引的行数变少了,只索引为处理过的;
  2. 索引的列变少了,因为被索引的都是未被处理过的数据;

其他一些不会使用索引的情况:

Date 类型

有些数据库(比如 Oracle ),没有 Date 类型,只有带 Time 的表示时间的类型。所以要查询日期的时候,常用的一个函数是 TRUNC,这个函数将时间部分设置为 Midnight。比如,查询昨天的销售额:

这个时候如果有 sale_date 的索引的话,是不会使用的。原因在上文 FBI 已经介绍个过了,函数对于数据库来说是个黑盒,不同的函数以为着不同的索引。

解决方法是使用 TRUNC 函数建立 FBI。或者直接指定查询范围到时间精度。但是要注意,BETWEEN 包含查询边界,所以这里手动拼接 SQL 的时间范围话,一定是从开始时间,到下一天的时间减去 1 个最小的时间精度单位。

以下是用 Postgres 实现的一个例子:

当然,更准确的一种方法是在应用的代码内拼接 SQL 的时间边界。或者不要用 BETWEEN,用 >= start_date AND < end_date.

数字和字符串

原理类似的,数据数据库用字符创(TEXT, VARCHAR)来保存数字的话(当然这是一个 bad practice),那么查询的时候也要格外小心。

这样查询,是走不到索引的。

原理是数据库发现要查的 = 的值,和数据库里面的列值是不一样的,就会进行隐式的类型转换,效果其实类似下面这样:

如此,就和我们前面提到过的 FBI 一样,函数对于优化器来说是一个黑盒的存在,所以优化器会决定 TABLE SCAN。

要解决这个问题也很简单,只要避免隐式的类型转换(避免使用函数就好了)。我们在查询的时候就转换好类型。

使用冗余的 where 语句暗示走索引

有时候我们要结合多列来查询,举个简单的例子,比如一列存了日期,一列存了时间,查询过去 24 小时的数据,需要以下的 SQL:

这个查询显然是无法使用任何一列的索引的。当然,最好是将时间和日期存到一列中,但是在修改表结构比较麻烦的情况下,我们可以想办法让这个查询走索引(即使是部分索引)。

这里的技巧是多使用一个 where,优化器会决定先用索引过滤出一部分数据,然后再扫表。

类似的技巧也可以用在 Bind Parameters 上。

还记得下面这个查询吗?

由于事先不知道这两列的分布情况,所以优化器无法做出选择。但是假如我们知道 LIKE 总是会有 % 的话,我们可以用一个 trick 暗示优化器不要走索引。

虽然和一个空字符串连接是冗余的,但是优化器会因为这个,不考虑 last_name 这一列的索引。

Smart Logic

SQL 强大的一个功能是支持嵌套查询。这个功能之所以可能,是因为优化器是作用在运行时,可以动态的给出查询计划。但是每次选择查询计划也带来了开销,这个开销可以使用 Bind Parameter 来解决。

有一个常见的错误,是想用静态 SQL 来替代动态 SQL。

举下面的例子,假设有一个表,这个表的三列中任何一列都可能用于查询。有人就想出用下面这个 SQL 代替:

这个静态 SQL,可以实现使用三列中的任何一(二/三都可)查询,只要将其他没有用到的列设置为 NULL 就好。

但是优化器在面对这个 SQL 的时候,只能按照最坏的 Case 准备,所以它做出的选择是扫全表。

所以最好的使用方式,应该 SQL 中只写用到的 filter:

The most reliable method for arriving at the best execution plan is to avoid unnecessary filters in the SQL statement.

Math

最后一个经常引起误解的带有数学计算的 SQL,考虑下面这个 SQL,能使用索引嘛?

下面这个呢?

如果换个角度考虑问题,如果你是一个数据库开发者,你会在你的数据库里面加一个计算器吗?大多数的回答,都是 No。所以以上两个查询都无法使用索引。

类似的,为了暗示优化器不要使用索引,你可以在查询中加0.

如果必须要用的话,可以使用 FBI 对这个表达式创建索引。

 

 

IRedis开发记3:编译正则的难题

这篇文章是 IRedis 的第三篇开发笔记。一直以来,IRedis 的补全都是基于 prompt_toolkit 的 regular_language 来实现的(一个例子)。我需要用正则表达式来验证用户输入的 Redis 命令是否合法,从中抓出来 token,然后对这些 token 进行自动补全。随着开发,支持的 Redis 的命令越来越多,这个正则表达式已经膨胀到 200+ 行了,编译速度也令人难以忍受。

这个问题困扰了我将近3个月,我尝试过各种各样的方法,从身边的朋友那里听取不同的思路和建议,终于在最近近乎完美地解决了这个问题。以至于兴奋的睡不着觉。

这篇文章分享一下这个问题,为了解决这个问题尝试过的方案,以及最终采用的方案的工作原理。读者从这个问题和方案本身可能并不会学到什么可以 Take away 的东西,因为很难在遇到这种问题(这也是这个问题比较难解决的原因之一)。但是我更想分享一下解决的思路,以及它带给我的启发。可能对于将来的我,再回来看的时候,会发现解决问题是如此美妙的一个过程,编程本身又是多么充满乐趣的事情。

问题:用正则来匹配输入……

为了接下来的讨论,我先描述一下我面临的问题。

我要写一个 Redis 命令行的客户端,支持对 Redis 命令的自动补全。(相关文章 IRedis 开发记录:Redis 命令语法的处理 )。但是我不会从头开始写这个命令行客户端的输入输出,而是选择了 IPython 和 mycli/pgcli 都用的一个库:prompt_toolkit. 它是用了 Python 的正则表达式的 named group 功能,从输入的内容中抓出来 token。比如这个例子中,语法的正则是这么写的:

当输入 abc  (注意后面有个空格)的时候,abc 就匹配到了 <operator1> ,然后空格匹配到了 \s+ ,框架就知道后面要输入的是一个 var1 了。

类似的,我写的 Redis 的命令节选如下:

因为 Redis 的命令不像 SQL 那样是结构化的语法,每个数据类型的命令格式都不一样,所以写起来要用或 | 将这些语法都连接起来。

另外还要补充一点的是,我写的这个正则并不是直接拿去匹配用户输入了,因为框架需要知道这个 token 的下一个 token 可能是什么,以此来做自动补全的提示。所以其实我的这个正则是交给框架去解析了,而不是直接 re.compile() 。框架会将这个正则拆散,然后一个一个编译。这一点也导致了后面会讲到的一些方案行不通。

另另外要补充的是,不光是拆开这些正则就可以了,如果这样到好了,也就是不到 100 个正则,编译一下也是很快的。作为用来匹配用户输入的问题是,即使用户只输入了一部分,也应该认为是合法的。比如正则是要匹配 SET 命令,而用户输入了 SE,那么也应该认为这是一个合法输入,而不应该显示成下图这样的非法提示。

那么怎么做到这一点呢?这个框架的方案是解析正则,然后分析出更多的正则来匹配部分输入。比如 SET,那么根据此应该生成 SET|SE|S,看起来也不复杂,但是如果支持的参数越来越多,需要编译的正则的数量将会呈指数级上涨。

举个简单的例子,下面这个语法:

最终生成的正则是这样子:

这就很恐怖了。

当 IRedis 支持 Redis-server 的 197 个命令语法的时候,需要编译的正则已经达到了 ~8000 个。IRedis 启动的时候需要等待 ~8s 编译正则完成。

这就是问题了。作为一个命令行客户端(对比一下 mysql/redis-cli/mongo 这种客户端),需要等待 8s 才能使用,是非常影响体验的。

缓兵之计:异步线程加载

这个问题没解决之前,我将这些正则的编译改到了一个 daemon 线程中去编译(这个PR)。在编译结束之前,最下方的 bottom-bar 会显示一个 ascii 动画提示正在编译,并且 Lexer 高亮,补全这些功能都没有激活,像一个 redis-cli 那样只有基本的功能。

但是这段时间 CPU 在不停的做正则编译,占用量会很高。以及用户体验也有影响,相比 redis-cli 秒开,太伤了。

 

如果要从根本上解决这个问题,现在看来有以下几个思路:

  1. 能否缓存下来正则,不要每次都编译?
  2. 能不能替换掉编译正则的方案?
  3. 能否加速正则的编译?
  4. 减少需要编译的正则的数量;
  5. 不要一下子编译好所有的正则,用到哪个编译那个。

尝试1:缓存正则

这是一个比较直觉的方案。我尝试过用 pickle/dill (应该还尝试过一个,不过名字忘记了)。发现 dump 出来,下次启动直接 load,从方案上是可行的。但是速度依然很慢。后来发现 pickle 只是去打包一个对象的 __init__ 参数,当 load 的时候,再用类初始化一次(这样对于大部分 pickle 的使用场景来说是合理的)。所以还是相当于编译了一次。(资料

理论上,直接缓存 C 语言层面的 regex 编译结果也是可行的,但是会遇到 Python 跨版本不兼容的问题,因为这部分并没有公开的 API,所以没有人能保证它的兼容性。

我觉得这将会是一个大坑,所以没有继续沿着这条路走下去了。

尝试2:另寻没有正则的方案

老实说,用正则来处理语法并不是很好。比如 Redis 的命令有一些是下面的这种语法,而这种是无法用正则来表达的:

ZINTERSTORE 这个命令 后面有个 numkeys 表示后面紧跟着几个 key,然后再是 WEIGHTS。只有知道了 key 的数量,才不会将 WEIGHT 也作为 一个 key。而正则是不支持从前面解析出来数字然后应用到后面的 match 中的。

于是我想拿 pygments 来做一个基于状态机的 Grammar。参考 这个PR。理论上是可行的,但是并没有最终采用这个方案。原因是工作量太大了。如果我直接用正则,那么我可以用 prompt_toolkit 框架中的一些补全,Lexer。否则的话,我就要重写 Grammar,match 前缀的逻辑,Lexer,判断下一个 token 可能是什么来推测补全列表。相当于另外写一个 prompt_toolkit 了。所以这条路也放弃了。

Jonath(prompt_toolkit的作者)建议过我用状态机实现,这个方案同样也是工作量太大。本来 IRedis 就是因为另一个项目而生的,我不太想因为 IRedis 要先去完成另一外一个新的项目 :)

尝试3:编译更快的正则

这个方案比较好理解,Python 的 re 比较慢,能否用更快的 re 来替换呢。Python monkey patch 比较简单,我只要将系统 buildin 的那个 re 替换掉就好了。大部分其他 re 的库也是兼容 buildin re 的 API的。

我尝试过的库有:

  1. google 的 re2
  2. Rust 写的 rure
  3. Python 的 regex

效果不是很好,原因很简单:这些库可能在一些情况下编译正则的速度快一些。但是我这里的问题并不是编译一个正则太慢,而是要编译的正则太多。对于 8000 个正则来说,就算能快上一倍,效果也不明显的。

尝试4:减少编译正则的数量

guyskky 提到可以将正则 merge 一下,类似 werkzeug 处理 URL 的方式(werkzeug.routing.Rule.compile)。我觉得这个比较可行,但是还没有尝试。

但是跟 Jonath 讨论之后,Jonath 开始优化这一块正则的 merge,这个 PR 到我写这篇文章的时候,已经 work 了。

经过优化之后,需要正则的数量降低到了 496 个,1.7s 就可以编译完成。

尝试5:即时编译

上面的方案4是一个治本的方案,但是在我这个方案之前,我并不是方案4是不是可行的(因为对 prompt_toolkit 读的代码不多),所以我上周用“即时编译”的思路进行了重构。

这个想法很简单:既然启动的时候编译那么多正则表达式很慢,那么我为什么要一开始就全部编译好呢?用到哪一个再编译哪一个不就好了吗?

比如用户输入了 KEYS 那么我就编译好 KEYS 的语法,然后将当前的语法替换成这个。当用户输入了 GET,我再编译 GET 的语法并进行替换。

能够这么做基于两点:

  1. Python 在运行时动态地替换一个对象的属性非常简单,并且我这个 client 也是单线程的,不会存在线程安全问题;
  2. Redis 的不同命令的语法都是独立的,不像 SQL 那样,你不能只编译一部分。当然,问题的根源也是它。

核心代码是下面这个 Processor,Processor 是框架的一个概念,每次用户按下什么键都会执行。

核心代码是 24-27 行,当用户输入的命令匹配到 Redis 命令了,就替换当前的 Lexer 和 Completer。

这样问题就完美的解决了,当然还有一些细节问题。

比如当用户输入了一个命令语法比较复杂的时候,会感觉到一点卡顿,因为在编译正则。我在编译的函数上加个一个装饰器 @lru_cache(maxsize=256) ,将编译结果直接缓存下来,这样只在第一次输入的时候会卡,后面就好多了。

等 prompt_toolkit 那个 PR 合并,配合我修改的“即时编译”,这个问题就算完美的解决了。

 

解决这个问题,大概花了 3 个月。但是最终解决的那一刻,感觉真的很奇妙。这件事情给我一些很强烈的感受:

  1. 编程这件事情本身,我是说就算没有带来任何名誉、财富上的收获,也实在太有意思了;
  2. Python 社区的人太好了,除了 Jonath 给我很多很多建议,Dbcli 的 amjith 还和我视频通话,跟我说他之前也想做一个 redis 的 cli,跟我说了一些他的想法,非常有用。此外还得到了很多很多其他人的帮助和建议。Python 社区很温暖!
  3. 用 Python 编程太快乐了!比如本文的 @lru_cache ,这一行能完美解决问题!IRedis 项目中,我遇到了很多类似的体验,我打算单独写一篇文章讨论这个。

Happy hacking!

 

2019年年鉴

这一年不知不觉又过去了,一年很长,但是到了年底,能回忆起来的事情不多。今年没有什么大事发生,还是一如既往的工作,生活。这篇文章,就来回忆一下今年的屈指可数的收获吧。本质上我写这篇文章是出于习惯,所以你阅读本文基本上不会有什么收获,建议不要浪费这个时间。:)

要说进步,今年值得表扬自己的是,一些存了很久的疑问,今年逐渐一个一个给了自己满意的回答,比如 Linux 分区是什么工作的文件系统是什么工作的,什么是 Daemon 进程等等(写了这么多 Linux 的文章,感觉这个博客需要开一个 Linux 分类了)。以及一些由于不明白而困扰自己的很幼稚的问题。这些答案基本上都来自 Linux System Programming 这本书,细说起来这本书是从 5 月份就开始读的,快到年底了才读完。如果你和我一样对于 Linux 有很多懵懂的问题的话,也推荐你读一下这本书。上一次给我这么大启发的书,还是 Fluent Python 了。作者(Family Name 竟然就叫 Love)具有丰富的 Kernel 开发经验,解释问题比较深入浅出。缺点就是书中解释各种 Error 含义的篇幅有点过多了,都是手册里面的内容,感觉有凑字数之嫌。

除了 Linux,今年还看了一下 Scheme(The Little Scheme)和 Elixir (The little Elixir & OTP Guidebook-Manning)这两本书,都是入门级别的。这两门语言和 Python 有很大的不同,比如 Elixir 有模式匹配,函数内可以写 when 来检查参数,Atom 的类型等等,也给我一些启发。

工作

今年上半年还是一种很不好的工作状态,每天的工作中,和同事沟通占用了大部分的时间,SRE 像是一个技术支持的工作,不断的协调,和不同的部分解释沟通等等。手里同时会被分好几件事,分身乏术。客观上说,总是感觉自己的工作没有意义,学到的东西也不多。

下半年组织结构调整,被调到了另一个组,做一个定位系统故障的系统。简单来说,就是业务不正常了,我们开发的这个系统要能自动定位到是一台机器的问题,还是一个机房的问题,还是数据库的问题,给应急提供一些辅助信息。项目语言是 Java 写的。因为我在之前的组中也尝试过这种定位系统,没有特别明显的结果,之前公司中失败的案例也不少,所以一开始对这个项目是没有信心的。但是做了半年,逐渐有效果了,有一些思路可以自己实现,觉得还是能取到一些成果了。

说来可笑,这几乎是入职以来,第一次能够专心写代码的时候。虽然到底要怎么做还不是很清晰,很多地方要自己摸索,但是工作状态相比之前是好了很多。

另外我们组是用 Java 来开发的,这门语言挑战了我的认知。我写 Python 的时候,每一行代码我都知道是做什么的,现在写的 Java,有很多代码看起来匪夷所思。比如 NPE,像 Python,JavaScript,如果你从 None/Undefined 试图获得一个属性,这些语言都会提示你 xxx 并没有这个属性。Java 呢?NPE。foo.getA().getB().getC(),NPE;call(foo.getA(), bar.getB()) 每当看到 NPE 这个错误的时候都让人痛苦万分,我要为这个简单的错误花很长的时间复现、排查。类似的例子还有很多。

总体上说,我觉得用 Java 开发项目的这段时间,我并没有因为这门语言学到什么启发性的东西(不像Elixir,Scheme)。在我看来,很多 Java 里面才有的东西是纯粹为了 Java 语言本身的问题,放到其他语言上很可能不需要这么做。我这么想也可能是我对这门语言学习的不深,使用的时间不长。以后这个想法也可能改变。

开源和社区

捕蛇者说。这是今年做的一件事,由 laike9m 发起的。Adam,Manjusaka 我们几个人一拍即合,就开始搞了。搞起来网站,在 V2EX Twitter 发了几个帖子宣传,然后开始录制,剪辑。现在看来这件事情是比较可持续发展的,除了剪辑的工作外,不会太让人疲惫,应该不会像 HZPUG 那样一直鸽掉了。今年一共录制了 10 期,感觉还会有源源不断的话题,接下来一年的发展我比较有信心。这件事情对我来说,最大的收获是结交的朋友了,要说学到什么,可能没有读书那样性价比更高。大家交流更多的是一些软性的东西,可以让你知道这么做一件事对不对,一条路是不是对的,类似这样。

PyCon。今年在 PyCon 做了两次演讲,个人觉得,内容比较浅薄。但是后来经常有人跟我说 Migration 那个演讲很好,还有人跟我讨论他们公司的 Migration 的一些方案,很高兴。

开源项目。业余时间,今年主要在做两件事情。第一个是 clock.sh(尚存在一些问题,个人认为还没有到稳定阶段,但是大家可以试用) 。这个项目就是想托管一些个人的定时脚本,没有很大的野心,做一个个人的 Saas,小而美,就够了。至于这个项目的最开始的动力,其实是我之前写爬虫的时候,我们有一个项目叫 xxx-control,里面有一个很长的 crontab 文件,用来管理爬虫什么时候启动执行,那时候我就想有一个更友好的定时任务控制的平台。这个项目我一直按照我的想法去做,半年之前有一个可用的 demo 版本,能通过在网页上简单的点击记下,就设定好一个定时任务了。后面有些慢 SQL 的问题,以及支持自定义 Docker 镜像的问题,一直没有时间解决。

第二个项目是 IRedis,这个是由于第一个项目用 Redis 作为 broker,而我又不太熟悉 Redis 那么多命令。所以就像要一个像 mycli/pgcli 那样的命令行工具。于是就自己开始写了一些。陆陆续续地,IRedis 支持的命令也越来越多,希望能在这个项目1周年的时候发布 1.0 版本。

我的第二个项目是为了解决第一个项目的问题而诞生的,此外还因为用到一些第三方库有问题,去给他们提交了一些 Pull Request。其实今年还有很多很好玩的想法, 精力有限,只能放弃那一些了,先把已经开始的项目做好。

工作上比较忙,正常晚上到家就10点了,所以自己的想法一直苦于没有时间去实现。现在的工作方式比较不健康,我还是想有一个正常的作息时间。

其实这么长的工作时间对公司来说,也未必是一件好事。依我个人看,会减少我对工作的热情,阻碍员工的发展。一周工作 40 个小时的时候,我还是盼望着上班的。太长的工作时间,客观上看,大部分时间也都被没有意义的事情给浪费了。另外很多公司不明白的一件事情是,如果给员工提供的是这样一种环境,那么大部分人的想法将会是不会在这一家公司工作很久,等自己能力提高立马换一家工作和生活更平衡的公司。如果没有时间学习(个人认为真正能学到新的技能的工作岗位很少),那么员工的价值也不会提高。为什么这些公司可以花很多钱从外面招厉害的人,而不愿意培养自己的员工成为那样的人呢?

如果我将来开一家公司,我一定不会认为工作时间长的员工是好员工。相反,我会看他们是否对技术有热情,是否有对自己不了解的事情有求知的渴望,无论这些事情是古老的技术还是新潮的技术。对于刚毕业的学生,一定要想办法减少他们花在没有意义的工作上的时间,一定要有至少20%的工作上的时间自由支配用于学习,一定不要给他们灌输:程序员必须学管理,程序员的“软技能”很重要,以及鸡汤。健康、可持续的生活和工作方式,比焦虑,没有意义的努力和长时间的工作要好一些。

未来的打算

  • 今年一年看的好代码太少了,需要学习一下 debug 工具链,多阅读好的代码;
  • 掌握 Elixir,我觉得这门语言很不一样,尤其是自带 supervisor,9 个 9 的可用率,比较吸引我;
  • 了解更多有关分布式系统,数据库的内容;
  • 锻炼身体,改善生活方式;

 

往年:

  1. 2013年
  2. 2014年
  3. 2015年
  4. 2016年
  5. 2017年
  6. 2018年
 

Daemon Process

本文介绍一个从 Linux 的 shell 诞生的进程,要经历怎样的“考验”,才能成为一个 daemon 进程。

后台进程,顾明思议,在后台执行,没有终端,没有 Login shell。当某些 Event 发生的时候进行处理,或者定期执行某项任务。通常,daemon 进程以 d 结尾,但不是必须的,比如 Redis 和 Nginx 的 daemon 进程就没有以 d 结尾。 简单来说,daemon 需要具备以下两项基本条件:

  1. 是 init 进程的子进程;
  2. 没有连接到任何 terminal;

此外,daemon 进程通常还会做以下几个事情:

  • 关闭所有的 file descriptors,尤其是 input output error。因为这些 file descriptors 可能是 shell,或者其他进程。而后台进程最关键的就是不连接 shell 和 terminal。可以使用 open_maxgetrlimit syscall 获取当前打开的最大的文件描述符,依次关闭。也可以遍历 /proc/self/fd 下的文件,依次关闭。
  • 将 working directory 切换到 / 目录。daemon 的生命周期一般伴随整个操作系统的工作时间,如果一直在继承自父进程的 working directory 工作的话,就会影响操作系统运行期间的文件系统 mount 操作。某些进程也可以切换到自己的特定目录工作;
  • 将 umask 置为默认值,通常为 0。因为 daemon 进程创建文件的时候,会想自己设置文件的权限,而不受 umask 的干扰。如果使用的第三方库的话,daemon 可以自己设置 umask 的值,自己限制使用的第三方库的权限;
  • 离开父进程的 process group,这样就不会收到 SIGHUP 信号;
  • 离开 controling terminal,并确保以后也不会再被重新分配到;
  • 处理 SIGCLD 信号;
  • 将 stdin stdout stderror 重定向到 /dev/null。因为后台运行的进程不需要用户输入,也没有标准输出。这样也可以确保当其他用户 login shell 的时候,不会看到 daemon 的输出。

这是 daemon 进程通常会做的事情,man 7 daemon 中有更详细的描述。 接下来,主要讨论 daemon 最精彩的部分,即如何通过两次 fork() 来完成脱离 terminal。

两次 fork()

前面介绍了一些比较简单的处理,比如 chdir,reset umask。接下来讨论如何脱离 terminal。

为了方便读者理解,我先画一张图,并标出每一步动作发生了哪些变化,然后再具体解释。

Shell 创建进程。1)pid 是什么?kernel 会分配一个 pid。2)ppid 是什么?创建此进程的进程,即父进程,这里就是 shell 的 pid。sid 是什么?3)sid 指的是 session id,本文不作过多介绍,读者可以认为是和 shell 在一组 session 的进程,这样 shell 退出的时候会给 session leader id 为 shell id 的进程都发送 SIGHUP,将自己产生的子进程都一并退出,方便管理。所以,新创建进程的 sid 也是 shell pid,自动加入 shell 的 session。4)pgid 是什么?pgid 是 process group id,是一组进程id。考虑这种命令:grep GET accessl.log | awk '{print $1}' | sort | uniq ,如果我们想结束这个命令的时候,不会想 grep,awk.. 这样一个一个的结束,而是想将他们全部结束。为了方便管理,shell 会将这种管道连接的进程置为一组,这样可以通过 pgid 一并结束,方便管理。所以,新创建的进程的 pgid 是自己,它自己也叫做 group leader。

第一次 fork()。 调用 fork(),父进程立即退出(为了方便后续讨论,我们将这次的子进程称为 child1)。这里的作用有3个:首先,进程是从 shell 启动的,如果进程不结束,那么 shell 的命令行将 block 在这里,这一次 fork() 让 shell 认为父进程已经正常结束了。其次,child1 fork 出来的时候,默认加入了父进程的 progress group,这让 child1 不再是一个 group leader(它的 pgid 不等于 pid),这是调用 setsid 的必备条件。实际上,由于父进程退出,child1 所在的 process group 已经是一个 Orphaned Process Group。第三,由于父进程已经退出,所以 child1 的父进程是 init 进程。

setsid。由于 child 的 sid 依然是 shell 的 id,所以当 shell 退出的时候依然会被带走。所以这里要调用 setsid ,脱离 shell 所在的 session。但是 setsid 之后,它的 pgid 和 sid 都等于它的 pid 了,这意味着它成为了 session leader 和 group leader。这其实就是为什么要 fork 第二次的原因,也是我最大的困惑,和花了最多时间去理解的地方。

第二次 fork() 。为什么要第二次 fork() ?这个问题我读了很多不正确的 Stack Overflow 讨论,以及没有第二次 fork() 的实现,比如 Linux System Programming 5.7 Daemons 中的 daemon 代码就是没有第二次 fork() 的,Kernel 提供的 man 3 daemon 也没有第二次 fork。需要做第二次 fork() 的原因很简单:如果一个进程是 session leader,那么它依然有机会获得 tty 的(在基于 SysV 的系统下),我们要确保它不可能获得 tty,就再 fork() 一次,并且退出 child1,确保最终提供 daemon 服务的 child2 不是一个 session leader。

这个过程也可以看下  daemonize 里面的 daemon 函数,和上述过程一样。

 

我写了一段代码演示两次 fork() 各种 pid 的变化,得到的结果会和上图一样。

运行结果如下:

Protocol Mismatch

如果使用 systemd 这种任务控制机制的话,注意需要按照这些系统规定的 readiness protocol 来设定你的程序,即你要可以将 chd