幻读

Posted on by Leave a comment

数据库的事务应该保证隔离性，这就是说，两个用户（连接）在操作数据库的时候，它们之间的操作应该互相不受影响的。比如用户 A 在修改了 foo 这个变量，但是还没有提交，那么 B 不应该看到这个修改。

但是隔离性的时间不是一件简单的时间，隔离性保证的越高，要么实现的技术手段越复杂，要么性能很低。因为很显然，避免多个事务之间互相影响，就必然要通过加锁来同步操作。如果想要更高的性能，就必须要加更加细粒度的锁，或者使用无锁（更加复杂）的技术来实现。

隔离性一般有这几个问题：

  1. 读到了未提交的数据。这个比较好理解，也比较好解决。一般加锁就行。
  2. 在同一个事务中，两次读到的数据不一样。比如用户 A 开始了一个事务，查询了 foo，这时候用户 B 修改了 foo 并且提交了，然后 A 在事务中又查询了 foo，发现和上一次查询不一样。这也违反了“隔离性”，但是读到的数据却的确是已经提交的数据。这就是“不可重复读”问题。现在用 MVCC 的方式解决，大体意思就是一个事务开始的时候记一个版本（时间戳）v1，其他人所有的操作都会带上新的版本（时间戳），那么在这个事务中，所看到的所有的数据都是先于 v1 的，所有在 v1 之后提交的数据都看不到。MVCC 有一些 tricky 的地方，比如要删除数据的时候，不能直接删除，因为删除了的话，对于所有的事务（即使是在删除操作 commit 之前开始的事务）来说都看不到了。为了解决这个问题，需要在要删除的对象上标记一个新的版本，记为删除。这样之前的事务看到这个数据的时候，发现删除操作是在自己的事务版本之后的，就仍然可以读到这个对象。这样，就可以解决了同一个事务中读到的数据不一样的问题。（但这样其实会带来新的问题，比如数据标记新的版本了，那么索引要不要标记呢？索引怎么做隔离？比如 PostgresSQL 的 COUNT 其实不是一个 O(1) 的操作，而是要遍历每一行数据，检查数据对当前的事务是否是可见的。
  3. 幻读。上面说这么多，主要是给这个问题做铺垫，我觉得这个问题最有意思了。本文下面会主要讲讲幻读。

假设这么一种情况：一家医院规定必须至少有 1 名医生在值班，某天值班医生 A 和 B 感到不舒服想请假，按照系统的要求，不能让 A 和 B 同事请假成功的。如果我们使用的数据库没有解决了幻读的问题，那么即使解决了“重复读”问题，也是不正确的。考虑下面这种情况：

这样两人都会同时请假成功。

这个问题并不是“不可重复读”问题，因为两个事务看到的正是事务开头的数据。这个竞争条件产生的根本原因是，这两个事务互相依赖了别的对象，但是别的对象又被更改了。

在这种情况中，我们可以锁住所有的对象，强制他们只能一个接一个的执行。

再举一个幻读的例子：抢占会议室。

抢占程序是这样的，先检查会议室 R 在 某一天 12:00 有没有被抢占，如果没有的话，就可以抢占。那么假如两个事务同时发起的话，就同时看到这个会议室并没有被抢占，就会错误地被抢占两次。被抢占两次的 SQL 过程如下：

这个问题我们也可以通过加锁来解决：将不存在的锁转换成已经存在的。比如，只允许抢占 7 天内的会议室，并且以小时为单位进行抢占。然后就可以将 7 天内的每一个小时作为一个锁，要抢占这个会议室就必须先获得锁。

另外有一些问题不容易实例化不存在的锁。比如注册系统，不允许同一个用户名字被注册两次。但是这种情况可以用数据库的 unique 约束来解决。

不太好解决的问题，防止双重开支。支付系统要保证用户支付的钱不能大于自己的余额，不然公司要倒闭了。那么付款的事务中，我们先检查一下余额是否足够，然后在发起支付，这样可以吗？如果用户同时用电脑付款，也用手机付款，会不会在同一个事务中提交两次呢？

