Shulou(Shulou.com)06/01 Report--

Editor to share with you examples of the use of Redis basic data structures, I believe that most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's learn about it!

1. Data type

Its basic data types are String, List, Hash, Set, Sorted Set, these are commonly used basic data types, you can see very rich, almost able to meet most of the needs. In fact, there are some advanced data structures, which we will not mention for the time being in this chapter, but only talk about the basic data structures.

2. String

String can be said to be the most basic data structure, and can be directly linked to String in Java. You can use the String type to store a flag bit, a counter, or even a bit harder, the serialized JSON string is fine, and its single key is limited to 512m. The common commands are get, set, incr, decr, mget.

2.1 use

Get gets a key and returns a null pointer if the key does not exist.

Set assigns a value to key and sets key to the specified value. If the key already has a value, it will be overwritten by the new value.

Incr gives the current key a value of + 1. If key does not exist, the key call set is assigned a value of 0, and then incr is called. Of course, if the type of the key cannot be added, such as a string, an error will be thrown

The value of decr to the current key is-1, and the rest are the same as above

Mget is the same as get, but returns multiple pieces of data at a time. If key does not exist, it will return a null pointer.

String related commands

Maybe most people just use it, which is understandable, but if you are a developer who pursues technology, or if you want to get close to a big factory, you must have the spirit to get to the bottom of it. Only when you really know the underlying principle of something, can you provide you with more ideas to solve problems when you encounter problems. Next, let's talk about how the bottom layer of String is implemented in Redis.

2.2 principle

2.2.1 structure

We know that Redis is written in C language, but Redis does not use it directly, but implements a structure called SDS (Simple Dynamic String) to implement the string, which is as follows.

Struct sdshdr {/ / record the number of bytes used in buf int len; / / record the number of unused bytes in buf int free; / / byte array to hold the string char buf [];}

2.2.2 benefits

Why would Redis implement SDS on its own instead of using C strings directly? Mainly because of the following points.

Reduce the cost of getting string length in C language to get the length of a string, you need to traverse the entire string until the end flag bit\ 0 is encountered, and the time complexity is O (n), while SDS maintains the variable of length directly, and the time complexity of taking length is O (1).

Avoid buffer overflow in C language, if you cram a byte array with more than its capacity, it will cause a buffer overflow, and SDS solves this problem by maintaining the free variable. When writing data to the buf array, it first determines whether the remaining space is enough to cram in the new data, and if not, SDS reallocates the buffer to increase the previous buffer. And the increased length is equal to the length of the new data.

Space pre-allocation-Space lazy release in C language, memory space will be reallocated every time a string is modified. If the string is modified n times, then there will be n times of memory reallocation. Because SDS has redundant part of the space, it optimizes this problem, so it will inevitably redistribute n times to a maximum of n times, and when the data is removed from the buf, the free memory will not be immediately reclaimed, preventing new data from being written to cause memory reallocation.

To ensure binary security in C language, strings will be truncated when they encounter\ 0, while SDS will not truncate strings because\ 0 appears in the data. In other words, the actual operation result will not be affected by some special characters.

You can understand SDS in conjunction with the following figure.

The picture comes from the network, invading and deleting.

To sum up the four subheadings in the above list, in order to reduce the overhead of getting string length, avoid buffer overflow, pre-allocate space & space laziness release, and ensure binary security.

3. List

List is also a frequently used data structure, it involves too many commands, it is not like String to demonstrate one by one, interested people can search. Commands are lpush, lpushx, rpush, rpushx, lpop, rpop, lindex, linsert, lrange, llen, lrem, lset, ltrim, rpoplpush, brpoplpush, blpop, brpop, all of which operate on elements in an array.

3.1 use

I think the use of List mainly focuses on the following two aspects.

