这两天写了一个跳表，虽然以前写着玩过，实际场景中应用这种数据结构还是头一次。
业务要用到这样一个结构：有一些活动，每个活动中有一些产品，每个产品中有一些创意包，每个创意包中有一个创意。这是我们竞价服务中使用到的一个结构，之前的实现是用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的结点的插入，要注意什么？结点插入是一个从上层到下层的过程，不能在访问该层的时候执行插入！
Read full article from 跳表实战
No comments:
Post a Comment