Redis There are many underlying data structures , These include SDS、ZipList、SkipList、LinkedList、HashTable、Intset etc. . If you are right about Redis The understanding is still in get、set At the level of , Is not nearly enough to answer interview questions . This article briefly introduces Redis The underlying most important data structure - Simple dynamic string (SDS)

Redis Use C Language development , But it's not used C The traditional string representation of the language ( An array of bytes ending in a null character , hereinafter referred to as C character string ), Instead, I built something called a simple dynamic string (simple dynamic string,SDS) Abstract type of , And will SDS Used as a Redis The default string representation of .

stay Redis Inside ,C Strings will only be treated as literal strings (static literal) Used where string values do not need to be modified . When Redis You need more than just a literal string , It's a string value that can be modified ,Redis Will use SDS To represent a string value , For example Redis In the database of , The key-value pairs that contain strings are all created by SDS Realized .

Let's take an example , If the command is executed on the client side :

redis> SET msg "hello world"
ok

that Redis A new key-value pair will be created in the database , among :

  • The key of a key-value pair is a string object , The underlying implementation of the object is a holding string “msg” Of SDS.
  • The value of a key-value pair is also a string object , The underlying implementation of the object is a holding string “hello world” Of SDS.

In addition to storing string values in the database ,SDS It is also used as a buffer :AOF Module AOF buffer , And the input buffer in the client state , It's all by SDS Realized . All in all ,SDS yes Redis Is the most fundamental and important data structure .

1.SDS The definition of

Every sds.h/sdshdr The structure represents a SDS value :

struct sdshdr{
// Record buf The number of bytes used in an array
// be equal to SDS The length of the saved string
int len;
// Record buf The number of unused bytes in an array
int free;
// Byte array , To hold strings
char buf[];
}

Let me draw a picture :

SDS follow C The practice of ending a string with a blank character , Save the null character 1 Byte space does not count in SDS Of len Attributes inside , And allocate extra for the null character 1 Byte space , As well as adding a null character to the end of the string SDS The function does that automatically , So this blank character is going to be SDS Is completely transparent to the user .

2.SDS And C The difference between strings

For now, ,C The language USES length as N+1 To represent the length of N String , And the last element of the character array is always empty “\0”.

C This is a simple string representation of , Not enough Redis On strings in security 、 Efficiency and functional requirements . There are the following aspects .

2.1 Constant complexity gets the string length

because C A string does not record the length of a string , So in order to get one C Length of string , The program must traverse the entire string , Count each character encountered , Until a null character is encountered , The complexity of this operation is zero O(n). And in the Redis Of SDS in , The time complexity is zero O(1).

2.2 Prevent buffer overflow

In addition to the high complexity of getting the string length ,C Another problem with characters not recording their length is a buffer overflow . for instance ,C Linguistic strcat The concatenation () function concatenates the contents of a string to dest End of string , But when the string capacity is insufficient, the cache overflow occurs , Because strings are also implemented based on arrays , There is also a size limit .

Redis Of SDS The problem has been stamped out , So how does it work ?

When API Right SDS When making modifications ,API Will check SDS Is the space required to modify the space , If not enough ,API Will automatically SDS Space expansion , The actual modification is then performed . This avoids buffer memory overflow .

2.3 Reduces the number of memory reallocations that occur when strings are modified

It says API In the modified SDS Automatic expansion for strings , If each change is accompanied by a memory reallocation of the array within the string , That's pretty efficient . therefore Redis Two optimization strategies of space preallocation and lazy space release are realized .

Space preallocation

Space is pre-allocated for optimization SDS String growth operation : When SDS Of API To a SDS Make changes , And you need to SDS When you do spatial expansion , Not only will the program be SDS Allocate the space needed for modifications , Also for the SDS Allocate additional unused space .

in general , There are two possibilities for the amount of extra unused space allocated :

  1. If the SDS After the modification ,SDS The length of alpha is going to be less than alpha 1MB, So the program allocates the sum len Property of the same size of unused space , Now SDS Of free The value of the property will be sum len The value of the property is the same . in other words , The SDS After the string has been modified, it still has nearly half the capacity .
  2. If the SDS After the modification ,SDS The length of alpha is greater than or equal to alpha 1MB, So the program will allocate 1MB Of unused space . This is fixed .

Through space pre-allocation ,Redis You can reduce the number of memory reallocations required to perform string operations consecutively .

Inert space release

Lazy space release for optimization SDS String shortening operation : When SDS Of API Need to shorten the SDS Save the string , The program does not immediately use memory redistribution to reclaim the shortened bytes , But use free Property records the number of these bytes , And wait for future use .

2.4 Binary security

stay C In language , The storage of a string must conform to some encoding (ASCII), And the string cannot contain null characters , Otherwise it's considered the end of the string . So these restrictions make C Strings can only hold text data , You can't save images 、 Audio 、 video 、 Compress binary data such as files .

therefore , In order to solve C Shortage of strings ,Redis Of buf Arrays hold binary data , So this is just a SDS Of buf Why arrays are called byte arrays .

2.5 Compatible with the part C String function

although Redis Of API It's all binary safe , But they all follow C The convention of ending a string with an empty string , these API Always will be SDS The end of the saved data is set to a null character , And always will buf When an array allocates space, it allocates an extra byte to hold the empty character , This is for those who want to save text data SDS You can reuse part of it C Function of .

for instance , If we have one SDS The pointer to s , So we can use it directly stdio.h/printf function , By executing the following statement :

