redis bitmap数据结构之java对等操作
在之前的文章中，我们有说过 bitmap，bitmap 在很多场景可以应用，比如黑白名单，快速判定，登录情况等等。总之，bitmap 是以其高性能出名。其基本原理是一位存储一个标识，其他衍生知道咱就不说了，而 redis 就是以这种原生格式存储的。
实际上，redis 是基于 string 的数据结构实现了 bitmap 的功能。
1. redis 基本的 bitmap 操作命令
最基本的，redis 的 bitmap 有设置和读取两个值，即 setbit/getbit, 非常容易理解，即设置某个标识为 1，那么取值判定的时候，就可以得到 true.
127.0.0.1:6379> setbit bm1 222 1 (integer) 0 127.0.0.1:6379> getbit bm1 222 (integer) 1
这很容易理解，也是最基本的。当然，它还提供其他的一些操作：BITCOUNT 做数据量统计, BITOP 做 bitmap 的交并差运算... 我们也不必过多讨论它。
2. java 中的原生 bitmap
可以说 redis 的 bitmap 实现相当之简单，所以 java 也就顺便实现了一个 bitmap 的版本：BitSet .
@Test public void testJavaBitmap() { BitSet bitmap = new BitSet(); bitmap.set(88); // exist = true boolean exist = bitmap.get(88); BitSet bitmap2 = new BitSet(); bitmap2.set(99); // bitmap 中将包含 [88, 99] bitmap.or(bitmap2); }
java 中的 bitmap 实现，也是按位存储，但是是基于 long 的存储。
/* * BitSets are packed into arrays of "words." Currently a word is * a long, which consists of 64 bits, requiring 6 address bits. * The choice of word size is determined purely by performance concerns. */ private final static int ADDRESS_BITS_PER_WORD = 6;checkInvariants();} /** * Given a bit index, return word index containing it. */ private static int wordIndex(int bitIndex) { return bitIndex >> ADDRESS_BITS_PER_WORD; }</span><span style="color: rgba(0, 128, 0, 1)">/**</span><span style="color: rgba(0, 128, 0, 1)"> * Sets the bit at the specified index to {</span><span style="color: rgba(128, 128, 128, 1)">@code</span><span style="color: rgba(0, 128, 0, 1)"> true}. * * </span><span style="color: rgba(128, 128, 128, 1)">@param</span><span style="color: rgba(0, 128, 0, 1)"> bitIndex a bit index * </span><span style="color: rgba(128, 128, 128, 1)">@throws</span><span style="color: rgba(0, 128, 0, 1)"> IndexOutOfBoundsException if the specified index is negative * </span><span style="color: rgba(128, 128, 128, 1)">@since</span><span style="color: rgba(0, 128, 0, 1)"> JDK1.0 </span><span style="color: rgba(0, 128, 0, 1)">*/</span> <span style="color: rgba(0, 0, 255, 1)">public</span> <span style="color: rgba(0, 0, 255, 1)">void</span> set(<span style="color: rgba(0, 0, 255, 1)">int</span><span style="color: rgba(0, 0, 0, 1)"> bitIndex) { </span><span style="color: rgba(0, 0, 255, 1)">if</span> (bitIndex < 0<span style="color: rgba(0, 0, 0, 1)">) </span><span style="color: rgba(0, 0, 255, 1)">throw</span> <span style="color: rgba(0, 0, 255, 1)">new</span> IndexOutOfBoundsException("bitIndex < 0: " +<span style="color: rgba(0, 0, 0, 1)"> bitIndex); </span><span style="color: rgba(0, 0, 255, 1)">int</span> wordIndex =<span style="color: rgba(0, 0, 0, 1)"> wordIndex(bitIndex); expandTo(wordIndex); words[wordIndex] </span>|= (1L << bitIndex); <span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)"> Restores invariants</span>
所以，我们可以得出一个浅显的结论，bitmap 很简单，一点都不神秘。但是，大道至简，它高性能，它自然还是有好处的，咱们该用还得用。显然，java 版本的 bitmap 虽然很很好用，但是它只是应用级别的，只能在进程内使用，有太多的其他问题没考虑，所以咱们还得要依赖于 redis 的 bitmap.
问题：如果我有很多的数字标识想要写入 redis 中，然后再进行读取判定，该怎么办呢？
很简单的，我们可以一个个地调用 setbit 命令，依次写入 redis 中。这自然能解决问题，但是明显会带来很多的网络 io。
其次，我们可以使用 pipeline 调用 setbit 进行批量写入。这当然是一种优化方案，只是仍然不是最优。
那有没有什么更好的办法呢？
3. java 和 redis 的 bitmap 互操作
对于批量的操作，redis 是基于 string 实现，而 java 是基于 bitset 实现。其功能都基本差不多，判定、写入、交并差运算。那么，除了一个个按照各自语法进行添加外，有没有可能进行数据结构上的对等呢？
这个思路是很自然的，因为我们已经完全理解了各自的实现原理，为什么不呢？直接将 BitSet 转换为 byte[] 写入 redis，直接将 redis 的 bitmap 当作 string 读出来不就可以了吗？
事实真是如此吗？实际上有点差别，原因是一个是大端存储，一个是小端存储。
比如：比如对于存储 byte 值: 00000010 , redis 中会解释为偏移为 6 的值为 1, 而在 java 中则会解析为数字 2 存在于 bitmap 中。也就是说两个的判定结果是不一样的，一个是 6，一个是 2。如果把 java 中的值给调换一下，变成 01000000，那么就和 redis 是一样的了。
而从 redis 中转变到 java 中，则需要将每个 byte 位做一逆向操作判定，具体实现如下：
@Test public void testSetBitmapData2Redis() { //创建一个连接 Jedis jedis = new Jedis("localhost", 6379); // 正向设置 redis bitmap String testBitmapKey = "mybitmap1"; jedis.set(testBitmapKey.getBytes(), genRedisBitmap(2, 55, 133, 65537, 10_0000)); Assert.assertEquals("bitmap 取值不正确", true, jedis.getbit(testBitmapKey, 2L)); Assert.assertEquals("bitmap 取值不正确", true, jedis.getbit(testBitmapKey, 133L)); Assert.assertEquals("bitmap 取值不正确", true, jedis.getbit(testBitmapKey, 65537L)); Assert.assertEquals("bitmap 取值不正确", true, jedis.getbit(testBitmapKey, 10_0000L)); Assert.assertEquals("bitmap 取值不正确", false, jedis.getbit(testBitmapKey, 3L)); //在 redis 中获取 name 值 byte[] redisBitmapData = jedis.get("mybitmap1".getBytes()); BitSet bitSet = convertRedisBitmapToJava(redisBitmapData); Assert.assertTrue("redisBitmap 反解不正确", bitSet.get(2)); Assert.assertTrue("redisBitmap 反解不正确", bitSet.get(133)); Assert.assertTrue("redisBitmap 反解不正确", bitSet.get(65537)); Assert.assertTrue("redisBitmap 反解不正确", bitSet.get(10_0000)); Assert.assertFalse("redisBitmap 反解不正确", bitSet.get(332)); jedis.close();}</span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)"> 将redis的bitmap转换为java 的bitset</span> <span style="color: rgba(0, 0, 255, 1)">private</span> BitSet convertRedisBitmapToJava(<span style="color: rgba(0, 0, 255, 1)">byte</span><span style="color: rgba(0, 0, 0, 1)">[] redisBitmapData) { </span><span style="color: rgba(0, 0, 255, 1)">int</span> len =<span style="color: rgba(0, 0, 0, 1)"> redisBitmapData.length; BitSet bitSet </span>= <span style="color: rgba(0, 0, 255, 1)">new</span><span style="color: rgba(0, 0, 0, 1)"> BitSet(); </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)"> 每个 byte 8位, 所以整个bitmap 的长度为 len * 8</span> <span style="color: rgba(0, 0, 255, 1)">for</span> (<span style="color: rgba(0, 0, 255, 1)">int</span> i = 0; i < len * 8; i++<span style="color: rgba(0, 0, 0, 1)">) { </span><span style="color: rgba(0, 0, 255, 1)">byte</span> currentSegment = redisBitmapData[i / 8<span style="color: rgba(0, 0, 0, 1)">]; </span><span style="color: rgba(0, 0, 255, 1)">if</span>(currentSegment == 0<span style="color: rgba(0, 0, 0, 1)">) { </span><span style="color: rgba(0, 0, 255, 1)">continue</span><span style="color: rgba(0, 0, 0, 1)">; } </span><span style="color: rgba(0, 0, 255, 1)">if</span>((currentSegment & (1 << (7 - (i % 8) ) ) ) != 0<span style="color: rgba(0, 0, 0, 1)"> ) { bitSet.set(i); } } </span><span style="color: rgba(0, 0, 255, 1)">return</span><span style="color: rgba(0, 0, 0, 1)"> bitSet; } </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)"> 生成redis的bitmap数据</span> <span style="color: rgba(0, 0, 255, 1)">private</span> <span style="color: rgba(0, 0, 255, 1)">byte</span>[] genRedisBitmap(<span style="color: rgba(0, 0, 255, 1)">int</span><span style="color: rgba(0, 0, 0, 1)">... items) { BitSet bitSet </span>= <span style="color: rgba(0, 0, 255, 1)">new</span><span style="color: rgba(0, 0, 0, 1)"> BitSet(); </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)"> 2 55 133</span> <span style="color: rgba(0, 0, 255, 1)">for</span> (<span style="color: rgba(0, 0, 255, 1)">int</span><span style="color: rgba(0, 0, 0, 1)"> k : items) { bitSet.set(k); } </span><span style="color: rgba(0, 0, 255, 1)">byte</span>[] targetBitmap =<span style="color: rgba(0, 0, 0, 1)"> bitSet.toByteArray(); convertJavaToRedisBitmap(targetBitmap); </span><span style="color: rgba(0, 0, 255, 1)">return</span><span style="color: rgba(0, 0, 0, 1)"> targetBitmap; } </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)"> 将java中的字节数组转换为redis的bitmap数据形式</span> <span style="color: rgba(0, 0, 255, 1)">private</span> <span style="color: rgba(0, 0, 255, 1)">void</span> convertJavaToRedisBitmap(<span style="color: rgba(0, 0, 255, 1)">byte</span><span style="color: rgba(0, 0, 0, 1)">[] bytes) { </span><span style="color: rgba(0, 0, 255, 1)">int</span> len =<span style="color: rgba(0, 0, 0, 1)"> bytes.length; </span><span style="color: rgba(0, 0, 255, 1)">for</span> (<span style="color: rgba(0, 0, 255, 1)">int</span> i = 0; i < len; i++<span style="color: rgba(0, 0, 0, 1)">) { </span><span style="color: rgba(0, 0, 255, 1)">byte</span> b1 =<span style="color: rgba(0, 0, 0, 1)"> bytes[i]; </span><span style="color: rgba(0, 0, 255, 1)">if</span>(b1 == 0<span style="color: rgba(0, 0, 0, 1)">) { </span><span style="color: rgba(0, 0, 255, 1)">continue</span><span style="color: rgba(0, 0, 0, 1)">; } </span><span style="color: rgba(0, 0, 255, 1)">byte</span> transByte = 0<span style="color: rgba(0, 0, 0, 1)">; </span><span style="color: rgba(0, 0, 255, 1)">for</span> (<span style="color: rgba(0, 0, 255, 1)">byte</span> j = 0; j < 8; j++<span style="color: rgba(0, 0, 0, 1)">) { transByte </span>|= (b1 & (1 << j)) >> j << (7 -<span style="color: rgba(0, 0, 0, 1)">j); } bytes[i] </span>=<span style="color: rgba(0, 0, 0, 1)"> transByte; } }</span></pre>
经验证，将 8 位的 byte 进行位置反转，能够完美匹配两种数据结构。这样就可以做到 redis bitmap 的零存整取，整存零取，整存整取了。
如此一来，就可以轻松将整个 bitmap 进行初始化设置到 redis 中，从而在 redis 的 bitmap 中，使用 getbit 进行高效判定了。