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

Redis data structure and memory Management Strategy (part two)

Tag: Redis Redis data structure Redis memory management policy Redis data type Redis type mapping

Redis data type characteristics and usage scenarios String, List, Hash, Set, Zset case: Hujiang group buying system greatly promotes hot-top interface cache to design Redis memory data structure and coding OBJECT encoding key, DEBUG OBJECT key simple dynamic string (simple dynamic string) linked list (dict) jump table (skip list) integer set (zip list) Redis Object type and mapping Redis memory management policy key expiration time, Lifetime expired key deletion policy AOF, RDB processing expired key policy Redis LRU algorithm Redis persistence mode RDB (Redis DataBase) AOF (Append-only file) dictionary (dict)

Dict dictionary is based on hash algorithm and is the underlying storage data structure of Hash data type. Let's take a look at the dict.h header file definition for redis version 3.0.0.

Typedef struct dict {dictType * type; void * privdata; dictht ht [2]; long rehashidx; int iterators;} dict;typedef struct dictht {dictEntry * * table; unsigned long size; unsigned long sizemask; unsigned long used;} dictht;typedef struct dictEntry {void * key; union {void * val; uint64_t u64; int64_t s64; double d;} v; struct dictEntry * next;} dictEntry

When it comes to hash table, there are two things we often encounter. The first is the problem of hash collision. Redis dict is solved by chain address, and dictEntry- > next points to the node of the next conflict key.

Another problem that we often encounter is rehash. When it comes to rehash, we are still a little worried about performance. Then the implementation of redis is very clever, using lazy progressive rehash algorithm.

There is a number of ht [2] groups in dict struct and an rehashidx index. Redis's approximate algorithm for rehash is as follows: first, it will open up a new dictht space and put it on the ht [2] index. At this time, setting rehashidx to 0 indicates the beginning of the rehash phase, which may last for a long time, and rehashidx represents the number of dictEntry.

Every time there is access to the key in a ht [1] index, get, delete, update, redis will put all the key rehash in the current dictEntry index into the ht [2] dictionary. Once rehashidx=-1 indicates the end of rehash.

Jump table (skip list)

Skip list is the underlying data structure of zset, which has high-performance search and sorting ability.

We all know that the search with sorting is generally implemented with Tree, whether it is a variety of B Tree or B + Tree, is essentially used to do sequential lookup.

Skip list is easy to implement and its performance is similar to that of B Tree.

Typedef struct zskiplistNode {robj * obj; double score; struct zskiplistNode * backward; struct zskiplistLevel {struct zskiplistNode * forward; unsigned int span;} level [];} zskiplistNode;typedef struct zskiplist {struct zskiplistNode * header, * tail; unsigned long length; int level;} zskiplist

The value zskiplistNode- > zskiplistLevel- > span records the span of the current node from the next node. Each node will have a maximum of no more than the number of zskiplist- > level nodes, which is used to represent the distance between different spans and nodes.

Each node will have multiple forward forward pointers, with only one backward pointer. Each node has object * obj and score scores, each of which is arranged in order.

Set of integers (int set)

Int set integer set is the underlying implementation data structure of set data type. Its characteristics and usage scenarios are obvious, as long as the sets we use are integers and within a certain range, we will use integer set coding.

SADD set:userid 100200 300 (integer) 3OBJECT encoding set:userid "intset"

Int set uses a contiguous block of memory to store collection data, which is an array structure, not a linked list structure.

Typedef struct intset {uint32_t encoding; uint32_t length; int8_t contents [];} intset

Intset- > encoding is used to determine what type of integer encoding contents [] is, one of the following three values.

# define INTSET_ENC_INT16 (sizeof (int16_t)) # define INTSET_ENC_INT32 (sizeof (int32_t)) # define INTSET_ENC_INT64 (sizeof (int64_t))

Redis will dynamically sizeof a corresponding space size according to the value type we set. If our collection is originally int16 and then adds an int32 integer to the collection, the upgrade will be triggered, and the downgrade operation will not be triggered once the upgrade is successful.

Compression table (zip list)

Zip list compressed table is one of the underlying data structures of list, zset, and hash data types. It is designed to save memory by compressing data stored in a continuous piece of memory space.

Typedef struct zlentry {unsigned int prevrawlensize, prevrawlen; unsigned int lensize, len; unsigned int headersize; unsigned char encoding; unsigned char * p;} zlentry

