Scul Blog
Published at

Làm tí Redis - P1 - Simple Dynamic Strings

Làm tí Redis - P1 - Simple Dynamic Strings

Cấu trúc dữ liệu chuỗi của Redis

Table of Contents

Preface

Tài liệu được tham khảo từ source code của Redis v8. Các bạn có thể đọc tại đây: Redis repository

Thích đọc code Go hơn? Có luôn. Mình có 1 bản minimal về các data structure tại đây: Gedis repository

Tại sao Redis lại đẻ ra hẳn một cái kiểu dữ liệu mới cho String mà không dùng thẳng kiểu dữ liệu sẵn có của C?

Quan sát C một tí, ta thấy như sau:

  • Để define một string trong C, ta có: char str[] = "Hello World"
  • Lúc này, str đóng vai trò là một con trỏ, trỏ vào phần tử đầu tiên của mảng char. Hay nói cách khác, str có kiểu dữ liệu là char *.
  • Trong C, ta quy định kết thúc của chuỗi là kí tự \0, hay còn gọi là NULL terminator (tương ứng với 0 khi chuyển sang int). Tức là ta không thể set một phần tử ở giữa chuỗi thành \0 vì nó sẽ kết thúc chuỗi ngay lập tức tại phần tử đó (binary safe problem).

Thế nhưng, Redis có một command cho phép nghịch để biến bit thứ 36 của chuỗi str thành 1:

> SETBIT str 36 1
OK

Vậy nếu, các bit được biến đổi khiến cho một byte của value ở str thành kí tự \0 thì sao? Với string truyền thống, nó sẽ end luôn mặc dù ở đằng sau còn data. Như vậy là hư, là chưa tốt.

Thực tế hơn, nhiều usecase cho phép Redis lưu trữ các định dạng khác nhau, giả sử như các file JPEG, hay một cái encrypted password nào đó mà nó có chứa byte 0. Nếu sử dụng kiểu dữ liệu truyền thống, nó sẽ dẫn đến việc dừng ngay khi gặp NULL terminator trong khi dữ liệu vẫn còn ở phía sau.

Do đó, Redis sử dụng một kiểu dữ liệu mới gọi là Simple Dynamic Strings.

Data Structure

Cấu trúc cơ bản của SDS được mô tả như sau:

+--------+-------------------------------+-----------+
| Header | Binary safe C alike string... | Null term |
+--------+-------------------------------+-----------+
         |
         `-> Pointer returned to the user.

Tuy nhiên, phần triển khai sẽ ảo ma hơn là những gì ta thấy ở trên:

typedef char *sds;

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};


#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4
#define SDS_TYPE_MASK 7
#define SDS_TYPE_BITS 3
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
#define SDS_TYPE_5_LEN(s) (((unsigned char)(s[-1])) >> SDS_TYPE_BITS)

Trước tiên, ta cần làm rõ __attribute__ ((__packed__)) là cái gì. Đây là một cách để nói với complier rằng: "Hey bro, đừng có add padding bytes để align memory giúp tao. Nén mớ đó lại gần sát nhau là được". Với các bạn từng học qua C thì cũng biết, nó thêm padding vào để tăng tốc độ đọc lên do CPU nó đọc lẹ hơn nếu data đã được align sẵn, tuy nhiên struct size cũng sẽ tăng lên. Giả sử với ví dụ dưới đây:

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;   // 1 byte
    uint8_t alloc; // 1 byte
    unsigned char flags; // 1 byte
    char buf[];
};

Nếu để mặc định, compiler có thể thêm padding byte và biến nó thành 4 byte hoặc 8 byte struct. Tuy nhiên, khi đã thêm __attribute__ ((__packed__)) thì nó sẽ giữ nguyên 3 byte. Redis làm điều này đơn giản vì nếu mà có hàng triệu hay hàng tỉ key mà data bé xíu thì nó sẽ dư ra một lượng cực kì lớn memory chỉ dành cho padding.

Quay lại ý chính, ta sẽ thắc mắc, tại sao lại có typedef char *sds. Vậy thì khác quái gì string bình thường đâu. Lý do sds lại define vậy là để hỗ trợ việc sử dụng sds thay cho string như bình thường (backward compatible). Những thứ gì bạn làm được với string thì với sds bạn cũng làm được tương tự. Chẳng hạn như việc print out hay các operation.

Vậy, làm sao một sds biết header nó nằm ở đâu khi mà chính sds còn không phải là một struct? Lúc này, ma thuật thực sự xảy ra ở đây. Chú ý đến toàn bộ header được define ở trên, ta thấy:

struct __attribute__ ((__packed__)) sdshdrX {
    inttype_t len;        // X bytes
    inttype_t alloc;      // X bytes
    unsigned char flags; // 1 byte
    char buf[];          // 0 bytes (Just a marker!)
};

Vậy, byte flags luôn nằm ở cuối cùng của một header. Từ đó, nếu sds chỉ là phần ở giữa theo cấu trúc đã mô tả, ta có thể đơn giản nhảy ngược về 1 byte đằng trước để biết mình là kiểu gì:

static inline unsigned char sdsType(const sds s) {
    unsigned char flags = s[-1];
    return flags & SDS_TYPE_MASK;
}

Lúc này, ta đã biết nó là type nào rồi thì mọi thứ trở nên đơn giản, giả sử như việc tính length sẽ xảy ra như sau:

static inline size_t sdslen(const sds s) {
    switch (sdsType(s)) {
        case SDS_TYPE_5: return SDS_TYPE_5_LEN(s);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->len;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->len;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->len;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}

Nhìn lại dòng define sau:

#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

Để lấy được header, nó chỉ việc đơn giản thực hiện một phép trừ để lùi về k bytes, với k là size của header struct. Lúc này ta có được pointer trỏ vào đầu header, khi đã có header, ta chỉ việc xài nó như bình thường.

Creation and Destruction

Vậy, khi khởi tạo một sds, ta không chỉ đơn giản khởi tạo mỗi string, mà còn phải allocate memory space cho header ở phía trước nó.

sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}

sds sdsnewlen(const void *init, size_t initlen) {
    return _sdsnewlen(init, initlen, 0);
}

sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
    void *sh;

    char type = sdsReqType(initlen);
    /* Empty strings are usually created in order to append. Use type 8
     * since type 5 is not good at this. */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type);
    size_t bufsize;

    assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */
    sh = trymalloc?
        s_trymalloc_usable(hdrlen+initlen+1, &bufsize) :
        s_malloc_usable(hdrlen+initlen+1, &bufsize);
    if (sh == NULL) return NULL;

    adjustTypeIfNeeded(&type, &hdrlen, bufsize);
    return sdsnewplacement(sh, bufsize, type, init, initlen);
}

Tương tự, với việc free memory khi xoá nó đi, ta cũng cần phải xoá cả phần header, free size sẽ tương tự với phần size đã được khởi tạo phía trên bằng malloc:

#define s_free free

void sdsfree(sds s) {
    if (s == NULL) return;
    s_free((char*)s-sdsHdrSize(s[-1]));
}

Concatenation Operation (Append)

Ta sẽ xem cách mà sds quản lý vùng nhớ khi cần một cấp phát lớn hơn cho dữ liệu cần thêm vào thông qua nối chuỗi.

/* Append the specified binary-safe string pointed by 't' of 'len' bytes to the
 * end of the specified sds string 's'.
 *
 * After the call, the passed sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call. */
sds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s);

    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    memcpy(s+curlen, t, len);
    sdssetlen(s, curlen+len); // Set the value for length in the header
    s[curlen+len] = '\0';
    return s;
}

/* Append the specified null terminated C string to the sds string 's'.
 *
 * After the call, the passed sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call. */
sds sdscat(sds s, const char *t) {
    return sdscatlen(s, t, strlen(t));
}

/* Append the specified sds 't' to the existing sds 's'.
 *
 * After the call, the modified sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call. */
sds sdscatsds(sds s, const sds t) {
    return sdscatlen(s, t, sdslen(t));
}


/* Enlarge the free space at the end of the sds string more than needed,
 * This is useful to avoid repeated re-allocations when repeatedly appending to the sds. */
sds sdsMakeRoomFor(sds s, size_t addlen) {
    return _sdsMakeRoomFor(s, addlen, 1);
}

Hàm _sdsMakeRoomFor hơi dài, mình để ở cuối nhé. Click here

Trong hàm sdscatlen, đầu tiên nó thực hiện gọi hàm sdsMakeRoomFor để đảm bảo rằng string s có đủ size để append thêm một lượng data có kích thước là len vào. Lúc này sdsMakeRoomFor có thể sẽ allocate thêm memory hoặc không, tuỳ vào việc có cần resize lại hay không.

sdsMakeRoomFor quyết định thông qua điều kiện như sau:

  • Nếu hiện tại còn đủ bộ nhớ cho len aka avail >= addlen thì không cần làm gì cả.
  • Nếu không đủ, thực hiện cấp phát bộ nhớ như sau:
    • Redis define SDS_MAX_PREALLOC = 1MB
    • Nếu size cần cấp phát < SDS_MAX_PREALLOC thì ta sẽ cấp phát gấp đôi.
    • Nếu vượt quá, ta sẽ cấp phát thêm SDS_MAX_PREALLOC mỗi lần, nghĩa là tăng 1MB mỗi lần.
    • Dựa trên size mới, có thể sẽ có khả năng ta cần đổi header type cho sds mới. Khi đổi, ta cần thực hiện relocate lại toàn bộ sds mới (bao gồm cả header) thông qua malloc.
    • Nếu không thay đổi header, realloc được sử dụng để kiểm tra ở vùng hiện tại liệu còn đủ memory cho sds mới? Nếu có, chỉ cần dùng memmove và trả về address tương tự address của sds cũ. Nếu không, nó phải kiếm một vùng nhớ khác đủ sức chứa cho sds mới, sau đó trả về address mới.

Nhìn chung, ta có thể thấy các hàm trong sds thường trả về sds. Điều này là vì thông qua các operation, ta không thể biết được rằng nó có thực hiện đổi vùng nhớ hay không? Nếu có đổi thì vùng nhớ cũ lúc này đã invalid nên ta không dùng được nữa. Vì vậy, assign lại address sau các operation là một điều nên làm.

Other functions

Hàm sdsResize cũng sẽ được thực hiện với các quy trình khá tương tự sdsMakeRoomFor. Ta chỉ cần biết quy trình nó diễn ra như nào, cấp phát, thu hồi ra sao là được rồi.

Ngoài ra, còn có các function khác như:

sdslen(const sds s): Get sds string length.
sdssetlen(sds s, size_t newlen): Set sds string length.
sdsinclen(sds s, size_t inc): Increase sds string length.
sdsalloc(const sds s): Get sds string capacity.
sdssetalloc(sds s, size_t newlen): Set sds string capacity.
sdsavail(const sds s): Get sds string free space (i.e., alloc - len).
sdsHdrSize(char type): Get header size based on header type.

Thế thôi, để mà giải thích hết thì khá dài, làm vậy thì cái blog loằng ngoằng lắm, nếu có thời gian thì mình sẽ đọc và update sau hẹ hẹ.

Note

_sdsMakeRoomFor

/* Enlarge the free space at the end of the sds string so that the caller
 * is sure that after calling this function can overwrite up to addlen
 * bytes after the end of the string, plus one more byte for nul term.
 * If there's already sufficient free space, this function returns without any
 * action, if there isn't sufficient free space, it'll allocate what's missing,
 * and possibly more:
 * When greedy is 1, enlarge more than needed, to avoid need for future reallocs
 * on incremental growth.
 * When greedy is 0, enlarge just enough so that there's free space for 'addlen'.
 *
 * Note: this does not change the *length* of the sds string as returned
 * by sdslen(), but only the free buffer space we have. */
sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);
    size_t len, newlen, reqlen;
    char type, oldtype = sdsType(s);
    int hdrlen;
    size_t bufsize, usable;
    int use_realloc;

    /* Return ASAP if there is enough space left. */
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    reqlen = newlen = (len+addlen);
    assert(newlen > len);   /* Catch size_t overflow */
    if (greedy == 1) {
        if (newlen < SDS_MAX_PREALLOC)
            newlen *= 2;
        else
            newlen += SDS_MAX_PREALLOC;
    }

    type = sdsReqType(newlen);

    /* Don't use type 5: the user is appending to the string and type 5 is
     * not able to remember empty space, so sdsMakeRoomFor() must be called
     * at every appending operation. */
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    assert(hdrlen + newlen + 1 > reqlen);  /* Catch size_t overflow */
    use_realloc = (oldtype == type);
    if (use_realloc) {
        newsh = s_realloc_usable(sh, hdrlen + newlen + 1, &bufsize, NULL);
        if (newsh == NULL) return NULL;
        s = (char*)newsh + hdrlen;
        if (adjustTypeIfNeeded(&type, &hdrlen, bufsize)) {
            memmove((char *)newsh + hdrlen, s, len + 1);
            s = (char *)newsh + hdrlen;
            s[-1] = type;
            sdssetlen(s, len);
        }
    } else {
        /* Since the header size changes, need to move the string forward,
         * and can't use realloc */
        newsh = s_malloc_usable(hdrlen + newlen + 1, &bufsize);
        if (newsh == NULL) return NULL;
        adjustTypeIfNeeded(&type, &hdrlen, bufsize);
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    usable = bufsize - hdrlen - 1;
    assert(type == SDS_TYPE_5 || usable <= sdsTypeMaxSize(type));
    sdssetalloc(s, usable);
    return s;
}