Store data as a normal list (similar to Java's ArrayList)

Used as an asynchronous queue

Of course, there is no need to say much about the general list, which stores the necessary data needed in the business, let's focus on asynchronous queues.

What, List can still play as a queue?

List can be used not only as a queue, but also as a stack. There are a lot of operating List commands described above. When we combine commands with rpush/lpop, we are actually using a queue, and when we combine commands with rpush/rpop commands, we are using a stack. Lpush/rpop and lpush/lpop are the same.

Suppose we use rpush to produce messages, and when our program needs to consume messages, we use lpop to consume messages from asynchronous queues. But in this way, when the queue is empty, you may need to keep asking if there is any data in the queue, which will result in a waste of CPU resources on the machine.

So you can take the current thread to Sleep for a period of time, which does save some CPU resources. But you may need to consider the Sleep time, the interval is too short, CPU context switching may also be a lot of overhead, the interval is too long, then the message may be delayed consumption (but all use asynchronous queues, should be able to ignore this problem).

Is there any other way besides Sleep?

Yes, the answer is blpop. When we use blpop to consume, if the current queue is empty, the thread will block until the following two kinds of condition.

Reached the set timeout time

There are messages in the queue that can be consumed

Real-time is better than Sleep for a period of time, and it is more friendly to CPU resources than polling.

3.2 principle

Before Redis3.2, Redis used ZipList (compressed list) or LinkedList (linked list). When the elements in List satisfy less than 64 bytes of each element and the number of List elements is less than 512, the storage mode is ZipList. Whenever a condition is not met, it will be converted to LinkedList.

After 3. 2, the implementation became QuickList (Quick list). Since LinkedList is a relatively basic thing, I won't go into it here.

3.2.1 ZipList

ZipList uses continuous memory compact storage, unlike linked lists, which do not require additional space to store pointers for front and subsequent nodes. According to its storage area division, can be divided into three parts, each part also has its own division, its detailed structure is as follows.

Header information of header ziplist

Zlbytes identifies the number of bytes of memory occupied by ziplist

Offset from zltail to ziplist tail node

Number of nodes stored in zllen ziplist

Entries stores the information of the actual node

Pre_entry_length records the length of the previous node, which allows you to quickly jump to the previous node.

Encoding, as its name implies, is the encoding format of storage elements.

The length of the data stored by length

Content saves the contents of the node

End identifies the end of the ziplist

If you use the linked list storage method, the elements in the linked list are connected by pointers, which may cause some memory fragmentation. Pointers also take up extra storage space. This is not the case with ZipList, where ZipList takes up a contiguous amount of memory space.

But accordingly, the modification operation of ZipList is relatively inefficient, insert and delete operations will be designed to frequent memory space request and release (similar to ArrayList re-expansion), and the query efficiency will also be affected. In essence, the ZipList query element is traversing the linked list.

3.2.2 QuickList

After version 3.2, the implementation of list has been replaced with QuickList. QuickList divides list into multiple nodes, each of which uses ZipList to store data.

4. Hash

Its usage is the same as in HashMap in Java, which is to throw key-value pairs into map.

4.1 use

The basic commands are as follows:

Hset sets key-value pairs in hash

Hget gets a key value in hash

Hdel removes a key from hash

Hlen counts the number of elements in hash

Hmget acquires the values of keys in hash in batches

Hmset sets keys and values in hash in batch

Hexists determines whether a key exists in hash.

Hkeys returns all keys in hash (excluding values)

Hvals returns all values in hash (excluding keys)

Hgetall gets all the key-value pairs, including keys and values

In fact, the use of HashMap is similar in most cases, and there is nothing special about it.

4.2 principle

There are also two underlying implementations of hash, ZipList and HashTable. But which one is used has nothing to do with the version of Redis, but with the elements stored in the current hash. First of all, when we create a hash, we use the ZipList for storage. As the number of elements in the hash increases and the threshold set by Redis is reached, it is converted to HashTable.

The threshold is set as follows:

A stored key or value is longer than the default value (64)

The number of elements stored in ZipList is greater than the default (512)

We have made a brief analysis of ZipList, and it should be easier to understand this setting. When there are too many elements in ZipList, the query efficiency becomes inefficient. The underlying design of HashTable is actually similar to that of HashMap in Java, which solves hash conflicts through zipper. For details, you can refer to this article from the basic use of digging HashMap.

5. Set

The concept of Set can be equated with Set in Java and is used to store a collection that does not contain repeating elements.

5.1 use

Its main commands are as follows: key represents Set,member in redis represents elements in the collection.

Sadd sadd key member [...] Add one or more elements to the collection and ignore any elements that already exist.

Srem srem key member [...] Remove one or more elements from the collection, and elements that do not exist will be ignored

Smembers smembers key returns all members of the collection

Sismember dismember key member determines whether member exists in key, returns 1 if it exists, and 0 if it does not exist

Scard scard key returns the number of elements in the collection key

Smove move source destination member moves elements from the source collection to the destination collection. If member is not included in the source, no action is performed and is removed from the collection if and only if it exists. If the destination element already exists, nothing will be done on the destination. This command is atomic.

Spop spop key randomly deletes and returns an element in the collection

Srandmember srandmember key is the same as spop, except that it does not delete the element, which can be understood as randomly extracting an element from the collection.

Sinter finds the intersection of one or more sets

Sinterstore sinterstore destination key [...] Similar to sinter, but the resulting results are saved in destination.

Sunion finds the union of one or more sets

Sunionstore sunionstore destination key [...]

Sdiff finds the difference of one or more sets

Sdiffstore sdiffstore destination key [...] Similar to sdiff, but the resulting results are saved in destination.

5.2 principle

We know that there are many implementations of Set in Java. Also in Redis, there are two implementations of IntSet and HashTable. First, IntSet is used for initialization, and when the following conditions are met, it is converted to HashTable.

When all elements saved in the collection are integers

The number of elements saved by the collection object does not exceed 512

HashTable has been briefly introduced above, so let's just talk about IntSet.

5.2.1 IntSet

The underlying layer of intset is an array, and since the data structure is an array, the stored data can be ordered, which makes the underlying query of intset through binary lookup. Its structure is as follows.

Struct intset {/ / Encoding uint32_t encoding; / / Collection contains the number of elements uint32_t length; / / Array int8_t contents of storage elements [];}

Like ZipList, IntSet also uses a series of memory space, but the difference is that ZipList can store binary content, while IntSet can only store integers; and ZipList storage is unordered, IntSet is ordered, so the query efficiency of IntSet will be more efficient if the number of elements is the same.

6. Sorted

The function of Set is similar to that of Set, except that on this basis, each element can be given a weight. You can understand it as the TreeSet of Java. Like List, Hash, and Set, there are two underlying implementations, ZipList and SkipList.

When initializing Sorted Set, ZipList will be used as its implementation, in fact, it is easy to understand that the number of elements at this time is very small, using ZipList for compact storage will save more space. It will be converted to SkipList when the following conditions are met in the current period:

The number of elements saved is less than 128.

The length of all elements saved is less than 64 bytes

6.1 use

In the following command, key represents the name of zset; 4 represents score, which is the weight; and member is the name of key in zset.

Zadd zadd key 4 member is used to add elements

Zcard zcard key is used to get the number of elements in the zset

Zrem zrem key member [...] Delete one or more key in zset

Zincrby zincrby key 1 member adds the weight value of key with the value of score (that is, 1)

Zscore zscore key member is used to obtain the weight value of the specified key

Zrange zrange key 0-1 gets all the elements in the zset, zrange key 0-1 withscores gets all the elements and weights, and the function of the withscores parameter is to decide whether to return the weight values as well. The returned elements are sorted from smallest to largest, and if the elements have the same weight, they are sorted in lexicographical order.

Zrevrange zrevrange key 0-1 withscores, which is similar to zrange, except that zrevrange is sorted from largest to smallest.

Zrangebyscore zrangebyscore key 1 5, which returns the element in key whose weight is in the range of interval (1, 5]. Of course, you can also use withscores to return weight values as well. Its elements are sorted from small to large. 1 stands for min,5 for max, and they can also be * *-inf and inf**, respectively. You can use this when you don't know the score interval in key. There is also an optional parameter similar to limit in SQL, which I will not repeat here.

In addition to being able to add weights to the elements, you can also implement delay queues using ZSet.

A delay queue is used to store deferred tasks, so what is a delay queue?

To take a very simple example, if you place an order in an e-commerce APP, but there is no payment, it will remind you that "if the order is not paid for more than 1 hour, it will automatically close"; for example, push a message to the user an hour before the end of an event; and for example, how many days after the completion of the order automatically confirm receipt, and so on.

Explain it in human words, that's what you have to do later.

So how does ZSet achieve this function?

In fact, it is very simple, that is, set the execution time of the task to the element weight in ZSet, and then regularly query the element with the least weight from ZSet through a background thread, and then judge by the current timestamp, if it is greater than the current timestamp (that is, it is time to execute), it will be taken out of the ZSet.

So, how do I get it?

In fact, I think many blogs that talk about Redis implementation delay queue do not explain how to take this clearly, what commands should be used and what parameters should be passed. We use the zrangebyscore command to do this, remember-inf and inf, whose full name is infinity, which stands for infinitesimal and infinity, respectively.

Since we don't know the scope of the score (that is, the task execution time) in the delay queue, we can use-inf and inf directly, as shown in the complete command.

Zrangescore key-inf inf limt 0 1 withscores

It's still a little useful, so how is the bottom layer of ZSet implemented?

I've already talked about ZipList, so I won't repeat it. Let's talk about SkipList.

6.2 principle

6.2.1 SkipList

SkipList exists in the structure of zset (Sorted Set), as follows:

Struct zset {/ / dictionary dict * dict; / / hopping table zskiplist * zsl;}

The structure of SkipList is as follows:

Struct zskiplist {/ / header node and footer node struct zskiplistNode * header, * tail; / / number of nodes in the table unsigned long length; / / number of layers of the node with the largest number of layers in the table int level;}

Have you ever wondered why Redis uses SkipList to implement ZSet instead of arrays?

First of all, ZSet if the array is stored, because the elements stored in ZSet are ordered, you need to put the elements in the corresponding position in the array when you store them. In this way, frequent additions and deletions will be made to the array, but frequent additions and deletions are not efficient in the array, because it involves the movement of array elements, and if the element is inserted in the first place, then all subsequent elements will be moved.

So in order to cope with frequent additions and deletions, we need to use linked lists. However, with the increase of linked list elements, the same problems will occur, although the efficiency of adding and deleting has been improved, but the efficiency of the query has become less efficient, because the query elements will traverse the linked list from beginning to end. So it would be nice if there was any way to improve the query efficiency of the linked list.

So the jump watch was born. Based on a single linked list, an index is established from the first node to every other node. It's actually a single linked list. Only the node is not omitted in the middle.

For example, there is a single linked table 13 4 5 7 8 9 10 13 16 17 18

The index after abstraction is 1 4 7 9 13 17

If you want to query 16, you only need to traverse to 13 at the index layer, and then according to the lower node stored by 13 (the address of the real linked list node), you only need to traverse two more nodes to find the node with a value of 16.

So we can redefine the jump table. The structure of the linked list plus multi-level index is the jump table.

In the jump table, the time complexity of querying any data is O (logn). The time complexity is the same as binary search. In other words, a binary search is implemented with a single linked list. But this is also a way of exchanging space for time, not free.

The above is all the content of the article "examples of the usage of Redis basic data structures". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.