What are the underlying data structures used for Redis

Redis, renowned for its blazing-fast performance, is a versatile in-memory data structure store used as a database, cache, and message broker. But what fuels this speed and flexibility? The answer lies in its clever use of underlying data structures. Understanding these structures is crucial for leveraging Redis effectively and optimizing its performance for your specific needs. This article delves into the core data structures that power Redis, exploring their functionalities and use cases.

Strings

The most basic data structure in Redis is the string. While seemingly simple, Redis strings are incredibly versatile. They can store not just text, but also binary data, integers, and even floating-point numbers. This flexibility makes them suitable for a wide range of applications, from caching HTML fragments to storing user session data.

Redis strings are binary safe and can hold up to 512MB of data. They also support atomic operations, enabling functionalities like incrementing or decrementing integer values directly within the string, a feature often used for counters and rate limiters. Furthermore, strings can be manipulated using a rich set of commands, including substring operations, bitwise operations, and even regular expression matching.

Lists

Redis lists are implemented as doubly linked lists. This structure allows for efficient insertion and deletion of elements at both the head and tail. This makes lists ideal for use cases such as queues, logs, and time series data. Imagine managing a queue of tasks for a background worker: Lists provide the perfect mechanism for adding new tasks to the end and retrieving the oldest task from the beginning.

Furthermore, Redis offers blocking list operations. This means a client can wait for an element to become available in a list, eliminating the need for constant polling and improving efficiency. This is particularly useful for implementing pub/sub messaging patterns.

Hashes

Hashes in Redis store collections of key-value pairs, much like dictionaries or objects in other programming languages. They are excellent for representing structured data, such as user profiles, product catalogs, or any data that can be modeled as a collection of attributes. Retrieving a specific field within a hash is extremely fast, making them ideal for situations where you need quick access to individual data points.

Consider storing user profile information. A hash allows you to store attributes like name, email, and address under a single user ID key. This facilitates efficient retrieval of individual attributes without the need to retrieve the entire profile data.

Sets

Redis sets are unordered collections of unique strings. Their unique characteristic is the ability to perform set operations like unions, intersections, and differences very efficiently. This makes them perfect for scenarios like tag management, social networking connections, and identifying common elements across different datasets.

For example, imagine tracking user tags for blog posts. Sets allow you to quickly determine which users share common tags, facilitating content recommendations or community building features.

Sorted Sets

Similar to sets, sorted sets also store unique strings. However, each member in a sorted set is associated with a score, which determines its order within the set. This makes sorted sets ideal for implementing leaderboards, ranking systems, and any application requiring sorted data.

Think of a gaming leaderboard where players are ranked based on their scores. Sorted sets provide an efficient way to maintain this ranking and retrieve the top players.

Bitmaps and HyperLogLogs

Beyond the five core data structures, Redis offers specialized structures like bitmaps and HyperLogLogs. Bitmaps are used for compact storage and manipulation of bitwise data, useful for tracking user activity or presence. HyperLogLogs are probabilistic data structures used for estimating the cardinality of sets, providing an efficient way to count unique elements with minimal memory usage.

Choose the right data structure for your specific needs to maximize performance.
Leverage Redis’ atomic operations for efficient counters and other similar use cases.

Analyze your data access patterns.
Select the appropriate Redis data structure.
Optimize your commands for efficiency.

As Salvatore Sanfilippo, the creator of Redis, states, “Redis is not just a key-value store, it’s a data structures server.” This quote emphasizes the importance of understanding the underlying data structures to truly unlock Redis’s power.

Choosing the right data structure is fundamental to optimizing Redis performance. Consider factors like data access patterns, the types of operations you’ll be performing, and memory usage requirements. By understanding the strengths and limitations of each data structure, you can leverage Redis effectively and build high-performing applications.

Learn More About Redis Data StructuresExternal Resources:

FAQ

Q: How do I choose the right Redis data structure?

A: Consider your data access patterns and the types of operations you need to perform. For example, if you need to maintain a sorted list, a sorted set is the ideal choice. If you need to store structured data, a hash is a better fit.

By understanding the nuances of each data structure, you can harness the full potential of Redis and build highly efficient and scalable applications. Explore the available resources and experiment with different data structures to find the best fit for your specific use case. Dive deeper into Redis commands and explore advanced functionalities to optimize your data management strategy. The efficiency and performance gains you achieve will be well worth the effort.

Question & Answer :
I’m trying to answer two questions in a definitive list:

What are the underlying data structures used for Redis?
And what are the main advantages/disadvantages/use cases for each type?

So, I’ve read the Redis lists are actually implemented with linked lists. But for other types, I’m not able to dig up any information. Also, if someone were to stumble upon this question and not have a high level summary of the pros and cons of modifying or accessing different data structures, they’d have a complete list of when to best use specific types to reference as well.