Its biggest advantage is the compression of space, and the utilization rate of space is very high. The disadvantage is that once an update occurs, it may be a chain update, because the data is continuous in the content space, and in the most extreme cases, sequential chain expansion may occur.

The compressed list consists of multiple zlentry nodes, each zlentry recording the length and size of the last node, and the current node length lensize and size len including the encoded encoding.

Depending on the business scenario, redis provides a set of configurations specifically for threshold control for different scenarios.

Hash-max-ziplist-entries 512hash-max-ziplist-value 64list-max-ziplist-entries 512list-max-ziplist-value 64zset-max-ziplist-entries 128zset-max-ziplist-value 64

The above configuration is used to configure ziplist as the underlying compression threshold control for hash, list and zset data types, respectively.

Redis Object type and mapping

Each data type within redis is object-oriented, that is, the five data types we are talking about actually correspond internally to redisObject objects, and then redisObject wraps the specific storage data structure and coding.

Typedef struct redisObject {unsigned type:4; unsigned encoding:4; unsigned lru:REDIS_LRU_BITS; int refcount; void * ptr;} robj

This is a very OO design. RedisObject- > type is one of the five data types, and redisObject- > encoding is the data structure and encoding used for this data type.

Let's take a look at the storage data structure and encoding of each of the five data types provided by redis.

/ * Object types * / # define REDIS_STRING 0#define REDIS_LIST 1#define REDIS_SET 2#define REDIS_ZSET 3#define REDIS_HASH 4#define REDIS_ENCODING_RAW 0#define REDIS_ENCODING_INT 1#define REDIS_ENCODING_HT 2#define REDIS_ENCODING_ZIPMAP 3#define REDIS_ENCODING_LINKEDLIST 4#define REDIS_ENCODING_ZIPLIST 5 # define REDIS_ENCODING_INTSET 6 # define REDIS_ENCODING_SKIPLIST 7 # define REDIS_ENCODING_EMBSTR 8

The REDIS_ENCODING_ZIPMAP 3 code is negligible, has performance problems under certain circumstances, has been abandoned since redis 2.6, and is reserved for compatibility.

The figure above shows the correspondence between the five data types of redis and the underlying data structure and coding, but this correspondence may change in each version, which is also the flexibility of redisObject, with the polymorphism of OO.

RedisObject- > refcount indicates the reference count of the current object. In order to save memory, the shared object method is used inside redis. When an object is referenced, the refcount is added by 1 and subtracted by 1 when released.

RedisObject- > lru indicates the idle time of the current object, that is, idle time, which will be the time basis used by the redis lru algorithm to release the object. You can view the idling time and lru time of a key through the OBJECT idletime command.

Redis memory Management Policy

Redis maintains a dict for different db index on the server side. This dict is called key space key space. Each redis client can only belong to one db index, and the redisClient of each link is maintained on the redis server.

Typedef struct redisClient {uint64_t id; int fd; redisDb * db;} redisClient

Every redis client on the server side has a pointer to redisDb.

Typedef struct redisDb {dict * dict; dict * expires; dict * blocking_keys; dict * ready_keys; dict * watched_keys; struct evictionPoolEntry * eviction_pool; int id; long long avg_ttl;} redisDb

The key space key space is redisDb- > dict here. RedisDb- > expires is the expiration time of each key that maintains all key spaces.

Key expiration time, survival time

For a key, we can set how many seconds it will expire in milliseconds, or we can set it to expire at a specific point in time, which is a timestamp.

The EXPIRE command can set how many seconds a key will expire.

The PEXPIRE command can set how many milliseconds a key will expire after.

The EXPIREAT command can set the number of seconds after which a key expires

The PEXPIREAT command can set how many milliseconds after which a key expires.

The PERSIST command removes the expiration time of a key

In fact, the above commands will eventually be converted to PEXPIREAT commands. An expired millisecond timestamp is maintained in the key dictionary pointed to by redisDb- > expires.

TTL and PTTL can view the number of expired seconds and milliseconds of a key through these two commands.

There is an event loop inside redis that checks whether the expiration time of the key is less than the current time, and if so, deletes the key.

Expired key deletion policy

When using redis, we are most concerned about how the key is deleted and how to delete a key efficiently and on time. In fact, redis offers two options to accomplish this.

Redis adopts the double deletion strategy of lazy deletion and periodic deletion.

When we visit a key, the redis checks to see if it expires, which is a lazy delete.

