如何正确实现分布式锁

Posted on by 15 Comments

分布式锁几乎是分布式系统中必备的一个组件，通常用在两个场景：

  1. 保证耗时的操作同一时间只有一个执行者，减少重复执行的时间；
  2. 保证一个共享资源同时只有一个修改者，防止竞争条件；

我在某些公众号看过好多讨论分布式锁的文章（在公众号里面好像是一个很热门的话题），但遗憾的是，我看过的这些实现里，或多或少都有问题。

一个分布式锁要求满足两点基本的条件：

  1. 同一时刻只有一个锁的持有者，不能出现两个进程同时持有锁的情况（safety）；
  2. 不能出现一个进程永远持有锁的情况（死锁）（liveness）；

在使用场景上，第一种场景（减少重复执行）对锁是弱依赖的，假如锁失去 safety，那么影响就是某个操作被多执行了几次；而第二种情况对锁的要求是强依赖的，如果锁没有 safety，就会面临数据不一致的严重后果。

最基本的实现

实现分布式锁，最基本的是有一个唯一的资源，支持 CAS 操作，最简单的实现如下面这样：

这也是本地环境中我们保护一个共享资源的方法。但是在分布式系统中，我们会遇到很多复杂的问题，比如获得锁之后，实例宕机了，这样它永远不会把锁还回来，造成了死锁。本地环境基本不需要考虑这种情况，因为线程退出一般会进行清理操作，在 finally 中释放锁；如果是整个进程 crash 了，那么连通锁、共享变量等就一起没了。

于是对于分布式的系统中，这些锁一般都需要带有一个“有效时间”，超过了这个时间，锁自动又变成了可获得的了（注意这一步是锁的提供者将锁过期的）。这就是常见的租期机制。

租期机制

租期机制解决了 liveness 的问题，但是带来了潜在的 safety 的问题。

因为在没有租期机制的情况下，如果原来锁的持有者不释放，那么锁是永远不会被再次 acquire 的。但是现在有了租期的机制，即使原来的进程还持有锁，但租期已经到了，那么锁就可以重新被 acquire。这样就有多个实例同时获得锁的可能性存在。

这就要求锁的持有者必须在锁的租期内完成事务，将锁释放。如果一个租期处理不完，那必须自己延长租期。

延长租期这里有一个细节，非常重要。就是延长租期的时候必须确认自己依然是锁的持有者。举个例子：现在有 A 和 B 两个实例，A 获得了锁，然后出现了网络问题掉线了，A 的租期超时，这时候 B 又成功获得了锁。A 的网络问题解决，重新上线，那么这时候我们就有了两个锁的持有者，A 和 B 同时续期。

这个问题其实很有意思，我在实际就遇到过这种情况：我用的一个定时调度器（Redbeat）为了保证高可用，采用了多个实例的同时运行的方法，然后通过一个分布式锁来保证只有一个获得锁的实例真正工作，然后此实例不断续期。如果这个实例没有续期成功，那其他实例就会获得锁开始工作。

Redbeat 的续期操作没有考虑检查锁的持有者问题，就导致可能出现多个持有者的情况，造成一个任务被执行两次。我在这个 issue 里面详细描述了这种情况和复现方法。

这个问题的解决方法很简单，就是我们在锁上面标志出目前锁的持有者，每次续期操作的时候都检查是否依然是持有者，如果不是，就失败掉续期，并且认为自己不再是锁的持有者（具体的一个实现参考下面）。在 Redbeat 里我提了一个 PR，先检查是否是锁的持有者再进行续期操作。

这样，锁的 liveness 还是有保证的，不会出现锁的持有者已经挂了，但是锁没有释放的问题；续期的机制也阻止了竞争者重复获得锁的问题。

以上都是分布式锁的经典实现，这些实现问题最多的其实是在锁的释放上。

锁的释放

对于提供 CAS 的系统，比如 Redis，我们一般用它的 SETNX 语义（如果 key 不存在则设置）来实现。释放锁的过程是删除这个 key，这样其他进程就可以获得锁了。

这种实现存在的典型问题是在释放的时候，没有检查自己是否仍是锁的持有者（本质上，和上面延长租期的时候要检查自己依然是锁的持有者，是一样的）。

考虑这样一种情况，存在进程A、B，A 获得了锁，然后出现网络问题，锁的租期过了之后 B 获得了锁。之后 A 重新上线，去释放锁，这时候 A 实际上释放了 B 的锁，造成可能有 C 重新获得锁，那么 B 和 C 就同时成为了锁的持有者。

锁的持有者标志方法

解决以上两个问题，就是标志出谁持有了锁，只有锁的当前持有者才能对锁做续期、释放等操作。

一种标致锁的持有者的方式是，设置的锁的时候将 value 设置为持有者的名字，比如 实例、进程、线程ID，不过考虑到 value 要唯一，实现起来可能有些复杂。

另一种方法是将锁的 value 设置成唯一的 token，获得锁的时候记住这个 token，释放、续期的时候检查 token 是否和自己的 token 一样。Redis-py 中的 lock 就是这样实现的。

但是 redis-py 中的 extend 操作（对我来说）很奇怪，这个 extend 10s 实际的语义是：将锁原来的租期还剩下的时间，加上 10 s。考虑上面 Redbeat 的场景，肯定是要在锁过期之前续期的，比如说我在使用锁第 9s 的时候续期，那么续期 10s 效果是锁的过期时间变成 11s。然后再运行 9s 的时候续期，锁的时间变成 12s。就导致运行的时间越长，锁的过期时间越长，假如进程挂了，要经过很长的时间（不可预期），其他进程才能 take over。

实际上在 Redbeat 中我们实现的 extend 是“Extend to”的语义。将锁的过期时间重置到 10s。这样就不会使得锁的过期时间越来越长。

