This is the 19th day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021

The cause of

Yesterday I saw an interview question in the group, the topic is:

Suppose there are 100 million keys in Redis, and 10W of them start with a fixed, known prefix. What if you could find all of them and explain the underlying principles of the methods used?Copy the code

In the end, there are three commands:

  • keys: Used to find all matches a given patternpattern 的 key
  • smembers: Returns the collectionkeyAll members of the
  • Scan: Incrementally iterates through all database keys in the current database

Keys and smembers return all members in O(n)O(n)O(n) O(n). Although the time complexity of SCAN is also O(n)O(n)O(n), it adopts the incremental mode. In a scenario with a large amount of data, it does not block the thread all the time like the previous two.

I’m not sure if the answers are from an Internet search. So I went to Github and downloaded the redis source code to see what it looked like.

github.com/redis/redis

The source code

There is a command table in the source file, located in redis\ SRC \server.c, where we can quickly find the corresponding function entry for each command.

Once the entry to the command is found, we can jump to see its corresponding implementation.

keys

In the keys command function, you can see that it iterates through the entire key space dictionary, adding those matching the given pattern to the return list.

void keysCommand(client *c) {
    dictIterator *di;
    dictEntry *de;
    sds pattern = c->argv[1]->ptr;
    int plen = sdslen(pattern), allkeys;
    unsigned long numkeys = 0;
    void *replylen = addReplyDeferredLen(c);

    di = dictGetSafeIterator(c->db->dict);
    allkeys = (pattern[0] = =The '*' && plen == 1);
    while((de = dictNext(di)) ! =NULL) {
        sds key = dictGetKey(de);
        robj *keyobj;

        if (allkeys || stringmatchlen(pattern,plen,key,sdslen(key),0)) {
            keyobj = createStringObject(key,sdslen(key));
            if(! keyIsExpired(c->db,keyobj)) { addReplyBulk(c,keyobj); numkeys++; } decrRefCount(keyobj); } } dictReleaseIterator(di); setDeferredArrayLen(c,replylen,numkeys); }Copy the code

smembers

The smembers command invokes the sinterGenericCommand function, which passes a range of 0 to indicate a global search.

/* SINTER key [key ...] * /
void sinterCommand(client *c) {
    sinterGenericCommand(c, c->argv+1,  c->argc- 1.NULL.0.0);
}

/* SINTER / SINTERSTORE / SINTERCARD * * 'cardinality_only' work for SINTERCARD, * * 'limit' work for SINTERCARD. Passing 0 means no limit. */
void sinterGenericCommand(client *c, robj **setkeys,
                          unsigned long setnum, robj *dstkey,
                          int cardinality_only, unsigned long limit) {}
Copy the code

scan

ScanGenericCommand code is too long to be posted here. If you are interested, you can download the source code and search it.

The approximate implementation logic of this function should be to parse the attached parameters to get the length of data to be returned and the value of the cursor, and then iterate through the collection to get the required data.

The specific entry function is disScan.

/* The SCAN command completely relies on scanGenericCommand. */
void scanCommand(client *c) {
    unsigned long cursor;
    if (parseScanCursorOrReply(c,c->argv[1],&cursor) == C_ERR) return;
    scanGenericCommand(c,NULL,cursor);
}

/* This command implements SCAN, HSCAN and SSCAN commands. * If object 'o' is passed, then it must be a Hash, Set, or Zset object, * Otherwise if 'o' is NULL, the command will operate on the dictionary associated with the current database * * When 'O' is not NULL, the function assumes that the first argument in the client argument vector is a key, * so it skips it to resolve the options before iterating. * * In the case of Hash objects, this function returns the fields and values of each element on the Hash. * /
void scanGenericCommand(client *c, robj *o, unsigned long cursor) {}
Copy the code

The last

As I was born in Java, I am not familiar with the syntax of C/C ++, the remarks are combined with annotations after reading the source code to understand, if there are remarks in the wrong place, I hope you can help give advice!