Robj * lookupKeyRead (redisDb * db, robj * key) {robj * val; expireIfNeeded (db,key); val = lookupKey (db,key); if (val = = NULL) server.stat_keyspace_misses++; else server.stat_keyspace_hits++; return val;} int expireIfNeeded (redisDb * db, robj * key) {mstime_t when = getExpire (db,key); mstime_t now; if (when)

< 0) return 0; /* No expire for this key */ if (server.loading) return 0; now = server.lua_caller ? server.lua_time_start : mstime(); if (server.masterhost != NULL) return now >

When; / * Return when this key has not expired * / if (now id); return dbDelete (db,key);}

Redis also periodically performs the expired deletion of key through the event loop, which is deleted periodically.

Int serverCron (struct aeEventLoop * eventLoop, long long id, void * clientData) {/ * Handle background operations on Redis databases. * / databasesCron ();} void databasesCron (void) {/ * Expire keys by random sampling. Not required for slaves * as master will synthesize DELs for us. * / if (server.active_expire_enabled & & server.masterhost = = NULL) activeExpireCycle (ACTIVE_EXPIRE_CYCLE_SLOW);}

Lazy deletion is that lazy deletion code is triggered every time there is a read or write. Cycle deletion is triggered by redis EventLoop. Much of the maintenance work within redis is based on EventLoop.

AOF and RDB deal with expired key policy

Since keys can expire at any time, it's about how persistence redis handles it for us.

When redis is persisted using RDB, each time it is persisted, it will check whether the key that is about to be persisted has expired, if it expires, it will ignore it directly, and persist those keys that have not expired. When redis starts as the master master server, the rdb persistence keys are also checked to see if they are out of date when they are loaded. Expired keys are ignored and only those that are not expired are loaded.

When redis is persisted in AOF mode, each time an expired key redis is encountered, a DEL command will be appended to the AOF file, that is, as long as we load and execute the AOF command file sequentially, the expired keys will be deleted.

If redis is started as a slave server, it will clear all data for full synchronization once it establishes a link with the master master server, although the new version of redis supports SYCN2 semi-synchronization. If the master/slave master-slave synchronization has been established, the master server will send DEL commands to all slave servers to perform delete operations.

Redis LRU algorithm

When using redis, we will set the maxmemory option, and the 64-bit default is 0. The online server must be set up, otherwise it is likely to cause the redis host server to run out of memory directly and end up unable to get on the link.

So basically set up two configurations:

Maxmemory maximum memory threshold

Implementation Strategy of maxmemory-policy arrival threshold

You can view the two configuration values separately through CONFIG GET maxmemory/maxmemory-policy, or you can configure them separately through CONFIG SET.

Maxmemory-policy has a set of configurations that can be used in many scenarios:

Noeviction: the client tries to execute a command that causes more memory to be used and reports an error directly.

Allkeys-lru: execute the lru algorithm in all key

Volatile-lru: execute the lru algorithm in all expired key

Allkeys-random: randomly recycle in all key

Volatile-random: randomly recycle in expired key

Volatile-ttl: reclaims expired key and preferentially reclaims keys with short TTL

About the hit rate of cache, you can check the hit rate and miss rate of the key space through the info command.

# Statskeyspace_hits:33keyspace_misses:5

Maxmemory will use certain policies to free memory when it reaches the threshold. We can choose these policies according to our business scenarios. The default is noeviction.

Redis LRU algorithm has a sampling optimization mechanism, which can enhance the accuracy of recovered key through certain sampling factors. CONFIG GET maxmemory-samples to view the sampling configuration, you can refer to a more detailed article.

Redis persistence mode

Redis itself provides persistence function, there are two persistence mechanisms, one is data persistence RDB, the other is command persistence AOF, these two persistence methods have their own advantages and disadvantages, can also be combined, once the combined use of redis will give priority to loading data when loading aof files, only when AOF persistence is turned off will load rdb files.

RDB (Redis DataBase)

RDB is a redis database, and redis triggers persistence based on a configuration.

# save save 900 1save 300 10save 60 10000CONFIG GET save1) "save" 2) "3600 1 300 100 60 10000"

Indicates the number of changes, such as the number of seconds, and once this trigger condition is reached, redis will trigger the persistence action. Redis has two modes BGSAVE and SAVE when performing persistence. BGSAVE is saved in the background, and redis will fork a child process to handle persistence and will not execute requests from block users. SAVE, on the other hand, block the user to execute the request.

