freecache源码分析

freecache实现分析

概述

作用比较直白，类似map的kv内存结构，所以hash会成为它的主要基调，也是为何能高效的根本。整个freecache被划分成了256个segment，根据key的hash值选择具体的segment，这一点我认为是它对并发友好的原因，假如不同线程操作不同的segment，意味着各自都是独立的空间，无需加锁（当然，它并没有做到这一点）。每个segment可以分成两部分：真实的数据存储以及对存放方式的描述结构。前者是一个ringbuff，所有kv结构的具体数据存放在这里，比较容易理解。后者相对麻烦一些，它描述了segment的逻辑组成：256个slot，每个slot含有不定数量的entry，每个entry就是每条kv记录的描述信息。

这里是它的源码 freecache ，宣称有不少好处，有一点是说Zero GC overhead，我觉得应该主要是因为它整体上其实是一个字节数组空间，并无任何对象的存放，所以不存在对象的分配和释放，鉴于自己对golang GC的无知，后续再补充。

这里有一个插曲，是给作者提了一个。

数据结构

如图所示。

这里面我认为有点不好理解的就是slot的组织方式。在segment的结构中，与slot存放相关的有3个变量：

• slotLens：是一个数组，存放了每个slot中实际的entry个数。

• slotCap：是一个具体的数值，意味着每个slot中最多可以存放多少个entry，如果实际存放的个数超过了这个容量就需要扩充（seg.expand），按*2扩展（熟悉c++STL的人可能比较明白，这里倒也不是拍脑袋的结论，最朴素的原因就是确保在于每次新分配的尺寸必然大于之前所有分配的总和，这样可以确保之前的数据具有O(1)的插入效率，但也不能太多，否则浪费，这里2倍刚好满足这个需求。但也会导致无法重用之前已经释放的缓存，效率有所降低，所以有的C++库会选择1.5倍，比如Facebook的Folly的FBVector。）

• slotsData：是一个数组，存放了所有slot中包含的entry。

具体操作

set

一般步骤

1. 根据key的hash值的低16位作为索引定位到某个segment。segId := hashVal & 255

2. 定位segment的slot：slotId := uint8(hashVal » 8)

3. 定位key对应的entry：seg.lookup(slot, hash16, key)

4. 如果该key已经存在了：

   • 当value的长度不大于之前value的长度（valCap），那么直接在当前位置写入kv记录
   • 否则，删除并扩展value的容量

5. 检查当前ringbuff的空间是否满足将当前kv记录存入，是则插入否则按LRU算法淘汰部分则插入

一些细节

1. 每一条kv记录都有两部分组成，头部信息和entry描述结构，其中头部和真实的kv数据会存放在segment的ringbuff中：

    type entryHdr struct {
        accessTime uint32   // 最近一次访问kv记录的时间
        expireAt   uint32   // 超时时间
        keyLen     uint16   // 
        hash16     uint16   // 当前entry所在slot的位置
        valLen     uint32   
        valCap     uint32   // 当前entry所能容纳的val的最大长度，
                            // 如果重复写入的value小于这个值会直接在当前位置写入，
                            // 否则会扩充这个value的容量
        deleted    bool     // 为了避免不必要的内存拷贝，删除的时候并不会移动其他kv结构来覆盖当前kv，
                            // 而只是通过这个标记来识别当前kv是无用的
        slotId     uint8    // 当前entry所在的slot
        reserved   uint16
    }
   
    type entryPtr struct {
        offset   int64  // 由于ringbuff就是一个字节数组，所以在其中定位一个kv必然需要一个偏移量。
        hash16   uint16 // 我们知道slot中可能并非只有一个entry，这是由于我们的slot是有限的。
                        // 当key多到一定程度时，hash之后必然会出现冲突，不同的key定位到同一个slot，
                        // 因此就必然会存放多个entry。这些entry是按这里的hash16的大小 排序 存放的，
                        // 所以查找时也是O(1)的。
        keyLen   uint16 // 该entry中存放的kv记录的key的长度，主要用于比较是否是要查找的key。
        reserved uint32 // 对齐字段
    }
   

   所以，计算真实耗用内存的时候，每条kv都要加上24B的头部消耗。

