Redis底层数据结构之深入理解跳表（2）

        上一篇文章中我们详细讲述了跳表的增添、查找和修改的操作，这篇文章我们来讲解一下跳表在多线程并发时的安全问题。在Redis中，除了网络IO部分和大文件的后台复制涉及到多线程外，其余任务执行时全部都是单线程，这也就意味着在Redis中不存在跳表的多线程并发问题。但在Java程序开发中，我们可能也会使用到跳表，这时候就不得不考虑如何设计一个并发安全的调表结构。

        JDK中提供了一种支持并发安全的跳表结构ConcerrentSkipListMap可以直接使用。不过这篇文章我们来自己思考一下在设计并发安全的跳表时我们需要考虑哪些内容。

全局读写锁

        首先对于跳表的操作可以分为读操作和写操作两种。那么最简单粗暴的方法就是对整个跳表加读写锁。所有的写操作需要持有写锁才可以进行，所有的读操作可以同时持有多把读锁，来实现并发读取。不过这时候我们来考虑这样一个问题，对跳表加了全局读写锁，如果一个线程拿到了写锁，并且对跳表的操作时间很长，那么后边所有的写操作和读操作都会被阻塞，如果对跳表的大小、存储数据的大小和每次写操作的时间进行严格限制，全局加读写锁在写少读多的场景下还是有一定的可用性的。

        上面全局加读写锁虽然实现简单，但是有很大可能会造成线程间的阻塞等待，实用性并不高，而造成阻塞问题的根源是锁的颗粒度太大了，有没有一种方法可以将锁的颗粒度进行细化，这样就可以同时允许多个线程拿到不同的锁进行操作，降低线程阻塞的概率。

节点读写锁

        我们来思考这样一个问题，当我们对单向链表并发操作时，对于写操作（增加、删除），其实只需要执行一步操作，就是找到被操作节点的前一个节点，并将其next修改为被操作节点的后一个节点。这就意味着，如果我们在并发环境下对被操作节点的前一个节点进行加锁操作，就可以保证同一时间只有一个线程对被加锁节点后的节点进行操作。

        在对跳表的节点进行加锁时，我们还需要多考虑一点，由于新加入的节点的高度是随机的，可能会比当前跳表的高度要高，这个时候我们需要对跳表的头结点进行加锁，并修改跳表的最大高度。

        总的来说，其实我们在细化跳表中锁的颗粒度到节点上时，需要考虑两部分。第一是如果新加入的节点高度小于跳表原最大高度，这时就从上至下逐层取到操作节点的左边界节点的锁即可；第二是如果新加入的节点高度大于跳表原有最大高度，这时就需要持有跳表的头结点锁，然后再进行第一部分的操作。

查询操作

        查询操作的步骤就是从跳表的最高层head节点开始，从上往下逐层遍历，直到找到key值小于target并且最接近于target的左边界节点，然后进行层数下降。具体的流程如下图所示：

增添操作

        增加操作执行时，如果增加的节点已经存在了，则会更新为新值，如果不存在，则要将其插入跳表中。可以将增加操作分为以下四个步骤：

        ①首先检查要添加的节点是否存在。

        ②如果存在，则将旧值更新为新值。

        ③如果不存在，则将新节点插入跳表中。

        ④如果要插入节点，并且节点高度比原有跳表要高，则对跳表的高度进行扩容。

        上述步骤中的①、②、③在并发情况下需要是原子性的，来保证单一线程对跳表更改的有效性。具体的流程如下图所示：

删除操作

        删除操作的步骤就是查询到要删除的节点，将其每一层的前一个节点的指针进行变更，指向当前层被操作节点的后一个节点就可以了。具体的流程如下所示：

        不过删除操作存在一个问题，就是左边界这种策略对于删除和增添并发执行的时候会失效，可能会造成新增添的节点被误删。所以造执行删除操作时，还是采用全局锁的方式来对其和增添操作进行隔离。

        本文主要梳理了一下自己实现并发安全的跳表的一些思路，算是学完Redis底层数据结构和并发编程之后笔者的一些思考，如果有什么问题或者勘误，欢迎评论区留言。