上一篇文章中我们我们看了下 cdb 的文档，从这篇文章开始我们来看下代码~ 上文中我们有介绍 cdb 的分层， 可以看到在 distribution layer cdb 抽象了一个 monolithic sorted map, 对于上层的调用者只需要做 kv request 这一层就能帮找到正确位置读取或存放 key， 本文我们来看一个问题: 一个上层 kv req 怎么找到对应的 range 和 节点信息?

DistSender 概览

首先，当调用方将 kv 请求送到 kv.DistSender#Send 之后会 distSender 进行以下处理:

  1. initAndVerifyBatch: 首先在 batchRequest 补充了 timestamp 和当前 gateway node id 信息， 并完成请求类型校验
  2. splitBatchAndCheckForRefreshSpans: 将 batch 的 requests 按照 flag 兼容性(也就是请求类型)进行分组在保证次序的前提下: admin 单独一组， 读写写 request 不混合， 在非 1PC 的情况让 EndTransaction 也单独一组
  3. keys.Range 对上面分好的每个分组， 寻找能 cover 分组中所有 key range 的最小 range
  4. 接下来会根据是不是 ParallelCommit 执行不同逻辑， ParallelCommit 是新版本的优化后面有机会我们单独分析， 我们这里先看不是 ParallelCommit(即 Inflight = 0) 的情况, 所以后面的逻辑都在 divideAndSendBatchToRanges
  5. 下一步是将这些可以 batch 的 request 根据存储的 range 信息， 进一步进行分组将其中属于一个存储 range 的的 request 作为一个 batchrequest ， 这部分逻辑首先通过 RangeIterator 来来定位描述存储 range 的 RangeDescriptor， 如果 batch 中所有请求都属于一个 RangeDescriptor 则可以直接发送对应的 range id， 但如果 batch 中的请求属于不止一个 RangeDescriptor 需分多次发送，多个请求的发送如果条件支持会并行发送， 因为有多个 response 需要维护一个 position 来让来让响应找到之前的 request, 这部分逻辑位于这里.
  6. 具体到一个 RangeDescriptor 的请求， sendSingleRange 会通过将 RangeDescriptor 中的 ReplicaDescriptors 信息从 gossip 获取所有 replica 地址列表，如果不是 follower read 会通过 leaseholderCache 来让 leaseholder 放到 replica 列表最前面； 如果是 follower read 会根据 hlc 之前的 latency 或 gossip 的 nodeDescriptor 中的 locality 来调整 replica 列表顺序实现大家喜欢的”美东读美东， 美西读美西”的功能
  7. 之后就是通过 grpc 发送了，cdb 抽象了一个 Transport 来完成对对地址列表的尝试， sendToReplicas 会调用 Transport 并根据 resp 信息来来选择驱动 Transport 或更新 leaseholder cache.

简单而言 distSender 会根据请求类型做一次分组，然后对分组的请求找到对应 range 根据 range 将请求再做一次分组， 最后根据 range 中的 Replica 信息从 Gossip 获取地址，并根据是否 follower read/延迟/Locality 找到目标节点，将最终的 batchrequest 进行发送；
可以看到 range 信息中只维护 nodeid 具体的地址维护交给 gossip， range 信息中也不关系 leaseholder 由单独的 LeaseholderCache 管理(一个做了 shard 优化并发访问的 map 维护 rangeID - storeID 的映射)， transport 封装处理了重试多个节点(包括 locality-aware balance)和 store 交互的细节, 通过抽象拆分职责 range 管理本身职责更清晰一些。
在简单看完 distSender 处理，后接下来我们看下 range descriptor 如何保存和维护的，从而支持第 5 步的 RangeIterator 找到 Range Descriptor ，而进行后续发送的。(其实请求 batch 划分和发送中也有很多值得看不过待后续再看下~)

Range Descriptor 存储

cdb 的数据是通过 kv 的存储， 并通过 range 进行分片，所以上一节的 distSender 在发送在得到一个 kv 请求时(实际是一组 key 或 key range)， 需要确认这个 key 属于哪个 range，那这个 range 信息在哪呢？
cdb 的 range 信息本身也会作为特殊的 range 存放到 cdb 中(自举 - -), cdb 的 range 可以理解为一颗 3 层的树结构:

  1. [/meta1/,/meta1/max)   <-- always one range, gossipped, start here!
  2.                      |
  3.           -----------------------
  4.           |                     |
  5.   [/meta2/,/meta2/m)   [/meta2/m,/meta2/max)
  6.           |                     |
  7.       ---------             ---------
  8.       |       |             |       |
  9.     [a,g)   [g,m)         [m,s)   [s,max)   <- user data

