Categories
Uncategorized

redis principle Series – realization of the principle (1) stored as a string

background

redis powerful, it has become almost essential modern services and medium-sized cache technology. In addition to the cache function is to force, redis as message queues, databases, also has a good performance.

As we all know, redis there are five data types, string, list, hash, set and zset. The most basic, and most commonly used is the string. This article will talk about internal redis, realization of the principle of string: SDS (simple dynamic string).

redis simple dynamic character channeling: SDS

    In redis, the character C language channeling only used to put a string literal, that is, only when the disorder string string changes when it is in C, for example, when the print log.

    In addition to the basic character string storage, sds buffer is also used. AOF buffer module, and a client state input buffer, sds are achieved.

SDS definitions

struct sdshdr {
    
    // buf 中已占用空间的长度
    int len;

    // buf 中剩余可用空间的长度
    int free;

    // 数据空间
    char buf[];
};

Illustrated as follows:

  • Simple explanation: buf is an array of bytes, is used to put the specific data. Its length is a telescopic certain policy, specifically explained below. buf len indicates the length have been used out, free length of buf represents the unused portion.

  • buf within sds string, always consistent null-terminated string that same c. Thus sds c can be directly reused string function library part.

Comparison with SDS and advantages of the character string C

1, O (1) Get string length

    Since the length of the data already exists sds, it takes a string length complexity is O (1), and the acquired character string of length C O (n).

2, to eliminate memory problems caused by buffer overflow

    Suppose the memory areas s1: “hi”, s2: “redis” two strings, immediately adjacent, as shown below:

    In this case necessary to add a “boy” to s1, if the string is C, s1 give forget previously additionally allocated at this time will result in added value s2 is accidentally modified. The use sds not have this problem. Because of its packaged function that will check whether enough space before additional data, if not enough to expansion.

3, by pre-allocating space and reduce memory space allocation inert release

  • When sds additional value to a string, and the current remaining space is not enough, it will trigger the expansion mechanism sds. Expansion space optimization strategy using pre-assigned, i.e., when the allocation of space: If the value of the size sds <1M, then="" doubled;="" whereas="" if=""> 1M, 1M plus the current space as a new space.

  • When sds character channeling shortened, will be some of the extra space in the sds buf, this space will not be recovered immediately, but temporarily prevent the reuse of when to keep extra memory allocation. This release is inert space strategy

4, binary safe

    c string must meet certain coding (e.g. ASCII), and can not contain the null character. These limitations make c character channeling not save pictures, audio, and other binary files. Sds api are binary and the security of all of its api will be a way to deal with binary data in buf, so it will not have any restrictions.

SDS API interface list

function

effect

the complexity

C character to a new parameter for the channeling sds

New empty string sds

Release sds

Get used length

Get unused length

Create a copy of a sds

Clear

C is added to the string sds

String to append sds sds

C string values ​​covered sds

Empty string extended to a given length sds

Delete the data outside the given interval

Contrast is the same sds

Sds removed from the characters appear in a given string through the c

sdsnew O(N)
sdsempty O(1)
sdsfree O(N)
sdslen O(1)
sdsavail O(1)
sdsdup O(N)
sdsclear O(1)
sdscat O(N)
sdscatsds O(N)
sdscpy O(N)
sdsgrowzero O(N)
sdsrange O(N)
sdscmp O(N)
sdstrim O(N*M)

to sum up

sds package is actually a string array, but due to consider a variety of scenarios, the authors to adapt it more efficient, elegant interface, excellent design makes sds become a storage string. Sds that form the basis of an independent entity, providing efficient service to.

We design some of the underlying data structure biased, objects, even when a database table, you can refer sds design and find some inspiration.

Reference: “Redis Design and Implementation” Huang Jianhong

Harvest on the point of a praise it ~

Leave a Reply