Redis 的 SETNX 文档中描述了一种锁的实现模型。这个文档没有使用过期机制，而是将 timestamp 设置为锁的 value，然后用检查过期时间的方式来判断锁有没有释放。对于锁的 timestamp 过期，多个实例试图获得锁的时候，是通过 GETSET 保证只有一个实例拿到了锁的。其他实例需要拿到锁，发现自己不是第一个的话，要认为自己获得锁失败。

 

同一租期内的问题

以上，看起来不可能出现竞争条件了，但实际上这个实现依然是有问题的。DDIA 的作者在跟 antirez 有关 redlock 的争论中，举了这么一种情况：A获得了锁，在租期内发生了 GC stop the world，然后时间超过了租期，但是 A 并不知道。这时候 B 获得了锁去更新了资源，然后 A 过了暂停之后也去更新了资源。

Client 1 不可能做每一步操作都检查锁是否过期，这样太繁琐了，并且即使这样，依然可能在检查锁ok之后发生进程暂停。然后这时候过期（因为检查操作和写操作不是原子的）。

这个问题的解决方法是 fencing。获得锁的时候，锁服务为其分配一个只递增的值。然后进程在访问共享资源的时候会带上这个递增 token，当存储资源接受写操作的时候，会只接受更大的 token 的写，低于存储资源当前最大 token 的写请求会被拒绝。

注意：这里要求写操作是感知和记录下现在的最大的 token 的，实现的复杂度上也有所增加。

 

以上，我们讨论的锁都是基于一个安全可靠的、提供 CAS 机制的资源来实现我们的分布式锁的，假如要实现这样一种资源（比如 Redlock 的尝试），就要面对进程暂停、时钟偏移、网络延迟问题，要复杂的多。

推荐阅读：

  1. Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency 
  2. Database · 理论基础 · 关于一致性协议和分布式锁
  3. Is Redlock safe?
  4. How to do distributed locking
 

Django 项目使用 CircleCI

Posted on by 6 Comments

自从认识了 CircleCI 之后，基本上都在用这个了。相比于之前用的 travis-ci，CircleCI 丑是丑了点，但是相比与 travis 有几点好处：

  1. CircleCI 基于 docker image 的，怎么做隔离的不太清楚，有可能是在虚拟机上面执行 docker 来做隔离的，而 travis 还是基于 VM。这样好的好处是，CircleCI 提供了很多 image，你可以组合出来很多服务。比如 Django 项目用到了 redis 和 MySQL，你只要在 yaml 里面加上这两个 image 就好了，而 travis 要在 VM 里面处理好服务依赖。不仅不方便，每次执行速度也慢很多。
  2. CircleCI 支持 private repo，travis 只支持开源 repo。

但要说缺点的话，CircleCI 用户体验实在不如 travis，配置比较复杂。每次用都会多少踩一些坑。这篇文章介绍一下一个 Django 项目接入的过程，和其中一些要注意的坑。

1. 设定好 Django 项目的测试和依赖

以前 Django 测试用的是 Django 自带的 manage.py 里面的 test. 后来发现还是 pytest 比较好：插件多、模板代码少些很多，fixture 的设计比较合理，测试中使用到 db 需要明确声明，否则无法 access db，这样更加 explicit，测试执行的速度也更快。

除了 pytest，其他的还有一些依赖，test-requirements.txt 文件的内容如下：

其中 pytest-django 是 pytest 继承到 Django 中去了，pytest-cov 是追踪测试覆盖率的，factory_boy 是可以根据 Django 的 ORM 自动生产测试需要的 Model （这个强烈推荐，如果不用这个的话，需要写一推 json 来事先定义好测试用的 Model，后续维护也很费劲，如果改了一个不需要测试的 Model 的 Field，这些 json 也需要维护）。

然后运行 Django 测试，使用 pytest 命令就好了:

这个命令太长了，我们可以将环境变量和命令参数写到 pytest.ini 文件中去：

这样每次测试，使用 pytest 这个命令就可以了，参数和环境变量会自动设置。

解释一下每个参数是干嘛用的：

  • 第一行是 Django 环境变量，用来区分测试使用的 django.conf.settings 和开发、生产用的；
  • –resuse-db ：pytest 测试复用DB，不必每次都创建然后执行 migrations，对测试执行速度的提升非常明显。但是在 CircleCI 上运行测试，由于每次 MySQL 都是一个新的镜像实例，所以还是要每次新建数据库，执行 migrations 的。这个参数只是在本地执行的时候有用；
  • –cov-config / –cov ：这个是追踪测试覆盖率的 coverage.py 使用的配置文件，和要追踪测试覆盖率的文件夹；
  • –cov-report ：生成测试覆盖率的格式，每次运行完测试之后，生成覆盖率测试的文件。在 CircleCI 上我们可以设置测试运行完之后将这些文件上传至 artifacts 上去，可以在浏览器看这些文件；
  • –junitxml ： 测试的 Summary，也可以在 CircleCI 上展示；

以上就是项目中测试的配置，现在运行 pytest 可以自动发现项目中的测试用例执行了，并且测试完成后会生成测试报告。

接下来介绍如何在 CircleCI 上配置，实现每次 git push 之后自动执行代码。

2. 在 CircleCI 开启 CI 和设置运行环境

接入的方式分两步，根据 CircleCI 的指引就可以：

  1. 用 Github 账户登陆 CircleCI，然后在 CircleCI 上导入 Github 的项目；
  2. 在项目中添加 .circleci/config.yml 配置文件，git push，就会自动触发 CircleCI 的 build 了。

其中配置文件以我的这个项目为例，配置文件如下（基本上是拿 CircleCI 的配置模板修改了一下，保留了注释）：

前面说过 CircleCI 是基于 Docker 的，它的一个好处就是：如果你需要 MySQL、Redis 之类的服务，只要在 docker 这里声明就好了，CircleCI 在启动测试的时候会帮你启动这些容器。

build:docker 这里的配置就是用到的服务，用到哪个配置就写上 CircleCI 的 image 就好了，常用的都有，比较丰富。后面的 steps 来定义 CI 的步骤，一些事先定义好的 steps 可以参考下文档， 比如 clone 代码之类的就不需要自己实现了。