这些问题都有一种共同的模式：

  1. 执行一个 select 查询；
  2. 根据 1 的查询结果，判断当前的操作是否能够继续；
  3. 如果能，就继续，但是这个操作会改变 1 的结果；

因为事务进入的时候 2 都是检查通过的，但是都执行了 3，会影响彼此的 1 的结果，导致出现竞争条件。这就是幻读。

除了“强行加锁”，即上文中提到的方法以外。最靠谱的是使用串行化的隔离级别，即对于程序员来说，数据库好像在串行地一个一个执行事务，这样永远不会有竞争条件。但是因为性能问题，串行化很少使用。

 

注：本文内容大多数都阅读 DDIA 第七章的笔记。

 

Redis 的命令设计

Posted on by 3 Comments

很多人都知道，Redis 对代码上简单有一种极致的追求，比如坚持命令处理单线程。我在很多用户层面的配置和命令中，也看到了这种简单而优雅。比如 SAVE 的参数，save 900 1 表示 900 秒内有一次写，就执行备份，这样可以配置多条配置，就可以达到即可以根据时间配置备份频率，又可以根据写入次数配置频率。

又比如 ACL 的设计，虽然不能说设计的特别简单，但是功能非常丰富，即可以根据 key 来设置权限，又可以根据命令来设置权限，并且既可以设置白名单，又可以设置黑名单。单单来说白名单与黑名单，我见过很多系统，只要涉及这两个概念，就会让用户一头雾水了。如果我有一个A是在黑名单中，然后A里面的X在白名单中，那么X到底会不会生效呢？然后你就必须去看它的实现才知道是怎么样一个逻辑。（比如 poetry 对文件的 include 和 exclude 配置，就是一个反例）但是 Redis 的 ACL 设计，用了类似 DSL 的方式，一点歧义都没有。

但是 KeyDB 中说，Antirez 对代码库的简单要求的太过分了，以至于将很多复杂留给了用户。在 Redis 命令设计方面，我有类似的感受。甚至对于有一些命令的设计上，我认为并没有设计的取舍，纯粹是不知道为啥就设计成了这个样子。

这篇文档就来说说我对 Redis 中那些理解不能的设计。首先声明，这都是我个人无法理解，也可能它有它的道理，只是我不知道，如果你知道这个设计的道理，麻烦在评论中告诉我。

第一个想到的就是，为什么命令会允许有空格？

在 RESP 协议中，是用首位标志指示后面的 String 的，假如我用 RESP 将 set foo bar 打包发出去，那么我实际上发出去的就是（以下输出用这个脚本抓到的）：

这里 => 表示发出去的内容，<= 表示收到的内容，这是抓包脚本添加的。*3 表示后面会发送 3 个 token，$3 表示接下来的字符串长度是 3.

假如命令中可以允许空的话，那么对于 client list 这个命令，实际发出去的就是：

可以看到，redis-cli 是将 client 和 list 分开作为两个 token 发送出去的，根本无法知道第一个“变量”一个命令，还是第一个变量+第二个变量是一个命令啊！对于一些要解析发送内容的场景来说很是头疼。

这个问题仔细想想，如果你用 Redis Module 来扩展 Redis 的功能的话，也会遇到的。比如你要实现一个 HELLOWORD RAND 命令怎么办？你没办法告诉 Redis说 “嘿！ 兄弟我实现的这个命令，你收到的时候要拿前两个参数作为命令名字，后面的参数才是命令参数，不要搞混了哦~”，因为 Redis Module 总不能连 Redis 去解析命令那部分代码也干涉吧（我不确定做不做得到，没有去看 Redis 这一部分的源代码，读者知道的话请赐教），我写个 Redis Module 就是想做个简单的功能，你不要对我要求太多！

