在Prometheus推送监控指标到Pushgateway上的时候,需要现在本地做一个缓存减少开销,这时候的缓存通常用的类型就是跳表,即ConcurrentSkipListMap

数据结构

传统意义的单链表是一个线性结构,向有序的链表中插入一个节点需要O(n)的时间,查找操作需要O(n)的时间。
而跳表可以抽象的看成是一个有“层次”水平结构的链表集,不仅可以向右还能向下走,宛如第四象限的坐标轴。

跳表分为许多层(level),每一层都可以看作是数据的索引,这些索引的意义就是加快跳表查找数据速度。每一层的数据都是有序的,上一层数据是下一层数据的子集,并且第一层(level 1)包含了全部的数据;层次越高,跳跃性越大,包含的数据越少。

源码分析

以ConcurrentSkipListMap为例:

static class Index<K,V> {
    final Node<K,V> node;//索引节点关联的数据节点
    final Index<K,V> down;//下一级别索引节点(关联的数据节点相同)
    volatile Index<K,V> right;//当前索引级别中,后继索引节点
    ……
}

static final class Node<K,V> {
    final K key;
    volatile Object value;//value值       
    volatile Node<K,V> next;//后继数据节点
    ……
}

抽象成图形大概就是这样子:

每个index都有一个向右和向下的index指针,边界的话则为null。
同时,每个index都指向一个Node的指针,同一列的index指向同一个Node节点。(你也可以理解为同一纵的index都是同一分身)

查找流程

通过这图应该能加深上述结构的理解:
跳表查找19
该图整个方方为Index,左边数值为Node、右边分别是rightIndex和downIndex。level为2,我们要找到19。

先从原点开始,按最上面的level2出发,发现level2上的第一个节点的Node值为6比19小,所以走。
同样的方法在level2层走到17,发现下一个level2的对应值为21,比19大,不往右走,往下一级的level走,到level1。
发现level1下的17Index的下一个值就是19,刚好相对,走过去,结束。

跳表、哈希表、红黑树

关于跳表

跳表其实也是一种通过“空间来换取时间”的一个算法,通过在每个节点中增加了向前的指针,从而提升查找的效率。

在跳表中,对于一个链表内每一个结点包含多少个指向后续元素的指针,是通过一个随机函数生成器得到。
这就是说,跳表使用概率均衡技术而不是使用强制性均衡技术。因此,对于插入删除结点比传统上的平衡树算法更为简洁高效。

LevelDB、Reddis的底层存储结构就是用的SkipList。
SkipList底层是用链表实现的,可以实现为lock free(基于CAS的无锁编程),同时它还有着不错的性能(单线程下只比红黑树略慢)

三者比较

  • Hash表:插入、查找最快,为O(1);如使用链表实现则可实现无锁;数据有序化需要显式的排序操作。(不适合迭代)
  • 红黑树:插入、查找为O(logn),但常数项较小;无锁实现的复杂性很高,一般需要加锁;数据天然有序。(不适合并发)
  • SkipList:插入、查找为O(logn),但常数项比红黑树要大;底层结构为链表,可无锁实现;数据天然有序。

跳表和红黑树的性能相当,最主要的优势就是当调整(插入或删除)时,红黑树需要使用旋转来维护平衡性,这个操作需要动多个节点,在并发时候很难控制。而跳表插入或删除时只需定位后插入,插入时只需添加插入的那个节点及其多个层的复制,以及定位和插入的原子性维护。所以它更加可以利用CAS操作来进行无锁编程。

当我们希望快速存取<Key, Value>键值对时我们可以使用HashMap
当我们希望在多线程并发存取<Key, Value>键值对时,我们会选择ConcurrentHashMap
TreeMap则会帮助我们保证数据是按照Key的自然顺序或者compareTo方法指定的排序规则进行排序
当我们需要多线程并发存取<Key, Value>数据且保证数据有序时ConcurrentSkipListMap也许可以满足我们的需求。

CurrentSkipListMap

ConcurrentSkipListMap持有跳表的特点,它是线程安全的有序的哈希表,适用于高并发的场景。

ConcurrentSkipListMap和TreeMap
两者虽然都是有序的哈希表,但是ConcurrentSkipListMap是线程安全且由跳表实现;而TreeMap是线程不安全且由红黑树实现。

非多线程的情况下,应当尽量使用TreeMap。此外对于并发性相对较低的并行程序可以使用Collections.synchronizedSortedMap将TreeMap进行包装,也可以提供较好的效率。对于高并发程序,应当使用ConcurrentSkipListMap,能够提供更高的并发度。


主要是整合了关于跳表的知识点同时完善了结构图。
后面CurrentSkipListMap的具体操作可以看这里:ConcurrentSkipListMap分析和使用

Last modification:January 28th, 2021 at 09:55 am
喵ฅฅ