Struct redisServer {long long dirty;/* Changes to DB from the lastsave * / time_t lastsave; / * Unix time of last successful save * / long long dirty_before_bgsave;pid_t rdb_child_pid;/* PID of RDB saving child * / struct saveparam * saveparams; / * Save points array for RDB * /} struct saveparam {time_t seconds; int changes;}

RedisServer contains a lot of information, including information about RDB persistence. The number of change from redisServer- > dirty to the last save so far. RedisServer- > lastsave Last save time.

Saveparam struct holds the parameters we set through the save command, and _ _ time_t is a long__ timestamp.

Typedef _ _ darwin_time_t time_t; typedef long _ darwin_time_t; / * time () * / int serverCron (struct aeEventLoop * eventLoop, long long id, void * clientData) {for (j = 0; j)

< server.saveparamslen; j++) { struct saveparam *sp = server.saveparams+j; if (server.dirty >

= sp- > changes & & server.unixtime-server.lastsave > sp- > seconds & & (server.unixtime-server.lastbgsave_try > REDIS_BGSAVE_RETRY_DELAY | | server.lastbgsave_status = = REDIS_OK) {redisLog (REDIS_NOTICE, "% d changes in% d seconds. Saving... ", sp- > changes, (int) sp- > seconds); rdbSaveBackground (server.rdb_filename); break;}

The redis event loop periodically executes the serverCron method, and this code iterates through the server.saveparams parameter list.

If the server.dirty is greater than or equal to the configuration change in our parameters and the server.unixtime-server.lastsave is greater than the time configured in the parameters and _ _ server.unixtime-server.lastbgsave_try minus the bgsave retry delay time or the current server.lastbgsave_status==REDIS_OK, the rdbSaveBackground__ method is executed.

AOF (Append-only file)

AOF persistence is carried out by appending pairs to files, and each append is a command processed by redis. It is somewhat similar to the traceability pattern of command sourcing commands.

As long as we can replay all the commands in the order in which they are executed, we can restore the final redis memory state.

The biggest advantage of AOF persistence is that it can shorten the interval of data loss and achieve a loss rate of seconds. RDB will lose all data from the last save cycle to the present, and will not be persisted as long as the save seconds changes threshold data set by the save command is not triggered.

Struct redisServer {/ * AOF buffer, written before entering the event loop * / sds aof_buf;} struct sdshdr {unsigned int len; unsigned int free; char buf [];

Aof_buf is the command cache, which is cached with sds structure. Every time a command is executed, it will be written to aof_buf. There are several mechanisms configured to control AOF persistence.

Appendonly no appendfilename "appendonly.aof"

Appendonly is used to control whether AOF persistence is enabled, and appendfilename is used to set the aof file name.

Appendfsync alwaysappendfsync everysecappendfsync no

Appendfsync is used to control the command flushing mechanism. Now the operating system has the concept of file cache/buffer, all writes and reads will go cache/buffer, and will not be flushed synchronously every time, because the performance will certainly be affected. So redis also provides this option for us to control according to the business scenario.

Always: write the aof_buf command to the aof file every time and perform a real-time flush.

Everysec: writes the aof_buf command to the aof file every time, but flushes the disk every other second.

No: each time the _ _ aof_buf command is written to the aof__ file, the flushing disk is not performed and is controlled by the operating system from the line.

AOF is also carried out as a backstage child process, sharing data space with the main process, that is, aof_buf, but as long as you start the AOF_ child process, the redis event loop file event handler _ will write the subsequent commands to another _ _ aof_buf, so you can switch smoothly.

AOF will constantly add commands to the aof file, and the aof file will expand rapidly with the increase of time and concurrency, so it is necessary to optimize the file size. Redis compresses files based on rewrite rewriting.

No-appendfsync-on-rewrite no/yesauto-aof-rewrite-percentage 100auto-aof-rewrite-min-size 64mb

No-appendfsync-on-rewrite controls whether command appends are needed during bgrewriteaof. If the command is appended, disk IO may run high.

As mentioned above, when the AOF process is executing, the original event loop will normally append commands into the aof file, as well as additional commands into another aof_buf to rewrite the new aof file. These are two parallel actions, and if we set it to yes, we will not append the original aof_buf because the new aof file already contains the commands that come in later.

Auto-aof-rewrite-percentage and auto-aof-rewrite-min-size 64mb, the former is the percentage of file growth for rewrite, and the latter is for rewrite according to file size growth.

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.