所以怎么办呢？Redis 文档里面说，哥们你得这么写 HELLOWORLD.RAND. 你看这不就没空格了吗？我解析的时候总是拿第一个参数来解析就可以了。

我靠，凭什么只能你官方的命令防火，不能我 Module 的命令点个灯啊！

第二个问题，人格分裂。

在 Redis 中，有一些命令是需要接受 pair 的。比如 HSET，你可以同时设置多个键值对（since 4.0）：HSET foo bar hello world. 所以 HSET 的语法是 HSET key field value [field value ...] 。So far so good, no problem at all.

But，XREADGROUP 这个命令的语法是什么鬼？？？

为什么会有 key key ... id id ... 这种设计？？

假如我想写一个自动补全的客户端，在 key 这个 token 的时候，我没有任何办法知道，应该根据 key 来补全，还是要根据 id 来补全啊！ T T

第三个问题，一些命令的向后兼容。

这里说的是 AUTH，在 Redis5 之前，AUTH 的用法是 AUTH PASSWORD。但是自动 Redis6 增加了 ACL 开始，AUTH 支持两种用法：AUTH USERNAME PASSWORD 或者 AUTH PASSWORD.

我的痛苦非常简单，也非常痛。

我有一个超屌的功能，就是能在命令行中将一部分输入替换成 * （屌吧，至少我没见过任何一个命令行能够这么做，sudo 让你输密码的时候，你根本不知道输入了几位，如果不小心输错，只能按下 N 次 Delete）

但是现在，第一个参数可能是 USERNAME ，可能是 PASSWORD，我到底是隐藏呢？还是不隐藏呢？（好吧其实这个痛点对于大部分用户来说不痛，向后兼容了嘛，还挺好的！只有我哭晕在厕所）

 

PS: IRedis 即将支持 Redis 6~ 欢迎尝试

 

Use the Index, Luke! 笔记6：增删改的索引

Posted on by Leave a comment

前面我们讨论的都是查询语言，但是 SQL 不仅仅是查询，还需要修改数据。索引是完全冗余的数据，是用空间换时间的一种形式。对于修改数据来说，这就意味着不仅要修改表中的数据，还要修改索引中的数据，索引对修改数据来说会带来负面的性能影响。

Insert

Insert 语句几乎是唯一无法从索引获益的语句，因为 insert 没有 where 条件。

索引越多，insert 执行的就越慢。

在表中添加一条记录的过程如下：首先，在数据库中找一个地方放这条记录。在一般的 heap table 中，没有对 row 的顺序的要求，所以随便找一个空闲的 table block 放就可以了。基本上都是顺序写，速度很快。

但是如果有索引的话，必须要保证在索引中能找到这条数据，所以也要在索引中添加这条数据。

索引中的数据都是有顺序的，并且还要保证索引的 BTree 添加了这条记录之后还是平衡的。这个操作就慢很多。虽然数据库的索引本身可以帮助这个过程快速的找到这个记录所在的 block 位置，但是依然要查几（1-4）个block。

找到这个 block 之后，数据库需要确认这个 block 现在是否有足够的空间放这个记录，如果没有的话，就要将叶子节点分裂，将当前 block 的记录平均分在新老的叶子节点中，保持树的平衡。最糟糕的情况下，如果父节点这个时候也同时满了，就需要再来一次分裂。

下图是没有索引到有5个索引的情况下，插入的性能：

可以看到，在第一个索引出现的时候，性能相比没有索引下降了上千倍。随着索引的增加，性能在不断的下降。所以尽可能的复用索引也很重要。

那么什么索引都不建的情况下不是插入很快吗？但是没有是索引的话，这些数据几乎没办法使用，也就没什么价值了。即使 write-only log 表也有一个主键索引。

但是有一种情况，就是从其他的 SQL 系统 load 大量的数据的时候，暂时 drop 掉索引是一个加速数据加载的好方法。数据仓库里面这样操作比较常见。

Delete

