0. Hash@数据结构

开始的开始 - ziplist

常见的数据结构, 包括set/hash, 在内容较少的时候是通过ziplist来是实现的, 为:

type ziplist struct {
        size         int
        tail_offset  int
        count        int 
        entries      []entry
}

type entry struct {
        prev_len     int8/32
        encoding     int8/32
        data         []byte
}

先来看ziplist: count与entries表示数据单元及元素数量, 这很好理解. size字段表示整体的长度, tail_offset表示从这个位置开始如何定位到最后一个元素.

然后我们来看元素entry, data很好理解. encoding则是表示了里面数据的类型, string还是int等等, 关键是prev_len, 这里面存了一个数值, 用于表示上一个元素的长度, 帮助我们定位到上一个元素用的.

关键是这个长度是可变的, 它可以是8位, 也可以是32位, 如果是8位那么这个值最多也就是2^8, 但如果上一个元素的长度大于这个长度的话, 我们就会把这个元素变成32位, 其中第一位是0xFF表示此32位用于表示长度

关于ziplist

从上面我们也能看到ziplist中的每一个元素都是前后紧紧贴在一起的, 这虽然比较省空间, 但也导致插入元素的时候都要重新分配内存.

另一种常见的问题叫做级联更新, 意思是某一瞬间插入的新元素很大, 那么下一个元素的prev_len从8位变成32位, 联锁的导致后面的元素扩张

listpack

listpack可以用来取代ziplist的, 区别是微小的: 没有tail_offset字段, 以及

type entry struct {
        encoding   int8/32
        data       []byte
        size       int8/32
}

最主要的是我们使用了size字段替代了prev_len, 并把这个字段放在一个单元的最后面, 那么现在假设我们在data2, 怎么定位到上一个元素data1呢? 我们站在data2上直接向前去读一个整数就能拿到data1的长度, 进而就能定位到data1了x

dict

在hash/set元素非常少的时候我们使用的是ziplist, 然而等元素多起来了以后, 就会使用dict来存储数据, 这个实现非常简单, 两个hashtable渐进式搬运, 解决冲突的方式是挂链表