但是这里有一些挺坑的地方，需要注意。

使用 CircleCI 官方 MySQL 这个 image 需要设置验证方式，不然的话会遇到以下这个错误：

MySQL，redis 等都不能通过 .sock 文件访问，访问的时候不要使用 localhost，使用 IP。因为本质上这不是在同一个 image 启动的，测试所在的容器并不会有这些服务的 sock 文件，实际上是启动了不同的 image 然后通过 docker 的 network 放在一组，实现了访问。

还有一个巨坑的地方是，有时候你依赖的服务还没准备好，测试就开始执行了。我用的时候发现有的时候访问 MySQL 端口不通，有的时候却是通的。解决的方式也很挫，就是 31-38 行，使用 dockerize block 住这个 step，不断检查端口是否接受连接了。端口通了才继续执行后面的步骤。

这里为了加快测试的执行速度，可以将创建的 venv 缓存起来，参考上面的 restore cache 和 save cache 那一步。需要注意的是 key 加上了 checksum，这样依赖文件更改的时候可以自动重新安装。有个小坑的地方是 CircleCI 竟然没提供删除 cache 的功能，所以我的 key 加上了 v3 ，如果想弃用之前的 cache 的话，只要升级到 v4 就好了，cache 找不到自动安装新的。

最后两步是上传测试 Summary 和覆盖率文件。效果如下：

test summary 展示

测试覆盖率文件

注意 venv 不要建立在 working_directory 下面，不然你的 venv 里面的库也会被追踪测试覆盖率。

最后再吐槽一下 Artifacts 没有自动打开 index.html 的按钮，每次都需要自己找到这个文件点开，有点反人类。

 

Redis客户端缓存设计（In-Process caching）

Posted on by 8 Comments

今天看 antirez 写了一篇有关客户端缓存设计的想法：《Client side caching in Redis 6》（文章比较难懂，如果先看 Ben 演讲，理解起来 antirez 这篇博客会轻松一些）。antirez 认为，redis 接下来的一个重点是配合客户端，因为客户端缓存显而易见的可以减轻 redis 的压力，速度也快很多。大公司或多或少都有实现这种应用端缓存的机制，antirez 想通过 server 端的一些设计来减少客户端缓存实现的复杂度和成本，甚至不惜在 redis 协议上做修改。

antirez 的博客对细节介绍的比较清楚，我这篇文章算是拾人牙慧了，一来理清一下自己的思路，二来我认为除了缓存，这个机制还可以用在实时控制应用程序的某些配置上面。跟大家分享一下。

一、缓存的数据一致性问题

通常我们谈论缓存一致性的时候，一般在谈的都是这种架构：应用有一个数据库和缓存，数据库中的常用数据会被放到缓存中，在这种场景下如何保证数据库的数据和缓存中的数据是一致的？这种其实比较好解决，Cache-aside 模式已经是比较成熟和通用的了，实现上也比较简单和可靠。

Remember kids: you either have a single source of truth, or multiple sources of lies.

但 Redis 这种缓存从某种意义上还是一种远程的缓存，每次缓存读取会增加一次 TCP RTT（这个影响个人认为随着技术发展会逐渐减少），数据的序列化和反序列化也需要资源。如果对效率有更高的要求，就要考虑进程内缓存了。

进程内缓存的数据一致性比分布式的缓存面临更大的挑战。一个进程更新的时候，如何通知其他进程也更新自己的缓存呢？如果按照分布式缓存的思路，我们可以缩短缓存过期时间，进程内缓存如果过期了就去分布式缓存获取数据。这样不必实现复杂的通知机制，但是不同进程内的数据依然会面临不一致的问题，并且不同进程缓存过期时间不统一，用户体验也不好，同一个请求到了不同的进程，可能出现反复幻读的情况。另外也会对分布式进行大量不必要的更新，浪费网络资源。

进程内缓存面临2个主要的问题是：

  1. 保证数据的一致性，包括各个进程缓存的数据要是一致的，进程缓存和 Redis 缓存要是一致的；
  2. 尽可能减小网络压力；

为了实现所有进程的缓存的一致性，显而易见的实现是，当一个 key value 被修改了，广播被修改的键值对。所有客户端收到广播的时候更新自己的 kv。这种实现的缺点是1）有可能一个进程收到两个冲突的广播，无法解决。2）广播键值对，这样修改缓存的代价太大了。基于这两点，可以想到优化方案是我们只广播更新的 key，Redis 的缓存最为 Source of Truth，客户端收到了 key 更新的消息，就去 Redis 获得最新的键值对。这样就解决了冲突的问题，对资源的消耗也少了。

这里还可能存在的问题是：业务为了避免 key 冲突，通常会把 key 的名字写的很长：project:app:username:lastlogin 。这样 debug 起来也很简单。Redis 的 Key 长度限制是 512M，“如果一个问题有可能发生，那么它就一定会发生”。另一个问题是即使其他进程缓存了 key 但是用不到，也要立即去 Redis 获取最新的 value，也浪费了资源，当然这里可以用类似 Cache-aside 的策略，收到 key 即删除，下次用到的时候再取，这个问题不大。

所以 Ben 视频中提出了一个很有创意的实现。这里是借鉴了 Redis Cluster，所以我们先跑个题：Redis Cluster 是将 key Hash 到不同的 slots，每个 Node 都保存一个范围的 Slots（Shared nothing），当读请求过来的时候，对这个请求的 key Hash 计算 Slot，然后根据 Slot 去对应的 Node 寻找这个 Key。

基于这个 idea，为了节省空间（同时节省广播 Key 的网络资源和处理 Key 更新的资源），每一个 key 都属于一个 slot，在 key 更新的时候，我们只广播更新了这个 key 所在的 slot：“嘿，这个 slot 更新了，你不用管 slot 里面哪一个 key 更新了，只要你的 key 在这个 slot 里面，那就去读 Redis 里面的数据吧，进程内缓存的数据已经脏了！” Slot 是 2bytes，比 key 小多了，可以节省很多网络资源。