Delete 可以受益于索引了，因为 delete 可以有 where 语句。所以我们在前文中讨论过的使用索引的场景，同样适用于 delete。（基本上就是索引可以用于 select 的地方都可以用于 delete）

找到了要删除的数据之后，就可以从 table 中删除这条数据，同 insert 一样，在 table 中删除之后，还要在 BTree 索引中执行删除。这一步操作和 insert 是一样的，在索引中删除之后可能要设计叶子节点的合并，是比较耗时的。所以随着索引越多，性能下降的跟上面 insert 那个图差不多。

Update

Update 操作同样需要更新索引，所以跟上 insert delete 差不多。

有一点不同的是，update 可能更多多列，可能更新一列，更新的列数更多，涉及需要更新的索引就越多。

显然，如果一列数据没有变，那我们就最好不要更新它。

这句话看起来是废话，但是很多 ORM 的 save() 操作，每次都会更新所有的属性的。比如 Hibernate，只有显示地关闭 dynamicUpdate 才不会每次都去更新。这一点格外重要。

一个保险的办法是在开发的时候打开 ORM 的真正执行的 SQL 日志，进行审计。

 

Use the Index, Luke! 笔记5：查询部分结果

Posted on by Leave a comment

上一篇笔记中降到了排序相关的索引技巧。排序经常和“取部分结果”这种用法结合。比如分页，我们只需要取 1 页数据来展示，如果需要读完所有的 row 然后取出来前 20 条作为 1 页展示的话，未免也太浪费资源了。在排好序的情况下，显然我们可以只读 20 rows 就直接返回，而不必读完整张表的数据。索引可以帮我们做到这一点。

Top N查询

我们需要某种 SQL 语法来告诉数据库只取前 N 条数据。SQL 对此并没有一个明确的标准。一方面是因为这并不是一个核心的 Feature，另一方面因为每个数据库对此都有了自己的实现。比如 MySQL 是 LIMIT N, pg 是 FETCH FIRST 10 ROWS ONLY, 也可以用 LIMIT.

Oracle 12c 之前，并没有 fetch first 的语法，但是我们可以用 rownum 来 work around.

我们知道，即使在有索引的情况下，优化器仍可能选择扫全表的方案。因为在要取出的 ROW 很多的时候，索引回表查数据比直接 SCAN 全表要慢。但是如果我们告诉优化器，只需要前10条，那么优化器就知道，即使是需要从索引回表，但只需要10条数据，回表也是要比不走索引扫表快很多的。

Oracle 对上面的查询计划如下。COUNT STOPKEY 会在达到需要的数量之后停止查询，立即返回结果。

这是在有合适的 order by 索引的情况下。假如没有 SALE_DATE 索引的话，就意义着这些记录是没有事先排好序的。即使我们取 Top 1 条记录，数据库也必须将此表全部排序，只有读完全表并排完序，才能将第一条结果返回。

Pipelined top N query 带来的不仅仅是性能的提升，还有水平扩展性。如果没有索引的话，我们每次取 Top N 都要读完全表排序，查 Top N 的速度是和表的大小成正比的，表越大，查询的速度越慢。而如果有索引的话，随着表不断增大，查询速度一直是 O(1) 的，会有很好的扩展性。

但实际上，即使有索引，查询 Top N 的效率是和要取的 N 正比的。查 Top 100 条数据比 Top 10 条要慢很多。

paging 的时候，这个问题尤为显著。比如我们要取第 5 页的数据，也要将前 5 页都读出来，然后丢弃前 4 页的数据，返回第 5 页的数据。

有一种分页的方法可以避免这种依次读 Top N 带来的性能问题；

分页技术

分页技术一般有两种。最常用的一种是需要从头读到第 N 页的数据，然后丢掉前几页的数据。

这种方法非常容易实现，甚至很多数据库都有一个专门的  keyword 来处理这种情况：offset. 在 Postgres 中，可以用下列的 SQL 取第二页的数据（每页有10条记录，跳过前10条记录）。