当我们希望发送一个 key 的请求的时候希望找到的是描述 user data 的 ranges 的 descriptor， 所以当一个普通的 key 到达时会通过 keys.RangeMetaKey 找到保存 descriptor 的 meta2 key, 并去 kv scan 这个 meta2 key， 如果不考虑缓存则扫 meta2 key 也需要获得 meta2 key 的 descriptor， 所以需要再次用 keys.RangeMetaKey 找到 meta2 key 的 meta 也就是 meta1 key， 所以需要 kv scan meta1 key 保存的 descriptor 即可， 但 meta1 key 在哪呢？？？—- 如上图标示描述 meta1 的 descriptor 会通过 Gossip 来获取，这样之后就是就能通过 meta1 找到 meta2/xxx 的 scan 位置获取希望找的 xxx key 的 descriptor 之后进行发送。
对于 meta1 和 meta2 在 cdb 中会被作为 PseudoTable(没有 table descriptor) ，所以他们的 ZoneConfig(一个或多个 ranges 的配置) 是比较特殊的 SystemZoneConfig 所以他两的 range 会做 5 replicas(正常数据默认是 3 replicas)， 来不会因为元数据不可用导致的可用性问题(除了 range 还有其他一些 pseduo 可以看前面连接中的注释)。
对于 meta range cdb 不会做 split, 当然仍然会有 rebalance 或故障的情况，对于 meta1 如前所述会通过 Gossip 来获取， 每个 node 会定期检查自己是不是 FirstRange(也就是 meta1 range) 的 leaseholder， 如果是则会通过 Gossip 向其他节点传染， 所有节点都会订阅 Gossip 的 callback 来完成在 meta1 range 节点变更时对 cache 的淘汰。

Range Descriptor 缓存

range 做为正常的 kv range 存放， 所以在请求处理需要获取 range descriptor 时只需要找到descriptor 的 descriptor 做 kv scan 即可， 不过每个请求都去 scan 下明显是低效的，所以在 cdb 每个节点都会在内存中维护一份 range descriptor 的 cache 信息， 所以在第一节中每个请求处理的 RangeIterator 其实都是从 RangeDescriptorCache 中获取。
这个 cache 的核心方法是 lookupRangeDescriptorInternal， cdb 选择使用 llrb(左倾红黑树 ps 有个 go 里 orderedmap 实现对比测试)来维护已经访问过的 key 到 range descriptor 的信息缓存, 如果有 miss 则会如上节所述的进行 kv scan 获取 descriptor 信息让后回填到 cache 中， 这里考虑到同一个 range 可能会有同时大量请求都去 scan 的情况(比如过期或主动废弃等…), 大神使用了 go runtime 里有用但标准库没有暴露的 singleflight 来让避免 miss 时大量重复的 kv scan 消耗； 另外如果发生了 cache miss， 在进行 kv scan 的时候除了获取遇到的第一个 range 外还会尝试多 prefetch 下一个 range(因为很可能上层应用是对多个 range 的依次 scan 预取据说有性能改进);
对 cache 查找结果返回的是 range descriptor + 一个 EvictionToken， 在外层的 iterator 会保存这个 token， 通过 token 可以:

  • 在下次迭代的中直接使用上次的 descriptor 位置继续往下查找，可以用上 prefetch
  • 可以在”很远的地方”通过 token 来操作对 cache entry 的主动淘汰和替换

cache 维护一个需要关注的问题就是怎么 eviction，前面我们已经看到 meta1 在 gossip 告知后会主动 EvictCachedRangeDescriptor, 而其他地方都是通过 EvictionToken 来进行， 主要还是在使用 cache 信息访问返回错误时根据错误信息进行 eviction:

  • 返回 RangeKeyMismatchError: 通常是 range 已经过期(比如 split) , 需要废弃过期缓存数据，不过这个 Error 比较特殊，会告知 MismatchedRange 和 SuggestedRange 信息，如果有返回可以用提示的 descriptor 对 region 进行 replace 修正，没返回则需要 evit
  • 返回 SendError: 前面我们提到过 cdb 抽象了 transport， 所以 SendError 带表对于 range 的可用 replica 尝试了一遍都不行，可能是信息过期或 replica 都换了，所以会将 这个 range evit 重试
  • Transport 遇到 NotLeaseHolderError：且 error 中的 leaseholder 的 store 不在已知 replica 中(正常在的话只需更新 leaseholder cache)， 会主动返回 SendError 然后利用上一条的处理进行 evit cache
  • 最后就是在 iterator seek 过程中发现非预期情况会进行淘汰。

    总结

    cdb 通过 range 来管理 kv 数据， range descriptor 自己也会作为 kv 数据存储，最终 range descriptor 的 descriptor 通过 gossip 来让所有节点都知晓， 且 range descriptor 数据使用了 5 replicas 来保证高可用， 为了提高效率对 range descriptor 维护了 cache， 并根据访问错误被动淘汰， 对于顺序扫场景进行了预取，并使用 singleflight 解决 miss 导致的重复 scan 问题。