Why Redis Doesn’t Use C Language Strings and Instead ‘Reinvented the Wheel’

Follow us, bookmark us, and join us every day at 7:30 for daily Java content sharing.

Technical Analysis

The ‘Four Sins’ of C Language Native Strings

The C language does not have a true “string” type. Its so-called string is simply a character array (<span>char*</span>) terminated by a null character<span>\0</span>. This simple design leads to four fatal issues when building high-performance, highly reliable databases:

1. 1. Poor efficiency in length retrieval (O(N) Complexity)

• • C Strings: To get the length of a C string, you must call the <span>strlen()</span> function. This function traverses the entire string from start to finish until it finds <span>\0</span>. The longer the string, the longer it takes. For a system like Redis that frequently operates on keys and values, this O(N) complexity operation is unacceptable.
• • SDS: The SDS structure has a <span>len</span> field that directly records the current length of the string. The length retrieval operation changes from traversal to direct reading, with a complexity of O(1), making it extremely fast.

2. Prone to Buffer Overflow

• • C Strings: Functions like <span>strcat()</span> do not check if the target array has enough space when concatenating strings. If there is insufficient space, a buffer overflow occurs, overwriting adjacent memory, leading to program crashes or serious security vulnerabilities.
• • SDS: The SDS API checks the <span>free</span> field (remaining space) before performing modification operations. If space is insufficient, it will automatically expand and then perform the modification, fundamentally eliminating the risk of buffer overflow.

3. Not Binary Safe

• • C Strings: Since <span>\0</span> is used as a special marker to end strings, the content of C strings cannot contain the <span>\0</span> character. Otherwise, the string will be “accidentally truncated”.
• • SDS: SDS determines the actual length of the string using the <span>len</span> field, rather than relying on <span>\0</span>. This means that the SDS buffer <span>buf</span> can store any binary data (including images, videos, serialized objects, etc.), even if it contains <span>\0</span> bytes, without error. SDS is binary safe.

4. Low Memory Allocation Efficiency

• • C Strings: Every time a string is increased or decreased, it may require reallocating memory (<span>realloc</span>). Frequent memory reallocations not only consume performance but also easily lead to memory fragmentation.
• • SDS: SDS optimizes memory allocation through two strategies:
• • Space Pre-allocation: When expanding SDS, it allocates more extra space than actually needed (<span>free</span> field). This way, the next small append operation does not require additional memory allocation and can directly use the reserved space.
• • Lazy Space Release: When shortening SDS, the program does not immediately reclaim the extra space but records this space in the <span>free</span> field for future growth operations.

Illustration of SDS Structure

// Simplified SDS structure
struct sdshdr {
    unsigned int len; // Used length
    unsigned int free; // Remaining available length
    char buf[];       // Flexible array that actually stores the string
};

Story Scenario: Measuring and Processing Ropes

You (Redis) are the chief craftsman of this workshop, and your daily work involves measuring, splicing, and cutting thousands of ropes (strings) of varying lengths.

Tool A: C Strings — An ‘Old Knotted Rope’

This is a very old, primitive measuring tool.

• • Its Appearance: A rope without markings. It only uses a red knot (<span>\0</span>) to mark the end of the rope.
• • Its ‘Four Major’ Defects:

1. 1. Measuring Length is Too Slow: The boss asks you, “How long is this rope?” You have no choice but to grab the end of the rope and measure inch by inch until you reach that red knot, to know the total length. The longer the rope, the longer it takes.
2. 2. Splicing Ropes is Dangerous (Buffer Overflow): You want to attach a 5-meter rope to the end of a 10-meter rope. You start attaching it without noticing that there is only 2 meters of space behind the pillar holding the 10-meter rope. As a result, the extra 3 meters of rope extends into the workshop aisle, tripping the boss (memory overflow, program crash).
3. 3. Cannot Handle ‘Special’ Ropes (Not Binary Safe): A customer brings a decorative rope for weaving Chinese knots, which has a decorative red knot in the middle. You use your old method to measure, and when you reach the middle knot, you mistakenly think the rope has ended and cut off and discarded the back half (data was accidentally truncated).
4. 4. Frequent Adjustments are Time-consuming: Every time you need to extend the rope a bit, you have to apply for a new, longer space in the warehouse and move the old rope over. It’s very cumbersome.

Tool B: SDS — A ‘Smart Retractable Tape Measure’

This is a modern, multifunctional tape measure with a built-in smart system.

• • Its Appearance: A tape measure box with a freely retractable tape. The box has a clear digital display.
• • Its ‘Four Major’ Advantages:

1. 1. Instant Length Reading: The boss asks you, “How long is this rope?” You just need to glance at the digital display on the box (<span>len</span> field) to immediately report the precise length.There is no need to pull out the tape completely.
2. 2. Absolutely Safe Splicing: When you want to extend a rope, the tape measure’s smart system will first check the internal remaining tape capacity (<span>free</span> field) to see if it’s enough. If not, it will automatically “click” to expand the internal space before allowing you to splice safely.It will never overflow.
3. 3. Perfectly Handles ‘Special’ Ropes: When faced with the decorative rope that has a red knot in the middle, the smart tape measure is unfazed. It only trusts the length number displayed on its screen (<span>len</span> field) and completely ignores what the rope looks like.
4. 4. Smart Space Management:
• • Reserved Space: When you only need to extend the rope by 2 meters, the smart tape measure may release 10 meters of extra capacity at once because it “guesses” you might need to extend it further soon.
• • Lazy Reclamation: When you cut the rope down by 5 meters, the tape measure does not immediately retract that 5 meters of tape. It simply updates the length number on the display, leaving that 5 meters as “available capacity” for you to use directly the next time you extend.

Story Summary:

Feature	C Strings (Old Knotted Rope)	SDS (Smart Tape Measure)
Length Retrieval	O(N) – Low Efficiency	O(1) – High Efficiency
Safety	❌ Buffer Overflow Risk	✅ Eliminates Buffer Overflow
Binary Safety	❌ Not Safe (Cannot contain <span>\0</span>)	✅ Safe (Can contain any byte)
Memory Management	Low Efficiency, Prone to Fragmentation	High Efficiency (Space Pre-allocation/Lazy Release)
Core Metaphor	A Clumsy Rope Marked by ‘Knots’	An Intelligent Tool with a ‘Digital Display’

Conclusion: Redis’s decision to abandon C language native strings and design its own SDS is a well-considered and extremely wise choice. By sacrificing a bit of extra memory space (for storing <span>len</span> and <span>free</span>), SDS achieves faster operation speeds, absolute safety, and more efficient memory usage, laying a solid foundation for Redis’s high performance and reliability.

Recommended Reading Click the title to jump

50 Java Code Examples: Master Lambda Expressions and Stream API

16 Java Code ‘Pain Points’ Major Overhaul: ‘General Writing’ VS ‘Advanced Writing’ Ultimate Showdown, Watch Code Quality Soar!

Why Senior Java Developers Love Using the Strategy Pattern

Selected Java Code Snippets: Better Writing for 10 Common Programming Scenarios

Enhancing Java Code Reliability: 5 Best Practices for Exception Handling

Why You Rarely See if-else in the Code of Experts, Because They All Use This…

Still Injecting Other Services Madly in Service? You Should Have Used Spring’s Event Mechanism Long Ago

Did you gain something from this article? Please share it with more people.

Follow ‘Java Content’ and bookmark it to enhance your Java skills



❤️ Give a 'Recommendation', it's the biggest support ❤️