Data Structures Used in Redis
From the translator:
I want to bring to your attention a translation of the answer of one of the Redis developers, to the question of what data structures are used inside Redis. The original discussion can be found on stackoverflow .
I will try to answer the question, but to begin with, it may seem strange at first glance: if you are not interested in Redis internals, you do not have to worry about how data structures are implemented from the inside. The reason for this is simple - the complexity of each Redis command can be found in the documentation, and if you have a set of operations and their computational complexity, then the only thing you need is some idea of ​​memory usage (and because we do a lot of optimizations, depending on the data, the best way to get these last numbers is tests in real conditions)
But as you asked, here are the internal implementations of each Redis data structure:
')
But when lists, sets, and ordered sets are small, in terms of the number of elements and the size of the largest values, a different, more compact representation is used. This representation is different for different structures, but it has the following feature: it is a compact BLOB, often having O (N) complexity for each operation. Since we only use this format for small objects, this is not a problem; Passing through a small O (N) BLOB's cache-independent (cache-oblivious algorithm, comment of the translator) , practically speaking, it is very fast, and as soon as there are a lot of elements, the view automatically switches to the native (linked list, hash, and etc.).
But your question is, in fact, not only about the internals, you wanted to ask: “ What structure to use for this or that? ".
Strings are the basic structure. This is one of the four basic structures, as well as the basis of all complex structures, because the List is a list of strings, the Set is a plurality of lines, and so on.
Strings are good in all obvious usage scenarios, when you want to store an HTML page, but they are also good if you want to avoid converting already encoded data. For example, if you have JSON or MessagePack, you can simply store objects as strings. In Redis 2.6, you can even manage this kind of server-side structures using Lua scripts.
Another interesting use of strings is bitmaps, and in general, random access to byte arrays, since Redis provides commands for accessing arbitrary byte ranges, or even individual bits. As an example, take a look at this nice post: Fast Easy real time metrics using Redis .
Lists are good when you mainly work with extreme elements: near the tail, or near the head. Lists are not the best choice for dividing something into pages, due to slow random access, O (N). Good use of lists will be simple queues and stacks, or looping through items with the RPOPLPUSH command, whose parameters will be the same list.
Lists are just as good when we need a limited collection of N elements, access to which is usually carried out only to the upper or lower elements, or when N is small.
A set is not an ordered set of data, it is effective when you have a collection of items, and it is important to very quickly check the presence of an item in the collection, or get its size. Another “trick” of the sets is the ability to get a random element (the SRANDMEMBER and SPOP commands).
Sets represent a relationship well, for example, “What are the friends of user X?” And the like. But, as we will see later, there are other suitable structures for such things, ordered sets.
The sets support complex operations such as intersection, union, and so on; this is a good way to use Redis in a “computational” manner, when you have data, and you want to get some results by performing transformations on this data.
Small sets are encoded in a very efficient way.
Hashes have a great structure for representing objects made up of fields and values. Hash fields can be atomically incremented by the HINCRBY command. If you have objects, such as users, blog posts, or other types of elements , hashes are what you need if you do not want to use your own format, such as JSON or any other.
However, keep in mind that small hashes in Redis are encoded very efficiently, and you can use atomic GET, SET operations or atomically increment a particular field at high speed.
Hashes can also be used to represent related data structures using links. For an example, take a look at the implementation of comments in lamernews.com
An ordered Set is the only data structure other than a list that supports working with ordered items . With ordered sets you can do a lot of cool things. For example, you can implement all kinds of Top Anything in your web application. Top users by rating, top posts by number of views, top anything, and one copy of Redis will serve tons of inserts and queries per second.
Ordered sets, like ordinary sets, can be used to describe relationships, but they also allow you to divide elements into pages, and maintain order. For example, if I keep friends of user X as an ordered set, I can easily store them in the order of adding to friends.
Ordered sets are good for priority queues.
Ordered sets are something like more powerful lists, in which inserting, deleting or getting items from the middle of the list is just as fast. But they use more memory, and are O (log (N)) structures.
I hope I have provided some information in this post, but it will be much better to download the source code of lamernews and understand how it works. Most Redis data structures are used in Lamer News, and their use can serve as a clue what to use to solve this problem.
I want to bring to your attention a translation of the answer of one of the Redis developers, to the question of what data structures are used inside Redis. The original discussion can be found on stackoverflow .
I will try to answer the question, but to begin with, it may seem strange at first glance: if you are not interested in Redis internals, you do not have to worry about how data structures are implemented from the inside. The reason for this is simple - the complexity of each Redis command can be found in the documentation, and if you have a set of operations and their computational complexity, then the only thing you need is some idea of ​​memory usage (and because we do a lot of optimizations, depending on the data, the best way to get these last numbers is tests in real conditions)
But as you asked, here are the internal implementations of each Redis data structure:
')
- Strings are implemented using the C dynamic strings library, so we do not pay (speaking asymptotically) for memory allocation in add operations. Thus, we get the complexity of adding O (N), instead of, for example, quadratic.
- Lists are implemented as linked lists.
- Sets and hashes are implemented as hash tables.
- Ordered sets are implemented as pass lists (special type of balanced trees)
But when lists, sets, and ordered sets are small, in terms of the number of elements and the size of the largest values, a different, more compact representation is used. This representation is different for different structures, but it has the following feature: it is a compact BLOB, often having O (N) complexity for each operation. Since we only use this format for small objects, this is not a problem; Passing through a small O (N) BLOB's cache-independent (cache-oblivious algorithm, comment of the translator) , practically speaking, it is very fast, and as soon as there are a lot of elements, the view automatically switches to the native (linked list, hash, and etc.).
But your question is, in fact, not only about the internals, you wanted to ask: “ What structure to use for this or that? ".
Strings
Strings are the basic structure. This is one of the four basic structures, as well as the basis of all complex structures, because the List is a list of strings, the Set is a plurality of lines, and so on.
Strings are good in all obvious usage scenarios, when you want to store an HTML page, but they are also good if you want to avoid converting already encoded data. For example, if you have JSON or MessagePack, you can simply store objects as strings. In Redis 2.6, you can even manage this kind of server-side structures using Lua scripts.
Another interesting use of strings is bitmaps, and in general, random access to byte arrays, since Redis provides commands for accessing arbitrary byte ranges, or even individual bits. As an example, take a look at this nice post: Fast Easy real time metrics using Redis .
Lists
Lists are good when you mainly work with extreme elements: near the tail, or near the head. Lists are not the best choice for dividing something into pages, due to slow random access, O (N). Good use of lists will be simple queues and stacks, or looping through items with the RPOPLPUSH command, whose parameters will be the same list.
Lists are just as good when we need a limited collection of N elements, access to which is usually carried out only to the upper or lower elements, or when N is small.
Sets
A set is not an ordered set of data, it is effective when you have a collection of items, and it is important to very quickly check the presence of an item in the collection, or get its size. Another “trick” of the sets is the ability to get a random element (the SRANDMEMBER and SPOP commands).
Sets represent a relationship well, for example, “What are the friends of user X?” And the like. But, as we will see later, there are other suitable structures for such things, ordered sets.
The sets support complex operations such as intersection, union, and so on; this is a good way to use Redis in a “computational” manner, when you have data, and you want to get some results by performing transformations on this data.
Small sets are encoded in a very efficient way.
Hashes
Hashes have a great structure for representing objects made up of fields and values. Hash fields can be atomically incremented by the HINCRBY command. If you have objects, such as users, blog posts, or other types of elements , hashes are what you need if you do not want to use your own format, such as JSON or any other.
However, keep in mind that small hashes in Redis are encoded very efficiently, and you can use atomic GET, SET operations or atomically increment a particular field at high speed.
Hashes can also be used to represent related data structures using links. For an example, take a look at the implementation of comments in lamernews.com
Ordered Sets
An ordered Set is the only data structure other than a list that supports working with ordered items . With ordered sets you can do a lot of cool things. For example, you can implement all kinds of Top Anything in your web application. Top users by rating, top posts by number of views, top anything, and one copy of Redis will serve tons of inserts and queries per second.
Ordered sets, like ordinary sets, can be used to describe relationships, but they also allow you to divide elements into pages, and maintain order. For example, if I keep friends of user X as an ordered set, I can easily store them in the order of adding to friends.
Ordered sets are good for priority queues.
Ordered sets are something like more powerful lists, in which inserting, deleting or getting items from the middle of the list is just as fast. But they use more memory, and are O (log (N)) structures.
Conclusion
I hope I have provided some information in this post, but it will be much better to download the source code of lamernews and understand how it works. Most Redis data structures are used in Lamer News, and their use can serve as a clue what to use to solve this problem.
Source: https://habr.com/ru/post/144054/
All Articles