【Redis系列】数据结构SDS简单动态字符串源码分析

SDS is Redis’s custom string handling library that provides a more efficient and flexible alternative to C strings. Here are the key aspects:

1. Data Structure:

• SDS uses a flexible header structure with 5 different types (sdshdr5, sdshdr8, sdshdr16, sdshdr32, sdshdr64)
• Each header contains:
  • len: The current length of the string
  • alloc: The total allocated space (except for sdshdr5)
  • flags: 3 bits for type and 5 bits for other uses
  • buf[]: The actual string buffer

2. Key Features:

a) Binary Safety:

• Unlike C strings, SDS strings can contain any binary data including null characters
• Length is stored explicitly in the header rather than determined by null terminator
• Still maintains null termination for compatibility with C functions

b) O(1) Length Operation:

static inline size_t sdslen(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5: return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8: return SDS_HDR(8,s)->len;
        // ... other cases
    }
}

c) Space Optimization:

• Uses different header sizes based on string length:
  • TYPE_5: For very short strings (< 32 bytes)
  • TYPE_8: For short strings
  • TYPE_16/32/64: For progressively larger strings
• Prevents buffer overflow by pre-allocating extra space

sds sdsMakeRoomFor(sds s, size_t addlen) {
    // Doubles allocation for small strings
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
}

d) Memory Management:

• Tracks allocated space separately from used space
• Reduces reallocation frequency by pre-allocating extra space
• Provides functions to manage memory explicitly:
  • sdsMakeRoomFor(): Ensures space for additions
  • sdsRemoveFreeSpace(): Trims excess allocation
  • sdsResize(): Adjusts allocation size

3. Common Operations:

a) Creation:

sds sdsnew(const char *init);      // From C string
sds sdsnewlen(void *init, size_t); // From binary data
sds sdsempty(void);                // Empty string

b) Modification:

sds sdscat(sds s, const char *t);    // Append C string
sds sdscatsds(sds s, const sds t);   // Append SDS string
sds sdscpy(sds s, const char *t);    // Copy C string
void sdstrim(sds s, const char *cset); // Remove chars from ends

c) Formatting:

sds sdscatprintf(sds s, const char *fmt, ...);  // Printf-style formatting
sds sdscatfmt(sds s, char const *fmt, ...);     // Faster custom formatter

4. Benefits over C strings:

• Constant time length operations
• No buffer overflows
• Binary safe
• Compatible with C string functions
• Reduced memory reallocations
• Explicit memory management
• Multiple size classes for space efficiency

This implementation is crucial for Redis’s performance as strings are one of its fundamental data types. The SDS library provides the efficiency and safety needed for a high-performance database system while maintaining compatibility with C string functions when needed.

如果你不想看代码，直接从这部分开始看

Redis’s SDS (Simple Dynamic String) is a custom string handling library that provides an efficient and flexible alternative to C strings. Here are the key aspects:

1. Data Structure:

• Uses flexible headers (sdshdr5/8/16/32/64) containing:
  • len: Current string length
  • alloc: Total allocated space
  • flags: Type and other metadata
  • buf[]: Actual string buffer

2. Key Features:

• Binary Safety: Can contain any binary data including null bytes
• O(1) Length Operations: Length stored in header
• Space Optimization: Different header sizes based on string length
• Efficient Memory Management: Pre-allocates space to reduce reallocations

3. Header Types:

• TYPE_5: Very short strings (<32 bytes)
• TYPE_8: Short strings
• TYPE_16/32/64: Progressively larger strings

4. Memory Management:

• Pre-allocates extra space to reduce reallocations
• For small strings (<1MB), doubles allocation
• For large strings, adds 1MB extra space
• Provides explicit memory management functions

5. Common Operations:

• Creation: sdsnew(), sdsnewlen(), sdsempty()
• Modification: sdscat(), sdscpy(), sdstrim()
• Formatting: sdscatprintf(), sdscatfmt()

6. Benefits over C strings:

• Constant time length operations
• No buffer overflows
• Binary safe
• C string compatibility
• Reduced memory reallocations
• Multiple size classes for efficiency

The implementation is crucial for Redis’s performance as strings are a fundamental data type, providing both efficiency and safety while maintaining C string compatibility when needed.