The sadd command stores data into the set structure

> sadd a 1
(integer1)Copy the code

Smembers can check the stored content

> smembers a
1) "1"
Copy the code

The sadd command performs tracing

The entry point for sadd execution is at saddCommand, and if the key does not exist the first thing to do is to confirm the underlying storage structure

 Code.SLICE.source("robj *setTypeCreate(sds value) {" +
      " if (isSdsRepresentableAsLongLong(value,NULL) == C_OK)" +
      " return createIntsetObject();" +
      " return createSetObject();" +
      "}")
      .interpretation("See if the value to be added to the set can be converted to long long. If so, set is IntSet, otherwise hash table.");
Copy the code

Once you’ve determined the structure, you can add to it

  • If it was hashtable, insert it;
  • If it was an intset, we need to see if the newly inserted element meets the intset structure, otherwise we convert it to a Hashtable
Code.SLICE.source("else if (subject->encoding == OBJ_ENCODING_INTSET) {" +
        " if (isSdsRepresentableAsLongLong(value,&llval) == C_OK) {" +
        " uint8_t success = 0;" +
        " subject->ptr = intsetAdd(subject->ptr,llval,&success);" +
        " if (success) {" +
        " /* Convert to regular set when the intset contains" +
        " * too many entries. */" +
        " if (intsetLen(subject->ptr) > server.set_max_intset_entries)" +
        " setTypeConvert(subject,OBJ_ENCODING_HT);" +
        " return 1;" +
        "}" +
        " } else {" +
        " /* Failed to get integer from object, convert to regular set. */" +
        " setTypeConvert(subject,OBJ_ENCODING_HT);" +
        "" +
        " /* The set *was* an intset and this value is not integer" +
        " * encodable, so dictAdd should always work. */" +
        " serverAssert(dictAdd(subject->ptr,sdsdup(value),NULL) == DICT_OK);" +
        " return 1;" +
        "}" +
        "}")
        .interpretation("Intset, another data structure of set, continues to increment in set as long as the current data can be converted to longlong, otherwise convert structure to HashTable.")
        .interpretation("1: After adding intset, if the set has exceeded the configured set_max_intset_entries number, convert to hashtable");
Copy the code

When inserting into intSet, we need to make sure that we don’t store the same elements, so we first look for elements that have the same value

Code.SLICE.source("int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;")
        .interpretation("Write down the subscripts of the minimum and maximum.");
Code.SLICE.source(" if (intrev32ifbe(is->length) == 0) {" +
        " if (pos) *pos = 0;" +
        " return 0;" +
        " } else {" +
        " /* Check for the case where we know we cannot find the value," +
        " * but do know the insert position. */" +
        " if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {" +
        " if (pos) *pos = intrev32ifbe(is->length);" +
        " return 0;" +
        " } else if (value < _intsetGet(is,0)) {" +
        " if (pos) *pos = 0;" +
        " return 0;" +
        "}" +
        "}")
        .interpretation("Dealing with boundary cases")
        .interpretation("1: If the set is empty, just insert it at the beginning.")
        .interpretation("2: If the newly inserted value is less than the current minimum value, just insert at the beginning")
        .interpretation("3: Insert at the end if the new value is greater than the current maximum value");
Code.SLICE.source("while(max >= min) {" +
        " mid = ((unsigned int)min + (unsigned int)max) >> 1;" +
        " cur = _intsetGet(is,mid);" +
        " if (value > cur) {" +
        " min = mid+1;" +
        " } else if (value < cur) {" +
        " max = mid-1;" +
        " } else {" +
        " break;" +
        "}" +
        "}")
        .interpretation("Binary search, finding where to insert, either finding where the existing value element is, or finding where to insert.");
Copy the code

conclusion

  1. Set uses intSet and hashtable.
  2. Intset is arranged in ascending order;
  3. Intset can be divided into different data structures according to the value size to save space

The appendix

Sadd command source code complete tracking process

Redis development and operation

Design and implementation of Redis