关于 RoaringBitmap 的线程安全问题

对于一个数据结构，如果作者没有表明该数据结构是线程安全的，我一般都会认为不是线程安全的，因为编写高效且线程安全的数据结构是比较困难的，关于 RoaringBitmap 的线程安全问题，早在 2015 年就有用户反馈希望能够有线程安全的实现，详见该 issue: thread safety，仅有几次提交后至 2017 年后就再无下文，而 RoaringBitmap 的主线一直在演进，且在官方文档中甚至没有关于线程安全实现的介绍，以至后续在我的工程中，关于 RoaringBitmap 的并发修改使用了 ReentrantReadWriteLock 去保证多线程下的线程安全，使用读写锁是为了提高读多于写场景下的吞吐量。

对于 RoaringBitmap 主线上的代码，很容易证明不是线程安全的，我们可以写个简单的程序进行验证，本文基于 RoaringBitmap 0.9.15 版本进行验证，其 Maven 依赖声明如下：

<dependency>
    <groupId>org.roaringbitmap</groupId>
    <artifactId>RoaringBitmap</artifactId>
    <version>0.9.15</version>
</dependency>

编写简单的验证程序：

package me.tianshuang;

import org.roaringbitmap.RoaringBitmap;

public class BitmapThreadSafeTest {

    public static void main(String[] args) {
        RoaringBitmap bitmap = new RoaringBitmap();

        new Thread(() -> {
            while (true) {
                bitmap.add(0);
                bitmap.remove(0);
                bitmap.trim();
            }
        }).start();

        while (true) {
            bitmap.contains(0);
        }
    }

}

程序会抛出异常：

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
 at org.roaringbitmap.RoaringArray.getContainer(RoaringArray.java:672)
 at org.roaringbitmap.RoaringBitmap.contains(RoaringBitmap.java:1611)
 at me.tianshuang.BitmapThreadSafeTest.main(BitmapThreadSafeTest.java:19)

我们可以稍做分析，contains 方法的源码为：

/**
 * Checks whether the value is included, which is equivalent to checking if the corresponding bit
 * is set (get in BitSet class).
 *
 * @param x integer value
 * @return whether the integer value is included.
 */
@Override
public boolean contains(final int x) {
  final char hb = Util.highbits(x);
  // 如果在执行下面一行代码前另一线程调用了 trim 方法清除了未使用的 keys 数组中的元素则会触发数组下标越界异常
  final Container c = highLowContainer.getContainer(hb);
  return c != null && c.contains(Util.lowbits(x));
}

contains 方法先获取 int x 数字的高十六位，用于定位 container 的索引，然后获取该 container，再判断该 container 中是否存在低十六位的值以得到 int x 是否存在于该 bitmap 的结果。在整个流程中，如果有其他线程触发了收缩则可能触发数组下标越界异常。

故在我的分布式 bitmap 服务中，采用了 ReentrantReadWriteLock 去保证多线程下 bitmap 的线程安全，在 ReentrantReadWriteLock 的官方文档中，其中举例即使用了 ReentrantReadWriteLock 去保证 TreeMap 的线程安全问题。

我们可以对上述程序进行进行简单的调整即可保证线程安全：

package me.tianshuang;

import org.roaringbitmap.RoaringBitmap;

import java.util.concurrent.locks.ReentrantReadWriteLock;

public class BitmapThreadSafeTest {

    public static void main(String[] args) {
        ReentrantReadWriteLock reentrantReadWriteLock = new ReentrantReadWriteLock();
        RoaringBitmap bitmap = new RoaringBitmap();

        new Thread(() -> {
            while (true) {
                ReentrantReadWriteLock.WriteLock writeLock = reentrantReadWriteLock.writeLock();
                writeLock.lock();
                try {
                    bitmap.add(0);
                    bitmap.remove(0);
                    bitmap.trim();
                } finally {
                    writeLock.unlock();
                }
            }
        }).start();

        while (true) {
            ReentrantReadWriteLock.ReadLock readLock = reentrantReadWriteLock.readLock();
            readLock.lock();
            try {
                bitmap.contains(0);
            } finally {
                readLock.unlock();
            }
        }
    }

}

Reference

RoaringBitmap
ReadWriteLock (Java Platform SE 8 )
ReentrantReadWriteLock (Java Platform SE 8 )