这种分页只需要 offset 就可以取回任意一页的数据，但是有两个显而易见的缺点：

  1. 分页会漂移。以为每次 offset 都是从头开始数的，假设从第一页跳到第二页的时候，恰好在第一页插入了一条数据，那么第一页的最后一条数据就会出现在第二页上。一个现实的例子是豆瓣，豆瓣是按照时间倒序分页的，我经常翻页到第二页的时候看到在第一页看到过的帖子；
  2. 第二个缺点就是性能问题。可以想象，每次都要从头开始读，那页数越大，那么要读的 Top N 就越多，效率也就越慢；

第二种分页技术可以完美地解决这两个问题：基于 seek 的分页。解释一下这个方法，这里没有第几页的概念了，而是用一个 where 条件来分页。从这个条件往后继续查 10 条记录。

举个例子，假设现在每一天只有一条销售记录，那么你可以用下面这条 SQL 查出来一页（10条）的销售记录（在 SALE_DATE 有索引的情况下）：

这里的 ? 上一页最后一条记录的时间。然后要查下一页的数据的话，继续将 ? 替换成这一页最后一条记录的时间即可。

这种方法的实现有几个要点需要注意：

  1. 必须要保证每次查询的结果是固定的顺序。显而易见，如果顺序不固定的话那么这个 Top N 是不可靠的。有一个陷阱是，可能你自己查了几次顺序都是固定的，但是上了生产顺序就不固定了，这是因为你看到的有序可能只是巧合，恰好是因为你本地的数据库每次用一样的 plan 来执行这个查询，到了服务器可能因为并行计算就出现乱序的情况。解决这个情况很简单，就是在排序的索引上添加固定的 column，比如 id；
  2. 基于此，查询下一页的时候要从上一页结束的地方开始，这也是比较 tricky 的地方。

接着上面的例子，假如不是一天只有一条销售记录了，那么我们可以创建这样的索引。

然后使用的查询语句如下：

当然，这个方法也不是没有缺点的。虽然可以解决第一种方法两个问题，但是 seek 方法本身的问题也很大：它只能按照一页一页的顺序查找，无法直接跳到某一页。但是对于现在很多应用（比如 Twitter）采用了无限滚动的方法，是比较实用的。

Window Function 也可以用来分页

Window Function 也可以基于索引分页。下面的查询：

这里按照排好序之后，按顺序分 ROW_NUMBER，然后限制 ROW_NUMBER 在 11 和 20 之间，同样可以使用索引。

查询计划如下：

但是生产中 Window Function 很少用，它真正的威力是在离线分析上。Window Function 功能很强大，值得好好读一读相关的文档。

 

近况更新

Posted on by 14 Comments

这是一篇碎碎念，最近有一些想法想分享一下，但是内容又比较简单，不适合写成一篇博客，twitter 又写不下，就一起写一篇博客好了。

首先是上个周做的有关命令行的分享，个人觉得比较满意吧，大家参与的热情也很高，提了不少问题，我自己想说的东西也都分享了。从另外两位讲师的分享中，我自己也学到很多东西。

命令行操作是一个程序员必备的技能。对我来说，写代码是我热爱的事情，我觉得要拿编程作为自己的饭碗（而不是焦虑着如何“在35岁之前转管理”），1）要不断学习新的技术；2）理解这些技术背后的原理更为重要，学习要学到精髓，技术一直在变，但是基本的原理（网络、容器、存储甚至机器学习等）几十年来的变化不大；3）要擅长使用自己的工具。第三点很容易被忽视，但是我觉得是程序员成长路上比较重要的一部分。如果你自己连自己的工具都用不溜，那你很难喜欢自己的编程工作。我见过一些蹩脚的程序员，解压 tar 包都要去网上下载一个解压工具。也难怪想方设法要转管理来脱离编程的“苦海”了。工具的使用不受重视的原因，有一点我觉得是技术氛围是比较受“面试官”导向的。比如面试喜欢问你读过什么源代码，就导致很多人读过各种牛逼项目的源代码，却连文档都没看完；比如面试喜欢问一些“JVM原理”，就造成候选人好像人人都是 Java 专家，却写不好 Java 代码；又比如很多人能回答上来 TCP 一些刁钻的问题，但是却不懂 TCP 的基本原理。面试中很少有人会问你工具如何使用，写一个命令行工具也远不如写一个xxx系统/中间件对面试官来说有吸引力，但是现实是，很多人连“将一个文件夹从一台服务器传到另一台”都做不好。

