Introduction to bitmap

bitmap is also called bitops in Redis. It represents the corresponding value or state of an element through a bit bit.
In fact, the implementation of bitmap does not add a new data type in Redis. Its underlying implementation is actually a String, that is, a char buf []. You should know that 1Byte = 8bit, so each subscript in this array corresponds to the state of 8 elements.
The key in bitmap is also an element. If the key can only be an integer of > = 0, it can be used as an offset based on bit. We can call it offset in Redis, so they don't need additional space to save like the subscript of the array. Each getbit/setbit can be regarded as an operation on the value corresponding to the subscript of the array, Therefore, bitmap itself will greatly save storage space.

• advantage
  • Save space
  • High efficiency. The time complexity of setbit and getbit is O(1), and the operation efficiency of other bits is also high
• shortcoming
  • In essence, there is only the difference between 0 and 1, so it can only be used for status recording
  • The number of keys that need to be counted is small, but the scenario with large span between keys and keys is not applicable

bitmap common operations

• SETBIT key offset value: sets or modifies the value of the bit (value) of the offset on the key; return is not the status of success or failure, but the old value originally stored on the modified offset
• GETBIT key offset: returns the value of the offset on the specified key. If the key does not exist, it returns 0;
• bit key: returns the number of bits set to 1 on the specified key;
• BITOP operation destkey key [key ...] :
  • Bitop and destkey [key...]: one or more keys are logically combined, and the results are saved to destkey;
  • Bitop or destkey [key...]: for one or more logical or keys, save the result to destkey;
  • Bitop XOR destkey [key...]: logical XOR of one or more keys, and the results are saved to destkey;
  • Bitop NOT destkey: for a key that is NOT logical, save the result to destkey; Note: in the NOT operation, there can only be one key
    

Application scenario

• Various user activity / login statistics
• Broadcast message user read unread flag

Source code reading

Because bitmap is not a new data type, its expression is a char buf [], so let's take a look at the source code of setbit

/* 
 * Find the target bit of the byte to be set, then record the original value of this bit, and finally set this bit as the target value
 * GETBIT The command is consistent with its implementation
 */
void setbitCommand(client *c) {
    robj *o;
    char *err = "bit is not an integer or out of range";
    size_t bitoffset;
    ssize_t byte, bit;
    int byteval, bitval;
    long on;
     // Parse offset
    if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset,0,0) != C_OK)
        return;
     // Parse value
    if (getLongFromObjectOrReply(c,c->argv[3],&on,err) != C_OK)
        return;

    /* bit The bit can only be 0 / 1, otherwise the direct return fails */
    if (on & ~1) {
        addReplyError(c,err);
        return;
    }
	/* 
	 * Find string object
	 * 		If it does not exist, a string object is created
	 * 		If the string exists but the space is insufficient, the capacity will be expanded
	 */
    if ((o = lookupStringForBitCommand(c,bitoffset)) == NULL) return;

    /* 
     * Calculate the byte position corresponding to the element (because 1byte = 8bit as mentioned above)
     * 		Bit operation bitoffset > > 3 is equivalent to bitoffset / 8
     */
    byte = bitoffset >> 3;
    // Get the corresponding byte
    byteval = ((uint8_t*)o->ptr)[byte];
    // Calculate the position of bit (based on the current byte)
    bit = 7 - (bitoffset & 0x7); 
    // Get the old bit value and use it to return after the operation is successful
    bitval = byteval & (1 << bit); 

    /* Update the bit in the byte and set its value */
    byteval &= ~(1 << bit);
    byteval |= ((on & 0x1) << bit);
    ((uint8_t*)o->ptr)[byte] = byteval;
    // Send modification notice
    signalModifiedKey(c,c->db,c->argv[1]);
    notifyKeyspaceEvent(NOTIFY_STRING,"setbit",c->argv[1],c->db->id);
    server.dirty++;
    // Returns the old value to the client
    addReply(c, bitval ? shared.cone : shared.czero);
}

Bloom filter

Bloom Filter is an ingenious probabilistic data structure proposed by Howard Bloom in 1970. It can tell you that something must not exist or may exist. When bloom says something exists, it may not exist; When the Bloom Filter says something doesn't exist, it must not exist.
The implementation of butmap is based on butmap.
The core of Bloom filter is to perform n different hash operations on the key to obtain n different hash values, then take the hash value as the offset, and mark the value corresponding to the offset as 1 in bitmap. When any key enters to judge whether it exists, it will calculate the corresponding n hash values through those hash functions, and then judge whether the values of * * offset * * corresponding to the hash value are all equal to 1. If any value is 0, the key must not exist; Otherwise, the key may exist.

Illustrated bloom filter

See how the bloom filter solves the cache penetration problem.

Your praise is the biggest driving force for my creation. If it's good, can I have a three company