printf("%s", s->buf);

To print out SDS The saved string value "Redis" , Without having to SDS Write special printing functions .

Last , Near the Spring Festival , Happy new year to you all !

Redis Simple dynamic string of data structure SDS More articles about

  1. Redis Simple dynamic string of data structure SDS

    Several concepts 1:key object The database stores the keys of key value pairs , Always a string object .2:value object   The database stores the values of key value pairs , It can be a string object ,list object ,hash object ,set object ,sorted set object .    ...

  2. redis series 3 Simple dynamic string of data structure SDS

    One .  SDS summary Redis No direct use C The traditional string representation of the language , Instead, I built a simple dynamic string (simple dynamic string, SDS) Abstract type of , And will SDS Used as a Redis The silence of ...

  3. Redis Simple dynamic string of data structure

    Redis No direct use C The traditional string representation of the language ( An array of characters ending in empty characters ), Instead, I built a simple dynamic string (simple dynamic string,SDS) Abstract type of , And will SDS Used as a Redi ...

  4. Redis The core principle - Simple dynamic string SDS

    SDS brief introduction Redis yes C language-written , But not used c The string structure of a language , Instead, I implemented a set of simple dynamic strings simple dynamic string abbreviation SDS,SDS compatible C String type of language , Similar principle Ja ...

  5. The illustration Redis Data structure of —— Simple dynamic string SDS

    The illustration Redis Data structure of -- Simple dynamic string SDS Preface      I believe used Redis Everyone knows ,Redis It provides a logical object system and builds a key value pair database for client users . This object system includes string objects ...

  6. Redis The bottom ( One ): Simple dynamic string (SDS)

    redis It's a caching technology that we use a lot , His performance is very high , The speed of reading is zero 110000 Time /s, The speed of writing is 81000 Time /s. Behind such high performance , What kind of implementation is supporting , Articles in this series , Let's go and have a look . redi ...

  7. 【redis】redis The underlying data structure principle -- Simple dynamic string Linked list Dictionaries Skip list Set of integers Compressed list, etc

    redis There are five types of data string.list.hash.set.zset( character string . Hash . list . aggregate . Ordered set ) And self - Implementation of a simple dynamic string . Double ended linked list . Dictionaries . Compressed list . Set of integers . Jump table and other data structures .red ...

  8. Redis The source code parsing :01 Simple dynamic string SDS

    Redis No direct use C character string ( With '\0' Array of characters at the end ), Instead, we've built something called a simple dynamic string ( simple  dynamic  string, SDS) Abstract type of , And will SDS Used as a Redis Default characters for ...

  9. redis note 01 Simple dynamic string 、 Linked list 、 Dictionaries 、 Skip list 、 Set of integers 、 Compressed list

    The content of the article is extracted from <redis Design and implementation > Simple dynamic string 1. Redis Only use C String as literal , in the majority of cases ,Redis Use SDS(Simple Dynamic String, Simple dynamic ...

Random recommendation

  1. cdnbest After the node is installed, it can't connect to the master controller

    1. Check whether the node program starts ps -aux |grep kangle 2. If node programs are started , Check the log , Is the node connected to your account uid Account number or other error information tail -f /var/log ...

  2. CUDA Programming learning ( Four )

    utilize Block and Thread Do parallel acceleration _global_ void add(int *a, int *b, int *c) { int index = threadIdx.x + blockIdx. ...

  3. SOA Service development subtotal

    http://item.jd.com/11181846.html#comment SOA Service Oriented Architecture ——SOA The concept of http://www.cnblogs.com/leslies2/archive/2 ...

  4. c# Use spy Perform simulation operations

    Very helpless , For a long time , The page lost its response when it was last saved , It's killing . I wanted to give up , But I think it's a rough rewrite , I hope I can help my friends in the future . Microsoft.Spy Tool is a basic tool , Let's briefly introduce ...

  5. modify Activity The inheritance class of causes the program to flash back

    Refactoring old projects today , It's rewritten BaseActivity. One of the changes is to change the original parent class Activity Changed to AppCompatActivity. This change causes the program to flash back when it starts . see log Output ...

  6. __main() and main() 【 turn 】

    Because we are usually in BOOTLOADER We have done a lot of detailed initialization work in this project , Including code handling , So we'd better stop calling library functions __main(), because __main() As ADS Integrated library functions , Will initialize the system , can ...

  7. Makefile Common function table

    Makefile   Common function table One . String handling functions 1.$(subst FROM,TO,TEXT) The name of the function : String replacement function —subst. The functionality : Put the string “TEXT” Medium “FROM” Replace the character with “TO”. return ...

  8. HTTP agreement 【 Detailed explanation 】—— Classic interview questions

    http The request consists of three parts , Namely : Request line . The message header . Request body HTTP( Hypertext transfer protocol ) It's based on request and response patterns . Stateless . Application layer protocol , Chang Ji Yu TCP Mode of connection ,HTTP1.1 Version gives a persistent connection ...

  9. 【SQL】SqlServer in Group By after , String merge

    Reference resources : 1.SQL Query statement group by after , String merge 2.sql for xml path usage # demand : Merge column values Table structure , The data are as follows : id value ----- ------ aa bb ...

  10. javascript-- Interview questions

    (1)javaScript How to clear an array ? Such as var arrayList = ['a','b','c','d','e','f']; How to empty arrayList Method 1: Direct change arrayList To refer to ...