空间是节省了，随之而来的问题是更新逻辑变得复杂。如果广播 key，那客户端收到 key 即删除，下次从 Redis 取就好了。收到的是一个 slot 呢？Slot 是单向的（因为 hash 是单向的），有 key 可以计算出 slot，有了 slot 可不知道这个 slot 能包含哪些 key。

计算遍历所有的 key 吗？命中脏 slots 的话，就删除这个key？但是这样的话相当于对每一个缓存更新操作，客户端都要遍历计算一遍自己所有 key 的 slot，显然是不可接受的。

这里也是采用惰性计算的思想：客户端收到了 slot 更新的广播，只把 slot 存起来，当真正用到在此 slot 中的 key 的时候才去 Redis 更新。那么就会有这样一种情况，slot 中部分 key 更新了，部分 key 没有更新，如何区分开哪些 key 已经在 slot 更新之后更新过了呢？这里只要记一下 slot 更新的 timestamp 就可以，每一个 key-value 也带有一个 timestamp 属性。如果 key 的 timestamp 早于 slot 的 timestamp，那 key 就是需要更新的；更新之后 key 的 timestamp 就晚于 slot 的 timestamp 了。下次可以直接用。

客户端内缓存需要保存的内容，增加了 slot 和租后修改时间，kv 也增加了 timestamp 保存从 Redis 获得缓存的时间，用来判断这个 key 是否脏了。

读缓存的流程：先将 kv 的 timestamp 和 slot 的 timestamp 对比，看 key 是否已脏。

写操作比较直观，先写到 Redis，再写到 in-process cache，两个都洗完之后返回客户端缓存更新成功。

这里还有一些 tricky 的情况：我更新了一个 key，刷新了这个 key 的 timestamp，同时又收到了这个 key 所在的 slot 更新的消息。这时客户端如何处理这种情况呢？以自己更新的为准还是收到的 slot 信息为准？这个问题可以用 Master clock 时钟同步或 RedLock 来解决，但是从并发性和系统复杂度方面讲，两个都不是最好的办法。

这里有一种无锁的实现，通过操作的顺序来保证数据一致，非常巧妙，实现的几个要点如下：

  1. 所有的 timestamp 都是 server local timestamp：获得了 slot 更新的消息，将 slot 的更新时间设定为当前 local timestamp；进程更新 key 了，进程将 key 的更新时间设定为 local timestamp。实际上，timestamp 已经当成一个相对于本地 server 的偏移量来用了，无论是不同进程之间的时间如何偏移不准，都没有影响；
  2. 必须先更新 Redis，Redis 更新完成之后再发布更新消息（再次强调，Redis 作为 Source of the Truth）；
  3. 在更新 Redis、in-process cache 之前就获取 timestamp，这一步很关键。这里解释一下为什么要先获取 current timestamp 再进行更新：其根本目的是 slot、key 的 timestamp 就尽量提前。如果在 Get current timestamp 之前收到了 slot update message，那么我们的更新操作一定发生在其他进程的更新操作之后，没有毛病；如果在 Get current timestamp 之后收到了 slot update message，那么不管如何，我们的 key timestamp 会落后收到的 slot timestamp，会去 redis 获取，也没有毛病。假设这里先更新完再获取 timestamp，会有这么一种情况：我们更新好了 in-process cache，这时候来了一条 slot update message，我们更新了这个 slot 的 timestamp，然后我们自己的更新操作到了获取 timestamp 这一步，我们记录了自己的 key timestamp 和 slot timestamp。就造成了我们的 key 更新时间实际上晚于真正的 key 更新时间，我们保存了一个过时的 key 却不知道。

以上说的有点啰嗦，总结一下：我们总是更新完 redis 缓存在发送同步消息，这样其他进程收到消息的时候，Redis 总是保存了最新的缓存；通过提前获取时间来保证了本地更新缓存和收到缓存更新时的冲突（倾向于认为自己的数据过时），并且没有锁、没有时间同步要求、不会保存了一个过时的 key 却认为是最新的。

最后其实还有一种非常极端的情况，但是有出现的可能，我觉得作者这个解决方法很牛，所以也说一下。

这个情况就是在一个 timestamp 分辨率下，我更新缓存，但同时收到了 slot 更新的消息。即我的 key 的 timestamp 是 a，但是在 a 这个 timestamp 的同时其他进程更新了缓存，这个时候 timestamp a 依然是正确的，但其实缓存住的是一个过时的 key。其实这个发生的概率太小了，timestamp 的精度是 300ns 的话，必须在 300ns 内更新完 redis 缓存和 in-process 缓存，收到 sync 消息，才有可能发生——但是依然有概率发生的。

解决的方法很聪明：GetTimestamp() 之后总是 -1（其实不必-1，减一个 timestamp 精度就可以）.这样就保证收到 sync message 我总是倾向于缓存脏了，去 redis 获取。如果发生一个 timestamp 进度内出现缓存更新和收到 sync 消息，那么我实际缓存更新的时间肯定晚于其他进程更新缓存的时间，因为我把我的表调快了嘛，所以我保存的 key 是新的。

最后的方案还有一些小问题：如果 pub/sub 出现了网络问题，那么情况就退化成等待缓存过期的情况了。Pub/Sub 本身在 redis 中就不是可靠的，可以通过 Stream 或其他可靠的机制来替代。

Well well，以上就是在现有的 Redis 实现客户端缓存的一些设计，这个设计源自 Redis Conf 的演讲。Antirez 认为这个方法非常好，所以想在 Redis Server 端做一些支持。

二、Redis 6 客户端缓存加强

