What are the underlying data structures used for Redis?
Master System Design with Codemia
Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.
Introduction
Redis is a highly performant, open-source, in-memory data structure store widely used for caching, real-time analytics, message brokering, and more. The secret behind its robustness and flexibility lies in its underlying data structures. This article explores the core data structures Redis employs and how they contribute to its efficiency.
Data Structures in Redis
Redis supports complex data types as its primary data structures:
- Strings
- Lists
- Sets
- Sorted Sets
- Hashes
- Bitmaps
- HyperLogLogs
- Streams
1. Strings
Strings in Redis are the simplest kind of values, but they're more than just character sequences. They can store any kind of data, such as text or serialized objects, up to 512 MB in size. Technically, Redis uses a dynamic string representation known as SDS (Simple Dynamic Strings).
Example:
2. Lists
Redis lists are collections of strings sorted by the order of insertion, analogous to linked lists. Internally, Redis uses a doubly linked list or a quicklist, combining arrays and linked lists depending on the length and settings.
Example:
3. Sets
Sets are unordered collections of unique strings. Redis sets use a hashtable when it's small or a specialized data structure—a dictionary—when the set grows larger.
Example:
4. Sorted Sets
Sorted sets are similar to sets but with an added score, allowing elements to be sorted. Internally, Redis implements sorted sets with a combination of a skip list and a hash table, ensuring high efficiency.
Example:
5. Hashes
Hashes in Redis are collections of key-value pairs. Redis is optimized to handle small hash objects, internally using a hashtable or a ziplist when the hash is small.
Example:
6. Bitmaps
Bitmaps are designed for bitwise operations. Redis treats strings as arrays of bits, offering manipulation on the binary level.
Example:
7. HyperLogLogs
HyperLogLogs are probabilistic data structures used to count unique items in a large dataset with low memory usage. They're more suited for use cases where approximate cardinality suffices.
Example:
8. Streams
Streams are log data structures that support complex operations like storing multiple fields within the same entry as a stream item. Streams provide a powerful abstraction for handling time series data, complex message brokering, and more.
Example:
Summary Table
| Data Structure | Description | Internal Structure |
| Strings | Binary safe strings up to 512 MB | Simple Dynamic String (SDS) |
| Lists | Ordered collection of strings | Doubly linked list or quicklist (mix of linked list and array) |
| Sets | Unordered collections of unique strings | Hashtable or dictionary (depending on size) |
| Sorted Sets | Sets sorted by a score | Combination of skip list and hash table |
| Hashes | Field-value pairs | Hashtable or ziplist (depending on size) |
| Bitmaps | Strings interpreted as bits | Bit-wise operations on strings |
| HyperLogLogs | Probabilistic structures for counting unique items | Sparse and dense representation to minimize memory usage |
| Streams | Append-only log of entries with multiple fields | Listpack for storing list of simple elements, while each entry is a tuple stored in a similar fashion, akin to a hash map |
Conclusion
Redis efficiently utilizes these data structures to deliver remarkable performance. Each data structure serves specific use cases, and their internal mechanics guarantee that Redis remains flexible yet optimized for speed. Understanding these structures is essential for leveraging Redis's full potential in application development.