槽吐完了，流水账一下最近的工作和想法吧。

dbcli 放弃对 Python2 的支持

最近给 pgcli 放弃了对 Python2.7 3.4 3.5 。说实话 pgcli 到现在还能支持这些 Python 版本真够了不起了，但是 prompt-toolkit 3.0 支持的最小 Python 版本是 3.6，所以 pgcli 对这些 python 版本无法继续支持了。如果不升级 prompt-toolkit 到 3.0 的话，一些打包就会 broken。

我本来以为升级工作会很简单，删除这些 Python 版本的测试，添加对 3.8 的测试，然后升级依赖即可。但是遇到的坑实在太深了（可能是我太菜了）。三行代码花了我两个星期，push 了几十次（有些 commits 被 rebase 掉了）。

首先第一个坑是 CPR 的问题，之前以为 pexpect 的 terminal 是 dumb terminal，所以测试没有关闭 CPR 也一直没出过问题，但是升级 prompt-toolkit 这个问题暴露出来了。pexpect 应该是模拟了一个 shell，CPR 没被显式的关闭是有问题的。然后代码库里有个测试写错了，如果我关闭 CPR 这个测试还会挂掉，对发现这个问题的根因造成了极大的干扰。另外所有的测试在 mac 上是完全都能 pass 的，到 Linux 就出问题了（准确的说是在 travis-ci 的 Linux 会出问题，在我的虚拟 fedora 里面就不会），所以只能改代码 push ，让 travis 去测试，非常痛苦。

所以这三行代码背后有我巨大的工作量……

Coverage.py 4.5 对 Python 3.8 的 bug

我添加了 Python3.8 的测试之后，发现覆盖率神奇的下降了好多。一开始以为是 asyncio 的部分使得调度策略变了，导致一部分代码在测试的时候并没有运行？然后仔细看了一下并不是这样，coverage 生成的文件，竟然有一些代码是白色的，不是覆盖也不是未覆盖，成为 Phantom lines 了。然后查了一下，发现是 coverage.py 的问题。升级一下就 ok 了。

后来想了一下，对于已发布版本（向我们这样的）也无法加 warning 提示用户你用的是 Python3.8，只能发新版本，那么旧版本的用户总是会遇到这个坑，从这个 issue 也可以看到这个问题被 link 了无数次了。向前兼容好难啊！

IRedis 新的 feature

最近给 iredis 加 pager 的功能花了不少力气。要对所有的命令兼容 pager，然后要尊重系统的变量，比如 $LESS $PAGER等。prompt-toolkit 输出带颜色的 output 还无法 pipe 到 less，好烦。不过经过重构过一波代码，总算是实现了。再提一句，iredis 代码很多部分经过不同的人重构过，每一次都在变好了，单元测试功不可没啊！

Redis-py extend lock 可以直接接受新值

终于给 redis-py 的 lock 加上这个 feature 了。redis-py 的 lock.extend 语义一直让我很困惑。lock.extend(10) 的意思指的是，让 lock 的 timeout 变成“还剩下的 timeout + 10s”，这就导致我们在多数锁的场景下，这个锁的生命会越来越长，导致 fail over 的速度会来越长。（在这篇文章我有详细描述过）在 redbeat 里面我只能用一个新的 lua 脚本，来保持锁的最大超时时间总是 10s ，不会受之前剩下的 timeout 变得更加长寿。