注意上面讲的都是 Client 端所做的实现，对 Redis Server 并没有任何改动，这意味着，使用当前的 Redis 完全是可以实现的。这个实现存在的问题有：

  1. pub/sub 不可靠，如果 sub 掉线，pub 端和 Server 并不做任何承诺，这个上面说过的；
  2. 广播的是 slot 信息，slot 中如果有一个 key 更新了，那么整个 slot 都认为脏了。一共有 16384 个 slot，这意味着如果我们有百万级别的 key 数量的话，将平均几百个 key 共享 slot，这样的话变脏的几率是很高的。这是一种 Trade off 吧，一个 slot 占用 16bit，16384 个 slots 一共占用 64Kib 的数据。毕竟客户端的的目的是最大程度的利用缓存；
  3. 一个 slot 更新的消息，Server 要广播给所有的客户端，及时那些客户端并没有缓存这个 slot。这是因为服务端无法知道哪些客户端缓存了哪些 slots；

以上的问题，只有在 Server 端参与的情况下才可以更好地解决。所以 Redis 6 会实现 “Server-assisted client side caching”。

关于问题2和问题3：Redis 的 Command Table 里面会标记出来 Read Only 的命令，当客户端发送了 Read Only 的命令，比如 MGET，Server 除了返回响应之外，还会记住这个客户端读取了这个数据（数据所在的 slots）。这样 Server 会保持追踪哪个客户端缓存了哪些 slots，在 slot 变脏之后，只通知缓存这个 slot 的客户端。

实现的方式是保持一个很大的指针数组，每一个指针指向一个 Linked List，代表缓存了一个 Slot 的客户端列表。

每一个 client 都有一个 unique ID，第四行就表示，client 9，1，2 读取了 slot4 中的数据。client假设 slot4 中的 key 更新了，那么 Server 将会把 Slot 更新的信息发送给这三个客户端。这样就解决了问题3，无意义的消息推送问题。

这个指针数据有多大呢？首先这里的 slots 数量比 Ben 的方法多很多，这里使用的是 CRC64 的 24bit 输出，那就是 2^24 个 slots。指针是 64bit 指针，即 64bit ** 2^^24 = ~130Megabyte。Antirez 认为服务端这些内容是是值的，这解决了很多 key 共享 slots 的问题，就算有千万级别的 key，也只有两三个 key 共享 slots，散列度很高。

有2点需要注意：客户端可以重新 match 这些 slots，服务端是 16million 个，客户端可以使用更少，收到 slots 信息自己做 mapping；这个 feature 可以选择开关，通过 CLIENT TRACKING on 来打开。

关于问题1：Antirez 建议客户端感知连接的断开，处理好重连的情况；建议有一个 Thead 来 ping connection 确保连接存活。Redis Server 为了尽量减少影响，以及方便客户端的实现，还会通知其他客户端：请转发此消息（slot invalidation）给掉线客户端。

 

另外这样的实现在 Redis 协议里面有些冲突，客户端调用 block 命令收到的回复和收到的 slot push message 回复如何区分？Antirez 直接没有提复杂的实现（比如从 Response 中添加额外的信息标志这个是正常回复，还是 Invalidation message?），而是建议另开一个 Connection，专门处理 Invalidation messages，不和接收正常回复的 Connection 共享一个 Connection Pool。客户端可以通过发送命令 CLIENT TRACKING on REDIRECT 1234 来告诉服务器有一个专门的客户端是接收 Invalidation messages 的。

以上已经合并到 unstable。其实我倒觉得，现在同 datacenter 内的网速已经很快了（），增加这样的复杂度来换取客户端缓存的优势好像并不值得，实际我也没有接触过客户端缓存，也不知道会带来多少的性能提升。但是我看到这个实现我马上想到了一个非常实用的使用场景。

三、客户端缓存的应用场景：动态配置数据

复杂系统中我们肯定有动态修改配置的需求：比如如果 condition-1 就这样处理，如果 condition-2 就那样处理。每一个请求都需要判断这个 condition，这个 condition 又经常变。

如果放到数据库里面，通过数据库来修改，显然对数据库的压力就太大了。一般我们会实现某种形式的通知系统。类似下面的这种结构。

对支付宝中间件熟悉的同学，可以发现这就是 DRM（动态配置中心，Dynamic Resource Management）。现在有了 Redis 这种机制的话，我们可以很轻松的实现一个可靠的动态配置系统。

下面这张图很直白的表示了什么样的数据，适合什么样的缓存。

Source: https://www.youtube.com/watch?v=kliQLwSikO4

在这张图中，配置类型的数据几乎是属于最右下角的了，可能每一个请求都需要读取配置数据，访问频率非常高，但是改动很小。除此之外，像是对于每次请求都要通过 cookie 判断用户登陆状态的情况，对 session 的读取压力也是非常大的，这种场景其实做到客户端缓存中也比较合适。

综上，Client-caching 我认为意义是很大的。如果你有 Redis，那么你不需要引入其他依赖，不需要 Message Queue，不需要同步时钟，不需要锁，就可以得到一个近乎强一致的客户端缓存机制。

 

最后，在这篇博客中有这么一句话让我感动：

Yet I was among the streets of New York thinking about this idea.

像 Antirez 这种程序员是一种英雄主义，也是我的榜样。

参考资料：

  1. RedisConf18: Techniques for Synchronizing In Memory Caches with Redis – Redis Labs （Slide）
  2. /RedisMultilevelCache
  3. Client side caching: initial design ideas
  4. Client side caching in Redis 6
  5. 进程内缓存，究竟怎么玩？
  6. 进程内缓存与分布式缓存的比较
  7. 缓存更新的套路
 

Linux 文件系统 inode 介绍

Posted on by 7 Comments

平常使用计算机，我们的直觉是计算机里面分成了文件夹和文件两种东西。但是实际上在操作系统的文件系统中，文件夹也可以被认为是存储了特殊内容的文件，“所有的东西都是文件”。而且文件系统并不用文件名来区分文件，而是使用一串不重复的数字。本文就来介绍一些文件系统的一些概念和原理。

