Redis’s bitset Battle

  redis

Order

This article mainly studies the use of redis’ bitset data structure.

Relevant command

SETBIT

The time complexity is O(1)

setbit login.20180906 102400000 0
setbit login.20180905 201400000 1

GETBIT

The time complexity is O(1)

getbit login.20180905 201400000

BITOP

Time complexity is O(N)

bitop or login.9m.week1or login.20180905 login.20180906
getbit login.9m.week1or 201400000

Mainly do bitset and, or, xor, not operations, the results exist in the new bitset, note that the time complexity is O(N)

BITPOS

Time complexity is O(N)

bitpos login.20180905 1

Returns the offset with the specified value appearing first in the specified starting position in the specified bitset. start is not passed. the default estimate for end is 0,-1

BITCOUNT

Time complexity is O(N)

bitcount login.20180905

Count the number of 1s in bitset

the usage scenarios

Assuming there is a sign-in requirement, the functions to be realized are as follows:

  • Show if you have already signed in on that day. You cannot sign in again if you have already signed in.
  • Show the check-in status/history of the latest week or the latest month (you can only record the check-in time of each day without detailed records, and only record whether or not to check in each day)
  • Judge whether to sign in continuously. If you sign in continuously this week, you will be given the chance to draw a lottery.

Here we can use redis bitset to implement:

Sign in

boolean originValue = redisTemplate.opsForValue().setBit(uidYearKey,dayIndx,true);
  • The key here consists of uid and year, and then offset uses index of day.
  • If each uid has one key for each year, too many users may cause redis to have too many keys.

Get check-in data

    BitSet bitSet = fromByteArrayReverse(redisTemplate.opsForValue().get(uidYearKey).getBytes());
    public static BitSet fromByteArrayReverse(final byte[] bytes) {
        final BitSet bits = new BitSet();
        for (int i = 0; i < bytes.length * 8; i++) {
            if ((bytes[i / 8] & (1 << (7 - (i % 8)))) != 0) {
                bits.set(i);
            }
        }
        return bits;
    }
  • Here is a note that java reads bytes from right to left from small to large (main aspects), while bytes stored by redis are from left to right (Small end), so here reading bytes into BitSet needs to be reversed.

BitSet Range

public BitSet get(int fromIndex, int toIndex) {
    //......
}
  • BitSet has a method that can range according to index, and then can use the new BitSet to make relevant statistics, such as BitSet cardinality.

Summary

  • For bitset, its advantage is to save memory. If the user id is directly used as offset to store the corresponding value, this saves a lot of space compared with hash. Bitset can be used to realize scenes like counting the number of people who have logged in continuously in the last N days.
  • Attention should be paid to the operation of bitset. the time complexity of each operation is O(1) for getbit and setbit, O(N) for bitop, bitcount and bitpos. attention should be paid when n is relatively large, which may be a potential slow query.

doc