跳表实战

2015-01-24

这两天写了一个跳表,虽然以前写着玩过,实际场景中应用这种数据结构还是头一次。

业务要用到这样一个结构:有一些活动,每个活动中有一些产品,每个产品中有一些创意包,每个创意包中有一个创意。这是我们竞价服务中使用到的一个结构,之前的实现是用map[int64]map[int64]map[int64]FilterCreative,但是发现这是一个性能热点,尝试去优化。这么多级的map实在太反人类了,大量的小对象分配造成了不小的GC压力。另一个同事试过改用多级的slice来做,效果不理想。因为使用场景中有对各个级别的插入删除的需求,而slice删除一个结点要做大量的memmove。

我想了一下,skiplist正好可以满足这个场景。把(活动、产品、创意包)整体作为一个key,创意作为value。用key查value自然没问题。多级别的查询也能做到,比如遍历活动下的所有产品,比如遍历产品下的所有创意包,因为就是跳表一个有序的链表,顺着key搜索就能多级遍历了。

访问性能并不会比之前的map差,尤其是之前的结构要做多次的key的查询,而现在整体作为key只需要一次查询。跳表还可以通过控制level生成的概率来调节访问性能和存储开销。

做个简单的对象池,手动管理内存分配就没有之前使用map时大量的小对象引起地GC压力。


写的过程中发现的一些东西:

根据实际观察,其实概率算法数据分布很不均衡,1/2的概率,常常50多个结点了却只到3层。虽然理论上时间复杂度是O(logN)的,概率不好实际上很容易退化到O(N)。

不做对象池,垃圾回收那边的压力会很重。然后会造成CPU波动特别大,一下子100%多一下子就400%多。原因是频繁的结点分配导致GC频率变快,Go语言的垃圾回收是stop the world的,业务是计算瓶颈类型的,所以做垃圾回收期间CPU会降下来,但是积累的请求会造成接下来一波的CPU高峰。

找小于key的最大结点 vs 找大于等于key的最小结点。对于普通链表操作实现二者代码是一样简单的。但是对于跳表,直接实现后者很不容易,而实现前者却很简单。想一想为什么?

如果不允许相同key的结点的插入,要注意什么?结点插入是一个从上层到下层的过程,不能在访问该层的时候执行插入!

skiplist跳表