Linux 的文件系统将磁盘分成了两部分。一部分存储的是 inode，一部分存储的是 block。文件的内容存储在 block 中。文件的元信息，比如 owner,group,atime 等，都存储在 inode 中，包括 block 的位置。如下图：

从图中我们可以看到，这里面没有文件名字的信息。而我们日常对文件的操作都是通过文件名来的。那文件名字在哪里呢？上面说过，文件夹也是文件，其实文件的名字，就在文件夹的内容里面（即 blcok）。文件夹也是上面的形式，由 inode 记录了它的元信息，然后 inode 指向了 block，block 里面存储了文件夹的内容，即文件名字到 inode 的映射。

虽然文件夹也是文件，但是操作系统并不提供 syscall 对文件夹的内容进行直接操作。比如，你不能 cp /dev/null directory 来覆盖文件夹的内容，也不能查看 block 存储的真正内容。而只能通过系统提供的 syscall 对文件夹进行有限的操作。这么做第一是因为对文件夹的操作就这么多，通过 syscall 就够了；第二是因为文件夹存储的映射如果被搞乱了，不光这个文件夹不可用了，相关的 inode 都拿不到了（因为我们针对文件的操作都是通过文件名，inode 被文件系统屏蔽掉了）。

所以，当文件系统拿到一个路径，是怎么找到对应的内容的呢？比如 /home/root/a.txt 。

首先文件系统会从 #2 inode 开始（注意这里说的经典的文件系统，不同的文件系统开始的 inode 可能不同，但为啥是2呢？），也就是 / ，找到 #2 inode 指向的 block 读到 / 下面的文件列表。然后找到 home 对应的 inode。然后通过 inode 指向的 block，打开 /home 下的文件列表，找到 root 对应的 inode，找到 inode 指向的 block，读到 a.txt 对应的 block，最后读到 block 存储的内容，就是 a.txt 的内容啦。

我们可以通过 ls 的 -i 参数查看一个文件夹下的名字对应的 inode（跟上面说的从 #2 开始不一样，因为我这个环境是 xfs）：

[vagrant@trial /]$ ls -i
   66973 bin    8388737 etc        163 lib64  25274562 opt      12408 run          1 sys  25165953 var
       2 boot       161 home   8496943 media         1 proc       164 sbin     18789 tmp
    1025 dev      66978 lib   16854324 mnt    16797825 root       162 srv    8388747 usr

文件系统一旦创建，inode 的数量或 block 的数量就确定了，不能修改。如果 inode 用完了，文件系统就再也不能创建新的文件了（不太可能发生，除非创建的小文件非常多）。df -i 可以查看系统的 inode 使用情况。

[vagrant@trial ~]$ df -i
Filesystem      Inodes IUsed   IFree IUse% Mounted on
devtmpfs        251872   402  251470    1% /dev
tmpfs           254824     1  254823    1% /dev/shm
tmpfs           254824   462  254362    1% /run
tmpfs           254824    17  254807    1% /sys/fs/cgroup
/dev/sda3      7864320 74351 7789969    1% /
tmpfs           254824    11  254813    1% /tmp
/dev/sda1        65536   308   65228    1% /boot
tmpfs           254824     5  254819    1% /run/user/1000

inode 到 block 的寻址

你用过U盘吗？可否遇到过U盘不能存储超过4G的文件的问题（FAT32文件系统）？即使U盘是32G的。这其实是文件系统寻址的限制。接下来我们以 EXT4 文件系统为例，看下有了 inode，文件系统具体是怎么找到 block 的，顺便计算一下 EXT4 单文件最大可能是多少。

在前面的那种图中，可以看到 inode 包含了文件拥有者，访问时间修改时间等信息。最重要的，是 block 的位置，毕竟这是真正存储了文件内容的地方。

如果给你一个 inode，你怎么把 block 的位置存到 inode 里面呢？文件的大小是未知的，可大可小。基于这个特点，首先想到的可能是用一个 LinkedList 来存储 block 的位置，block 留出一个位置存储下一个 block。但是要知道，机械硬盘顺序读很快，随机读的话磁头移动是非常慢的。所以 block 肯定是尽最大的可能连续使用，用 LinkedList 来做寻址就太慢了，比较合适的是 Array 这种相邻的形式。

那么在 inode 中我们应该为 block 的地址留出多少位置呢？太少的话，单文件的上限就太小了。太大的话，如果系统中都是一些小文件，就太浪费空间了。

Ext2/3 文件系统是这么做的（也是大多数文件系统的一个做法）：留出15个位置来负责存储 block 的地址。一个文件只能有 15 个block 吗？当然不是。这15个地址里面分成了直接指向（Direct Block Pointers），间接指向（Indirect Block Pointers），双重间接指向（Double indirect Block Pointers），三重间接指向（Triple Indirect Block Pointers）。

其中表示直接指向 block 的地址占了12个，这里我们假设一个 block 的大小是 4K，那么如果文件如果小于 4*12=48K 的话，直接使用 inode 中的直接 block 指针就可以存的下。综上，Direct Block Pointers 一共有12个，每一个表示一个 4K 的block。一共可以存储 48K。

第13个指针表示的是 Indirect Block Pointers。这个指针指向的地址也是一个 block，但是这个 block 里面存储的并不是文件的内容，而是一些指向 block 的指针——整整一个 block，存储的都是像 Direct Block Pointers 那样的指针哦！满满 4K 的指针。Block 指针是 32bit 的，一个 block 可以存储 4K/32bit = 1024个 Block 指针。综上，Indirect Block Pointers 就一个，里面使用一个 block 存储了 1024 个 block pointers，可以存储 1024 * 4K = 4M 数据。