Specifically, I’m looking to outline all types: string, list, set, zset and hash.

Oh, I’ve looked at these article, among others, so far:

I’ll try to answer your question, but I’ll start with something that may look strange at first: if you are not interested in Redis internals you should not care about how data types are implemented internally. This is for a simple reason: for every Redis operation you’ll find the time complexity in the documentation and, if you have the set of operations and the time complexity, the only other thing you need is some clue about memory usage (and because we do many optimizations that may vary depending on data, the best way to get these latter figures are doing a few trivial real world tests).

But since you asked, here is the underlying implementation of every Redis data type.

Strings are implemented using a C dynamic string library so that we don’t pay (asymptotically speaking) for allocations in append operations. This way we have O(N) appends, for instance, instead of having quadratic behavior.
Lists are implemented with linked lists.
Sets and Hashes are implemented with hash tables.
Sorted sets are implemented with skip lists (a peculiar type of balanced trees).

But when lists, sets, and sorted sets are small in number of items and size of the largest values, a different, much more compact encoding is used. This encoding differs for different types, but has the feature that it is a compact blob of data that often forces an O(N) scan for every operation. Since we use this format only for small objects this is not an issue; scanning a small O(N) blob is cache oblivious so practically speaking it is very fast, and when there are too many elements the encoding is automatically switched to the native encoding (linked list, hash, and so forth).

But your question was not really just about internals, your point was What type to use to accomplish what?.

Strings

This is the base type of all the types. It’s one of the four types but is also the base type of the complex types, because a List is a list of strings, a Set is a set of strings, and so forth.

A Redis string is a good idea in all the obvious scenarios where you want to store an HTML page, but also when you want to avoid converting your already encoded data. So for instance, if you have JSON or MessagePack you may just store objects as strings. In Redis 2.6 you can even manipulate this kind of object server side using Lua scripts.

Another interesting usage of strings is bitmaps, and in general random access arrays of bytes, since Redis exports commands to access random ranges of bytes, or even single bits. For instance check this good blog post: Fast Easy real time metrics using Redis.

Lists

Lists are good when you are likely to touch only the extremes of the list: near tail, or near head. Lists are not very good to paginate stuff, because random access is slow, O(N). So good uses of lists are plain queues and stacks, or processing items in a loop using RPOPLPUSH with same source and destination to “rotate” a ring of items.

Lists are also good when we want just to create a capped collection of N items where usually we access just the top or bottom items, or when N is small.

Sets

Sets are an unordered data collection, so they are good every time you have a collection of items and it is very important to check for existence or size of the collection in a very fast way. Another cool thing about sets is support for peeking or popping random elements (SRANDMEMBER and SPOP commands).

Sets are also good to represent relations, e.g., “What are friends of user X?” and so forth. But other good data structures for this kind of stuff are sorted sets as we’ll see.

Sets support complex operations like intersections, unions, and so forth, so this is a good data structure for using Redis in a “computational” manner, when you have data and you want to perform transformations on that data to obtain some output.

Small sets are encoded in a very efficient way.

Hashes

Hashes are the perfect data structure to represent objects, composed of fields and values. Fields of hashes can also be atomically incremented using HINCRBY. When you have objects such as users, blog posts, or some other kind of item, hashes are likely the way to go if you don’t want to use your own encoding like JSON or similar.

However, keep in mind that small hashes are encoded very efficiently by Redis, and you can ask Redis to atomically GET, SET or increment individual fields in a very fast fashion.

Hashes can also be used to represent linked data structures, using references. For instance check the lamernews.com implementation of comments.

Sorted Sets

Sorted sets are the only other data structures, besides lists, to maintain ordered elements. You can do a number of cool stuff with sorted sets. For instance, you can have all kinds of Top Something lists in your web application. Top users by score, top posts by pageviews, top whatever, but a single Redis instance will support tons of insertion and get-top-elements operations per second.

Sorted sets, like regular sets, can be used to describe relations, but they also allow you to paginate the list of items and to remember the ordering. For instance, if I remember friends of user X with a sorted set I can easily remember them in order of accepted friendship.

Sorted sets are good for priority queues.

Sorted sets are like more powerful lists where inserting, removing, or getting ranges from the the middle of the list is always fast. But they use more memory, and are O(log(N)) data structures.

Conclusion

I hope that I provided some info in this post, but it is far better to download the source code of lamernews from http://github.com/antirez/lamernews and understand how it works. Many data structures from Redis are used inside Lamer News, and there are many clues about what to use to solve a given task.

Sorry for grammar typos, it’s midnight here and too tired to review the post ;)