Poison

关于 RoaringBitmap 的线程安全问题

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

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

1
2
3
4
5
<dependency>
<groupId>org.roaringbitmap</groupId>
<artifactId>RoaringBitmap</artifactId>
<version>0.9.15</version>
</dependency>

编写简单的验证程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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);
}
}

}

程序会抛出异常:

1
2
3
4
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 方法的源码为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* 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 的线程安全问题。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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();
}
}
}

}
References

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