第14个指针是 Double indirect Block Pointers，比较好理解了，这个位置存储的地址依然指向了一个 block，但是这个 block 里存储的还是 block 指针，这些 block  指针指向的 block 里面存储的还是指针！这些指针再指向的block存储的才是文件的内容。见上图的最后那一个位置。我们知道 Indirect Block Pointers 可以存储 4M 的数据，那么这里的双重 Block 指针其实就是存储了 4M 的指针，4M 可以存储多少个 Block Pointers 呢？4M /32bit = 1048576个，每个block 4K，那就可以存储 4G 数据。

第15个指针，很好理解了吧，让我绕个圈子，这里存储的是指向 Block 的指针，指针指向的 Block 存储的还是 Block 指针，指针指向的 Block 存储的还是Block指针，这里存储的 Block 指针指向的还是 Block 指针（数数这里面有几次 Indirect吧）。这些指针指向的Block存储的是文件内容啦。这里最多可以有多少个 Block 呢？Double indirect Block Pointers 可以有 4G，那么这 4G 数据都是指针的话就是 4G / 32bit * 4K = 4G * 1024 = 4T.

综上，文件最大是 48K + 4M + 4G + 4T。是不是很巧妙的设计？

因为这种方式指向无法动态给二重或者三重指针分配大小，未免有些浪费。在 Ext4 中，ext4_extent_header 的多重指针是动态分配的，简单来说，eh_depth 字段标识了目前的 block 是第几重指针，如果是0，说明指向的 block 直接存储的是文件内容，如果不是0，那么 block 存储的就是 Indirect Block Pointers, 并且 eh_depth 标识了会有几重指针。在 Ext4 中，但文件最大大小不再受层级限制，而受 logical block number 的限制，即 block number 最大是 2^32，在 4K block 下，就是 16T。eh_depth 最大是 5，仅仅是因为 5 就可以存储下 2^32 个 block number 了，再大也没有意义。(ext4_extent_header 长度是 12bytes，4*(((blocksize - 12)/12)^n) >= 2^32 中 n 最小是5）

最后需要强调一点是，不同的文件系统 inode 数据结构有所不同，比如 ext4 文件系统就支持将很小的文件直接存储在 inode 中，不使用 block。

Hard Link 和 Symbolic Link

上面我们说过，文件夹的内容其实是文件名字到 inode 的映射。

那么是否可以有两个 name 映射到同一个 inode 呢？

答案是可以的，这就是所谓的 Hark Link.

通过 ln source-filename target-filename 可以创建一个 Hard Link，即创建一个 target-filename 映射到和 source-filename 一样的 inode number。

举个例子，我们现在有 hello 这个文件：

➜  foo ls -il
total 0
12945694378 -rw-r--r--  1 laixintao  wheel  0 Jun 25 20:46 hello

可以看到它的 inode number 是 12945694378, 然后我们再创建一个 Hark Link：

➜  foo ln hello world
➜  foo ls -il
total 0
12945694378 -rw-r--r--  2 laixintao  wheel  0 Jun 25 20:46 hello
12945694378 -rw-r--r--  2 laixintao  wheel  0 Jun 25 20:46 world

我们可以观察到两个有趣的现象：

1）hello 和 world 有相同的 inode number，这意味着这两个文件名字对应的 inode 是一样的，即它们的 owner、atime，以及指向的 block 一模一样，文件内容也当然一模一样。如果我们改变了一个文件的权限，那么去看另一个文件名字，也会跟着改变。

➜  foo chmod 777 world
➜  foo ll -il
total 0
12945694378 -rwxrwxrwx   2 laixintao  wheel    0 Jun 25 20:46 hello*
12945694378 -rwxrwxrwx   2 laixintao  wheel    0 Jun 25 20:46 world*

2）有一个数字从 1 变成 2 了。这数字叫做 Link Counts，就是在 inode 中有一个字段记录的是有多少 filename -> inode number 的 mapping，当没有 filename 指向这个 inode 的时候，说明这个 inode 可以被回收了。

从上面我们可以看到，创建一个 Hard Link 之后，实际上就有两个 filename 指向了同一个 inode。即新创建的 Hard Link 和原来的在本质上没有什么区别，也分不出来谁是 Hard Link 谁是原来的文件。删除文件这个操作其实是 unlink，就是删除了一个 filename -> inode 的 mapping 而已，当一个 inode 的 Link Counts 为0，inode 才会被删除。

有没有感觉像 GC 中的引用计数？那么新的问题就来了：怎么解决循环引用的问题呢？比如像下面这个情况，子文件夹里面建立了一个指向父文件夹的 Hard Link.

可能的循环指向问题

这样在整个父文件夹删除的时候，这些 Hard Link 指向的 inode 的 Link Counts 依然不会下降，导致释放就有问题。文件系统是怎么解决的呢？禁止对文件夹建立 Hard Link，只允许对文件建立 Hard Link.

另外，你有没有想过为什么我们可以使用 cd .. 跳转到父文件夹呢？其实就是在文件夹创建的时候，会自动创建一个叫做 .. 的 mapping，指向父文件夹的 inode。即一个新文件夹创建之后，它的 Link Count 就是2了，一个是 .，一个是 .. 。

相对而言，Symbolic Link 更常用一些，因为 Hard Link 的管理成本太高了。你删文件的时候，得把所有的 Hard Link 都删掉才行。

Symbolic Link 可以理解成一个特殊的文件，文件的内容指向的是真正的文件。这样一来，如果删除了源文件，Symblic Link 还是存在的（用过 Windows 的朋友可以理解成 Windows 的快捷方式）。

早期符号链接的实现，采用直接分配磁盘空间来存储符号链接的信息，这种机制与普通文件一致。这种符号链接文件里包含有一个指向目标文件的文本形式的引用，以及一个指示自己为符号链接的标志。

这样的存储方式被证明有些缓慢，并且早一些小型系统上会浪费磁盘空间。一种名为快速符号链接的新型存储方式能够将文本形式的链接存储在用于存放文件信息的磁盘上的标准数据结构之中（inode）。为了表示区别，原先的符号链接存储方式也被称作慢速符号链接。

Source

Fun with inodes

  • 移动文件、重新名等操作，实际上只是修改了 parent directory 的 block 中存储的 filename -> inode 映射，所以跟文件多大是没有关系的，都是 O(1) 复杂度；而且这也不影响 inode 的号码。
  • 理论上，当文件创建，inode 分配，就不会再变了。移动、重命名、写入文件、截断文件都只是修改 inode 的元信息或者修改 parent directory 的内容，inode 总是不变。所以像日志收集程序，使用 inode 来区分日志文件，是非常可靠的。日志被 rotate 了也可以做到不重不漏。
  • 如果你知道一个 inode ，怎么找出这个文件呢？$ find . -inum 23423 -print
  • 但是直接操作 inode 是不允许的，Kernel 提供的 syscall 只能通过 filename 来操作文件。理由同上，文件系统 corrupt 了是很危险的。
  • 文件系统里面有一个文件带着古怪的名字，怎么删除？可以通过 inode 删啊。 $ find . -inum 234234 -delete .

 

最后再强调一下，本文介绍的是大多数 filesystem 的表现，具体到一个特定的 filesystem 可能会有所不同。如果本文有疏漏，欢迎指出。

参考资料（以下列举了一些参考资料，和文件系统的实现）：

2024年9月12日更新：原文介绍的 inode layout 其实是 Ext2/3 文件系统，不是 Ext4 文件系统，进行了纠正以及补充 Ext4. Debian 中文群 dududu 和 Yancey Chiew 指出。

 

Gitops 的一些实践经验

Posted on by Leave a comment

之前看过多很多讲 Gitops 概念的文章，今天终于看到一篇讲实践的（原文见这里），我觉得这篇文章很有参考价值，介绍了一些 gitops 实在会遇到的问题和工具，和大家分享一下。

1.只用一个 git 仓库

建议所有跟基础设施有关的内容都放到一个仓库，包括有的团队、所有的项目。比如 kubernetes 的 template， infra as code 的平台，比如 terraform，比如 ansible playbooks，监控设施比如 grafana dashboards, alerts, 等等。

这样有哪些好处呢？

  1. single source of truth。线上的真实环境，实际在生效的配置，都可以在这一个仓库找到，就避免了去各个平台看现在生效的是什么配置的问题；
  2. 可以将在 CI 中设置 lint、准入检查等。虽然如果分多个仓库，也可以分别设置 CI，但是那样毕竟容易乱。用 CI 我们可以自动的检查某些变更是否符合标准，一开始可能是全部要人工检查(去 Review Merge Request)，但是逐渐自动化起来难度也不大；
  3. 灾难恢复更简单。都放在一个仓库里面，可操作性就很强了，不然你要处理多个仓库的先后顺序问题，相互依赖的问题等等。
  4. 加强了管控能力和审计。这个很好理解，毕竟只有一个仓库嘛。但是 git log 一定要写好，审计才方便。

作者推荐了一个目录结构：

思考：

只用一个仓库所带来的透明性，收益是很高的，审批可能都是 merge requests 了。我们也不必各种问”最近有什么变更”了，每个人都可以去看 git log。如果操作都能设计成声明式的，那么回滚也很方便，revert log 就可以了。

恢复整站，或者再搭建一套环境速度也大大提高，waveworks 经历过所有机器都被抹掉的情况，得益于 gitops，集群的重新 provision 只用了 45min.

2.自动化

Automation is key because it speeds you up immense.

作者在这里举了一个例子，如果用 Prometheus 的话，可以将 HTTP 服务的大盘监控抽象成一种通用的模板，新加一种 HTTP 服务的话大盘可以自动生成。(监控规则同理)

思考：

在Web平台上点点点，是比较难自动化和复用的，但是如果是 Code 就不一样了。你可以用你最喜欢的Vim编辑器快速处理大量的配置文本，也可以用脚本批处理，可定制化很高。但是这依赖于 Infra as Code,监控代码化，configuration-as-code、database-as-code、infrastructure-as-code 等。

配监控太痛苦了！我觉得比较理想的监控是：中间件层收集一些通用的 metric，开发同学在代码中(用注释或者继承类的方式？)暴露关键的业务指标，大盘可以根据template自动生成。(要是真这样就好了)

3.能用Operators就用Operators

简而言之，可以减轻手动 Apply 的负担。(既然都 gitops 了，鼠标能少点几次就少点几次吧。)

举几个例子：

  • Atlantis: 基于 PR 的 Terraform 流程，看这里一张图就明白了。
  • flux: waveworks的作品，确保 git 仓库的配置和 k8s 集群中的状态一致。(消除 diff 应用变更，readme 里面也有一张图展示的很明白)

思考：

XX as code, 声明式，diff merge 应该是 gitops 的核心吧？

4.Secrets 能够被自动获取

Secrets are still just parts of the deployment, that is why they are required for full disaster recovery for example.

推荐将 Secrets 存在仓库中(当然了，加密存储)，或者在部署后能以某种形式自动地获取。这里的关键和难点是保持 Secrets 以加密的形式存储，严禁明文存入 repo。

Problem: “I can manage all my K8s config in git, except Secrets.”

Solution: Encrypt your Secret into a SealedSecret, which is safe to store – even to a public repository. The SealedSecret can be decrypted only by the controller running in the target cluster and nobody else (not even the original author) is able to obtain the original Secret from the SealedSecret.

— sealed-secrets

推荐的几种形式有：

  • 用类似 sealed-secrests 的 Operator，已加密形式将 Secrets 存到仓库，Secrets 到达集群的时候进行解密。(同类产品还有 Mozilla 的 SOPS)
  • 使用 Hashicorp Vault 类似的集中式 Secrets 管理工具
  • 云服务商提供的同类产品
  • 使用 git-crypt 或 git-secret 进行手动加密

以上，水平有限，如果有疑问可以看下原文确认，如有理解错误欢迎指出。如果原文有错误欢迎讨论。