2. 上面简单说了，定位一个key，要先找到segment，再找到slot，再找到entry，才能找到具体的kv记录，在实现中由于使用了数组来存放所有slot的entry，所以这里的查找并非显而易见。

   • 从slotsData中查找某个slot所对应的区间：

        // 每个slot在slotsData中的偏移量
        slotOff := int32(slotId) * seg.slotCap
     
        // 偏移量+该slot所存放的entry个数，即为当前状态下该slot所对应的区间
        slot := seg.slotsData[slotOff : slotOff+seg.slotLens[slotId] : slotOff+seg.slotCap]        
     

   • 从该区间中查找某个key所对应的entry：

       // 可以看到，这就是一个简单二分查找，直接使用key的hash16的值作为对比字段（插入的时候似乎并未排序？？）
       high := len(slot)
       for idx < high {
           mid := (idx + high) >> 1
           oldEntry := &slot[mid]
           if oldEntry.hash16 < hash16 {
               idx = mid + 1
           } else {
               high = mid
           }
       }
       return
     

   • 如果找到了对应的entry —— 说明之前曾经设置过同样的key，检查key是否都是一样的，这里可能会有一个小疑问，因为查找的hash16已经是通过hash(key)得到的值，按理找到idx即意味着key是一样的了，但稍微一想就知道hash是不可能保证不同的key得到不同的值，更何况这里还只是截取了高16位，所以从字节的层次上检查key是否相同：

       // ringbuff的按字节判断 —— 略
       match = int(ptr.keyLen) == len(key) && seg.rb.EqualAt(key, ptr.offset+ENTRY_HDR_SIZE)
     

   • 如果找到了对应的key，那么：

       // 从ringbuff中，该kv记录所在的偏移处读取，先读头部
       seg.rb.ReadAt(hdrBuf[:], matchedPtr.offset)
     
       // 更新头部字段
       ……
     
       // 如果新的value不大于之前老的value长度，那么会在原来的偏移处写入新的值        
       if hdr.valCap >= hdr.valLen {
           ……
       }
     
       // 否则（新的value更长）删除该entry
       // 删除的时候只是将位于ringbuff中的kv记录的头部字段deleted设置为true
       // (这里可能存在一些重复计算 —— lookup和lookupByOff会有2次针对slotIdx的二分查找，感觉应该是可以优化的)
       seg.delEntryPtr(slotId, hash16, slot[idx].offset)
     
       // 并扩充kv中value的容量为原来容量的2倍但要确保，kv之和不能超过maxKeyValLen
       // 假设，将freecache设置为1G，那么maxKeyValLen = ((1G/256)/4) - 24                
       ……
     

   • 如果没有找到对应的entry或者对比后key不一致，更新为新key的头部描述信息

   • 找到一块合适的内存供新的entry使用：

       // 在插入之前，先检查一遍ringbuff，是否有需要淘汰的：seg.vacuumLen < entryLen，成立则进入淘汰策略
       // 1. 优先清理已经标注为删除的：if oldHdr.deleted {
       // 2. 再清理过期的：expired := oldHdr.expireAt != 0 && oldHdr.expireAt < now，
       // 所以可以看到，这里的过期是一种懒清理策略——写时清理
       // 3. 再根据LRU策略选择需要淘汰的entry，这个LRU的计算有点没看明白，但明确的是，越早访问的肯定越先被淘汰，
       // 关键就是早到什么时候就会被淘汰
       // 4. 如果entry的淘汰算法无法得到一个合适的大小，那么就需要淘汰ringbuff中的数据，跟entry的淘汰的区别是，
       // 此处并未参考访问时间这一因素，仅仅是越早写入的越先淘汰
       // 5. 直至空闲出满足需求的空间
       // 这一段逻辑比较复杂，尚未完全明白，待完善
       slotModified := seg.evacuate(entryLen, slotId, now)
     

   • 写入新的entry，有一个值得注意的点是，写入都是发生在ringbuff的最后，顺序写入的，并不会产生空的“气泡”：

       // 紧跟着ringbuff的最后
       newOff := seg.rb.End()
     
       // 插入上面说过的kv的描述结构：entry
       seg.insertEntryPtr(slotId, hash16, newOff, idx, hdr.keyLen)
     
       // 写入具体的kv数据到ringbuff
       seg.rb.Write(hdrBuf[:])
       ……
     
       // 更新ringbuff中可用的空闲长度
       seg.vacuumLen -= entryLen
     

get

一般步骤

1. 查找的方式跟set一致，不再赘述。

2. 如果该key已经存在了，检查是否超时，如果超时就将其删除（打标记），无数据返回，否则正常返回。

3. 更新访问时间

del

一般步骤

比较简单，查找并删除，不再赘述。

原理

上文也说过，此处并非真正的释放内存，可以说整个运行期freecache都没有主动释放内存的行为，这里的删除也只是将key对应的entry的头部标记字段deleted设置为true，这样后续如果再需要插入数据时可以直接使用这块内存。

这里有一个值得注意的地方是，在segment.del中通过lookup()找到了slot中entry对应的索引idx，然后调用seg.delEntryPtr发起删除（标记）行为，此时用同样的slotId和hash16，通过lookupByOff再次查询了entry对应的索引idx，我一直认为这两次的值都是一样的，不知道作者为何会再次检查一遍。我的理解是：当key一样，则slotId、hash16、slotsData都不会变，所以key所在的slot区间是一样的，也就是说对应的entry的idx是一样的，因此，entry必然也是一样的，且lookupByOff的参数offset是通过lookup查找到的entry的offset设置的，这两者还有必要再对比一次吗？

所以，我给作者提了一个 issue ，然后他回复确实是多余的，也做了一次 commit 。当然，错了不在我，反正是他改的，哈哈。

• Previous

  MIT6.824-Lab3实现笔记