SeaweedFS 提供了几种不同的 needle 索引策略,包括 memory, btree, blotdb, leveldb 四种,其中默认的是 memory,也是其内部唯一自己实现的一种索引,btree 使用 google 的 btree 开源实现,boltdb 和 leveldb 都依赖一个 db.
memory 的索引实现,使用了一个叫 CompactMap(这是作者自己起的名) 的数据结构。本文后面将会重点介绍 compactMap 是一个怎样的数据结构,以及如何使用这个数据结构简历 needle 的索引。
compactMap 本质是一个数组 (Golang 中可以动态扩展的数组),其元素类型是 CompactSection,定义如下:
- //This map assumes mostly inserting increasing keys
- typeCompactMapstruct{
- list []*CompactSection
- }
CompactMap 结构体内部只有一个 CompactSection 的结构体的指针数组,那么为什么作者假设插入的 key 是增序的呢?我们先看 CompactSection 是一个什么样的结构,答案后面就会很清楚。 下面是 CompactSection 的结构:
- typeCompactSectionstruct{
- sync.RWMutex//读写锁values []NeedleValue//NeedleValue数组,保存了Needle的key, offset, sizeoverflowmap[Key]NeedleValue//用于保存超出batch,但是在(start, end)范围的needleValuestart Key//该section保存的key最小值end Key//该section保存的key最大值counterint //当前该section的needleValue的数量}
CompactSection 保存了 key 值在 [start, end] 范围内的所有 needleValue,每个 section 都会记录当前处于该段的所有 needleValue 数量,并且有一个固定的容量限制,目前版本的限制是 100000,如果该段已经存储的 needleValue 已经达到了最大容量,但是其 key 那么就会将当前 [start,end] 范围,那么 needleValue 保存到 map 里,也就是说 values 数组最大长度为 100000, 主要是因为当前使用二分搜索,查找 key 对应的 needleValue, 所以数组还是不能太大。使用 map 也能够快速的定位。
上面简单介绍了 compactSection 的结构,先不管怎么向某个 section 插入一个 needleValue, 我们只用知道一个 compactSection 保存从 [start,end] 范围内的所有 needleValue。所以 CompactMap 的 list 就是将 key 分成一段一段管理,至于每一段的 key 是怎么管理的可以不用管,只用知道每个段的范围即可,当要插入一个 key 的时候,使用二分查找的方法找到该 key 所处的 section, 然后插入到该 section。
下面是二分查找的代码:
- func(cm * CompactMap) binarySearchCompactSection(key Key) int {
- l,
- h: =0,
- len(cm.list) - 1
- if h < 0 {
- return - 5
- }
- if cm.list[h].start <= key {
- if cm.list[h].counter < batch || key <= cm.list[h].end {
- return h
- }
- return - 4
- }
- for l <= h {
- m: =(l + h) / 2
- if key < cm.list[m].start {
- h = m - 1
- } else { // cm.list[m].start <= key
- if cm.list[m + 1].start <= key {
- l = m + 1
- } else {
- //貌似这里有bug, 如果处于(end, $$start_{m+1}$$), 则同样要插入一个新的section
- /*if(key > cm.list[m].end){
- return -5
- }*/
- return m
- }
- }
- }
- return - 3
- }
下面以上面的代码分析怎么找到一个 NeedleValue 应该插入的 section: * 如果 list 为空则直接返回一个负值 * 先判断是否能够插入到最后一个 section, 能够插入的条件是该 key 大于 section 的最小 key 值,如果当前 section 没有超过容量,或者超过了但是处于 [start, end] 范围,则返回当前 section, 否则返回一个负值。 * 前两个条件都不满足的话,就二分搜索前面所有 section 能够插入的 section, 如果到第一个 section 都没有找到,即 key<list[0].start, 说明需要插入一个新的 section, 返回一个负值
总的来说,搜索有两个结果,返回一个可以插入的 section 和返回一个负值,当返回一个负值的时候,就需要重新生成一个 compactSection,使用插入排序的方法,将其插入到 list 代码如下:
- func(cm *CompactMap) Set(key Key, offset, sizeuint32) (oldOffset, oldSizeuint32) {
- x := cm.binarySearchCompactSection(key)ifx < 0{//println(x, "creating", len(cm.list), "section, starting", key)cm.list =append(cm.list, NewCompactSection(key))
- x =len(cm.list) - 1
- //keep compact section sorted by start
- forx > 0{//插入排序,保证start有序
- ifcm.list[x-1].start > cm.list[x].start {
- cm.list[x-1], cm.list[x] = cm.list[x], cm.list[x-1]
- x = x - 1}else{break}
- }
- }returncm.list[x].Set(key, offset, size)
- }
Note: 感觉这里存在一个 bug, 因为二分搜索的时候是根据 start 来查找能够插入的 section, 但是存在一种情况,比如假设 list[i].start <= key, 且 list[i+1].start > key, 那么上面的程序就会返回插入到第 i 个 section, 但是可能 list[i].end < key, 也就是说实际上这个时候应该生成一个新的 setction 插入到除以 i 和 i+1 之间。当然作者假设 key 是递增的(并不一定要连续),如果 key 是递增的,这样就能能够保证不会出现出现插入一个中间断节的 list. 但是如果假设是递增的,何必使用二分查找合适的 section 呢?肯定是最后一个或者需要重新在后面追加一个,所以目前感觉这个逻辑还是有问题的。考虑的非递增的情况,但是非递增的情况下,在二分查找 section 又没有考虑断节的情况,所以这里应该有问题,二分查找的代码里 21-23 行是我添加的,应该可以解决这个 bug。后分析发现,因为插入除了最后一个 section 时候,同样也更新了 end 所以就不存在这个问题
前面已经简单的介绍了 CompactSectionMap 的结构,主要有一个数组和一个 map 组成,并且每个 section 的数组都有一个容量,下面主要分析怎么 set 和 get 一个 needleValue。 下面是 set 的核心代码:
- //return old entry size
- func(cs * CompactSection) Set(key Key, offset, size uint32)(oldOffset, oldSize uint32) {
- cs.Lock() if key > cs.end {
- cs.end = key
- }
- if i: =cs.binarySearchValues(key);
- i >= 0 {
- oldOffset,
- oldSize = cs.values[i].Offset,
- cs.values[i].Size
- //println("key", key, "old size", ret)
- cs.values[i].Offset,
- cs.values[i].Size = offset,
- size
- } else {
- needOverflow: =cs.counter >= batch needOverflow = needOverflow || cs.counter > 0 && cs.values[cs.counter - 1].Key > key
- if needOverflow {
- //println("start", cs.start, "counter", cs.counter, "key", key)
- if oldValue,
- found: =cs.overflow[key];
- found {
- oldOffset,
- oldSize = oldValue.Offset,
- oldValue.Size
- }
- cs.overflow[key] = NeedleValue {
- Key: key,
- Offset: offset,
- Size: size
- }
- } else {
- p: =&cs.values[cs.counter] p.Key,
- p.Offset,
- p.Size = key,
- offset,
- size
- //println("added index", cs.counter, "key", key, cs.values[cs.counter].Key)
- cs.counter++
- }
- }
- cs.Unlock() return
- }
下面是 set 的过程: * 在插入前,首先会进行加锁的操作 * 然后如果当前的 key 大于 end, 那么更新 end(这里优于,在执行 set 之前,compactMap 的 set 里有个判断,如果 key 大于最后一个 section 时,如果小于当前容量,则直接返回最后一个 section,如果大于当前容量,那么要求要小于最后一个 sectiond 的 end, 这样的结果就是最后一个 section 的 end 只有在小于当前容量的时候才会更新。低于其他的 section 就没有这个限制,这样可以防止中间出现断节从而需要插入新的 section) * 使用二分查找在 values 数组中查找是否含有该 key, 如果含有那么就更新对应的 needleValue,返回旧的 needleValue * 如果没有找到,则判断是否需要插入到 overflow map 中,这里判断是否需要插入到溢出 map 中并不单单,根据 overflow 来判断,还有一种情况是,没有大于数组的容量,但是该 key 小于 values 数组中最后一个 needleValue 的 key, 这样能够保证 values 数组的 key 是有序的 * 如果不需要溢出,那么久直接追加在 values 数组的最后面
从 compactSectionMap 中获取一个 needleValue 的操作比较简单,下面是核心代码:
- func(cs * CompactSection) Get(key Key)( * NeedleValue, bool) {
- cs.RLock() if v,
- ok: =cs.overflow[key];
- ok {
- cs.RUnlock() return & v,
- true
- }
- if i: =cs.binarySearchValues(key);
- i >= 0 {
- cs.RUnlock() return & cs.values[i],
- true
- }
- cs.RUnlock() return nil,
- false
- }
get 的时候也同样要先加锁,然后先判断 overflow map 中 是否存在改 key, 如果不存在二分搜索 values 数组,如果都不存在,则返回没有找到即可。
整个 CompactMap 的设计思路还是比较清晰的,很像 skiplist,通过分段 (section),可以大大的加快查找速度,不过如果 key 比较随机,那么就会带来很多的二分查找,插入排序的操作,性能就不是那么理想,不过总的来说这个数据结构还是比较高效的。
来源: http://blog.csdn.net/kongdefei5000/article/details/73558176