htree：结构，冲突处理，内存和速度优化

htree 简介

• htree
  • 每个跟bucket 一个
  • 是一个16 叉完全树，数组分配，高度在配置中指定。
  • 每个叶子 对应一个 “list”
• key hash 8 bytes， 高位到地位分三部分：
  • 第一部分 定位在那个 bucket。
  • 第二部分 定位在 bucket.htree 的哪个叶子
  • 第三部分 在叶子对应节点中定位 key 对应的 item

冲突处理

伪代码

def get(key):
    pos = collisions.get(key) or htree.get(hash(key))
    rec = data.get(pos)
    if rec.key != key:
        pos = get_pos_slow(key)
        rec = data.get(pos)
    return pos

思路

1. 结构
   • 内存 htree 记录 hash(key): pos
   • 外存 dtree 记录 key：pos
     • 比如放在 leveldb 中： (<hash, key>: pos)， 就可以把相同 hash 的可以聚到一起。
     • 要求打配合：比如 fast write， 没有太多内存开销等
   • pos 对应 record = (key, value)
2. 算法
   1. 读 htree 的得到 pos 对应 record 的中 key 是错的。 fallback 到 dtree 中找即可。
   2. 找到冲突后就记在内存中（当然同时也持久化）
   3. 只要概率足够低，不影响整体性能
3. 此外
   1. htree 天然方便存 hash，并且自己隐含了一部分 hash， 能减少 list 存储 的部分 hash 的长度。

用 hint 实现 get_pos_slow 的原因

• 透明，方便管理（迁移，备份）
• 可以对应一个 data，方便快速查看等
• 性能可控，主要是写和 gc；读慢点，发生概率低，可以接受
• 不算复杂

优化

• 为了减少 go 内存使用效率和 gc 的影响， 每个叶子节点 对应的 list 用一整块内存分配，并且用 c 分配。
• 因为 cgo 慢， douban 场景下读多写少， 在增减新key时重写分配 list 时用 cgo， 读和更新用go 数据结构映射过去，没有cgo开销。