Quick list of redis source code analysis

xindoo 2021-01-21 23:55:14
quick list redis source code


What is the quicklist, Last time I said ziplist The time complexity of each change is very high , Because you have to regenerate a new ziplist As an updated list, If one list Very large and updated frequently , That will give you redis It's a huge burden . How to keep ziplist Space efficiency of , And can not let its update complexity is too high ? redis The answer given by the author is quicklist.

In fact, to put it bluntly is to ziplist Combined with ordinary two-way linked list . Each double list node holds one ziplist, Then each ziplist A batch of list Data in ( Specifically ziplist The size is configurable ), In this way, the memory consumption caused by a large number of linked list pointers can be avoided , It can also be avoided ziplist A lot of performance loss due to updates , Will be big ziplist break up the whole into parts .

data structure

quicklist

A picture is worth a thousand words , Let's look at the next practical quicklist What it looks like in memory .

Here's an overview of the different nodes in the figure above , all redis in list All of them are quicklist, So it's like pop push And so on list Parameters are quicklist.quicklist The fields and their meanings are as follows .

typedef struct quicklist {
quicklistNode *head; /* Head node */
quicklistNode *tail; /* Caudal node */
unsigned long count; /* Of all the ziplist Medium entry total */
unsigned long len; /* quicklist Total number of nodes */
int fill : QL_FILL_BITS; /* 16 position , The maximum capacity of each node */
unsigned int compress : QL_COMP_BITS; /* 16 position ,quicklist The depth of compression ,0 Indicates that all nodes are not compressed , Otherwise, it means how many nodes are not compressed from both ends */
unsigned int bookmark_count: QL_BM_BITS; /*4 position ,bookmarks Size of array ,bookmarks Is an optional field , be used for quicklist Use when reallocating memory space , No space when not in use */
quicklistBookmark bookmarks[];
} quicklist;

It can be seen that quicklist In fact, it's a simple double linked list , But here are a few more fields , Let's focus on compress. In the picture above, I used two different colored nodes , Among them, green is common ziplist node , And red is compressed ziplist node (LZF node ),LZF It's a lossless compression algorithm .redis To save memory space , Will quicklist The node of LZF Compressed storage , But it's not all compressed here , You can configure the compress Value ,compress by 0 Indicates that all nodes are not compressed , Otherwise, it means how many nodes are not compressed from both ends , As I see in the picture above ,compress Namely 1, Start at both ends , Yes 1 Nodes don't do LZF Compress .compress The default is 0( Uncompressed ), It can be configured according to the actual use scenarios of your business .

Why not compress all nodes , It's the outflow compress This configurable opening ? It's just statistics ,list Data changes are most frequent at both ends , image lpush,rpush,lpop,rpop And other commands are operated at both ends , If you compress or decompress the code frequently, it will cause unnecessary performance loss . You can see it here redis It's not just about performance , It's also trying to reduce storage footprint 、 Between storage and performance trade-off.

Here's another one fill Field , It means every quicknode The node of The maximum capacity , Different values have different meanings , The default is -2, Of course, it can also be configured to other values , The specific numerical meaning is as follows :

  • -1: Every quicklistNode Node ziplist The number of bytes occupied cannot exceed 4kb.( Recommended configuration )
  • -2: Every quicklistNode Node ziplist The number of bytes occupied cannot exceed 8kb.( The default configuration & Recommended configuration )
  • -3: Every quicklistNode Node ziplist The number of bytes occupied cannot exceed 16kb.
  • -4: Every quicklistNode Node ziplist The number of bytes occupied cannot exceed 32kb.
  • -5: Every quicklistNode Node ziplist The number of bytes occupied cannot exceed 64kb.
  • Any positive number : Express :ziplist Structure contains at most entry Number , The maximum is 215215.

quicklistNode

quicklistNode It is the node encapsulation of double linked list , In addition to the pointers to the front and back nodes , It also contains some other information about this node . For example, whether it is LZF Compressed nodes 、ziplist Related information …… As follows :

typedef struct quicklistNode {
struct quicklistNode *prev;
struct quicklistNode *next;
unsigned char *zl; /* quicklist Node corresponding ziplist */
unsigned int sz; /* ziplist Bytes of */
unsigned int count : 16; /* ziplist Of item Count */
unsigned int encoding : 2; /* data type ,RAW==1 or LZF==2 */
unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */
unsigned int recompress : 1; /* Has this node been compressed before ? */
unsigned int attempted_compress : 1; /* node can't compress; too small */
unsigned int extra : 10; /* Unused 10 position */
} quicklistNode;

We have learned from the above that quicklist What it looks like in memory at some point , Next, let's see how it changes when data is inserted or deleted .

quicklist The operation of

establish

/* Create a new quicklist.
* Use quicklistRelease() Release quicklist. */
quicklist *quicklistCreate(void) {
struct quicklist *quicklist;
quicklist = zmalloc(sizeof(*quicklist));
quicklist->head = quicklist->tail = NULL;
quicklist->len = 0;
quicklist->count = 0;
quicklist->compress = 0;
quicklist->fill = -2;
quicklist->bookmark_count = 0;
return quicklist;
}

create There's nothing to say , But here's a reminder ,fill The default value is -2, That is to say, each quicklistNode Medium ziplist The longest is 8k byte , You can adjust the specific configuration according to your own business needs .

Head and tail

about list nothing more , Head or tail insertion is the most common operation , But in fact, the head and tail are relatively simple .

/* stay quicklist Insert a piece of data into the head of the
* If you insert in an existing node , return 0
* If it is inserted in a new header , return 1 */
int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
quicklistNode *orig_head = quicklist->head;
if (likely(
_quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
quicklist->head->zl =
ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD); // At the head node corresponding to ziplist Insert
quicklistNodeUpdateSz(quicklist->head);
} else { // Otherwise, create a new head node , And then insert the data
quicklistNode *node = quicklistCreateNode();
node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
quicklistNodeUpdateSz(node);
_quicklistInsertNodeBefore(quicklist, quicklist->head, node);
}
quicklist->count++;
quicklist->head->count++;
return (orig_head != quicklist->head);
}
/* stay quicklist Insert a piece of data at the end of
* If you insert in an existing node , return 0
* If it is inserted in a new header , return 1 */
int quicklistPushTail(quicklist *quicklist, void *value, size_t sz) {
quicklistNode *orig_tail = quicklist->tail;
if (likely(
_quicklistNodeAllowInsert(quicklist->tail, quicklist->fill, sz))) {
quicklist->tail->zl =
ziplistPush(quicklist->tail->zl, value, sz, ZIPLIST_TAIL);
quicklistNodeUpdateSz(quicklist->tail);
} else {
quicklistNode *node = quicklistCreateNode();
node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_TAIL);
quicklistNodeUpdateSz(node);
_quicklistInsertNodeAfter(quicklist, quicklist->tail, node);
}
quicklist->count++;
quicklist->tail->count++;
return (orig_tail != quicklist->tail);
}

Both the head plug and tail plug call _quicklistNodeAllowInsert First of all, whether it can be directly in the current head | The tail node can insert , If you can, insert it directly into the corresponding ziplist in , Otherwise, you need to create a new node to operate . Remember what we said above fill Fields ,_quicklistNodeAllowInsert It's based on fill To determine whether the maximum capacity has been exceeded .

Insert... At a specific location

It's easier to plug in the head and tail , but quicklist It's more cumbersome to insert in non head and tail , Because you need to consider the insertion position 、 Front node 、 The storage of the back node .

/* In an already existing entry Insert a new one in front or behind entry
* If after==1 It means to insert after , Otherwise it's inserted in front of it */
REDIS_STATIC void _quicklistInsert(quicklist *quicklist, quicklistEntry *entry,
void *value, const size_t sz, int after) {
int full = 0, at_tail = 0, at_head = 0, full_next = 0, full_prev = 0;
int fill = quicklist->fill;
quicklistNode *node = entry->node;
quicklistNode *new_node = NULL;
if (!node) {
/* If entry Not filled in node, Then recreate a node And insert into quicklist in */
D("No node given!");
new_node = quicklistCreateNode();
new_node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
__quicklistInsertNode(quicklist, NULL, new_node, after);
new_node->count++;
quicklist->count++;
return;
}
/* Check that the node to be inserted is full */
if (!_quicklistNodeAllowInsert(node, fill, sz)) {
D("Current node is full with count %d with requested fill %lu",
node->count, fill);
full = 1;
}
if (after && (entry->offset == node->count)) {
D("At Tail of current ziplist");
at_tail = 1;
if (!_quicklistNodeAllowInsert(node->next, fill, sz)) {
D("Next node is full too.");
full_next = 1;
}
}
if (!after && (entry->offset == 0)) {
D("At Head");
at_head = 1;
if (!_quicklistNodeAllowInsert(node->prev, fill, sz)) {
D("Prev node is full too.");
full_prev = 1;
}
}
/* Not sure where to insert the new element */
if (!full && after) { // If the current node is dissatisfied , Just insert
D("Not full, inserting after current position.");
quicklistDecompressNodeForUse(node);
unsigned char *next = ziplistNext(node->zl, entry->zi);
if (next == NULL) {
node->zl = ziplistPush(node->zl, value, sz, ZIPLIST_TAIL);
} else {
node->zl = ziplistInsert(node->zl, next, value, sz);
}
node->count++;
quicklistNodeUpdateSz(node);
quicklistRecompressOnly(quicklist, node);
} else if (!full && !after) {
D("Not full, inserting before current position.");
quicklistDecompressNodeForUse(node);
node->zl = ziplistInsert(node->zl, entry->zi, value, sz);
node->count++;
quicklistNodeUpdateSz(node);
quicklistRecompressOnly(quicklist, node);
} else if (full && at_tail && node->next && !full_next && after) {
/* If the current node is full , The position to insert is the tail of the current node , And the latter node has space , Then plug it into the head of the next node .*/
D("Full and tail, but next isn't full; inserting next node head");
new_node = node->next;
quicklistDecompressNodeForUse(new_node);
new_node->zl = ziplistPush(new_node->zl, value, sz, ZIPLIST_HEAD);
new_node->count++;
quicklistNodeUpdateSz(new_node);
quicklistRecompressOnly(quicklist, new_node);
} else if (full && at_head && node->prev && !full_prev && !after) {
/* If the current node is full , The position to insert is the head of the current node , And the previous node has space , Then insert it at the end of the previous node . */
D("Full and head, but prev isn't full, inserting prev node tail");
new_node = node->prev;
quicklistDecompressNodeForUse(new_node);
new_node->zl = ziplistPush(new_node->zl, value, sz, ZIPLIST_TAIL);
new_node->count++;
quicklistNodeUpdateSz(new_node);
quicklistRecompressOnly(quicklist, new_node);
} else if (full && ((at_tail && node->next && full_next && after) ||
(at_head && node->prev && full_prev && !after))) {
/* If the current node is full , The front and back nodes are also full , Then create a new node and plug it in */
D("\tprovisioning new node...");
new_node = quicklistCreateNode();
new_node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
new_node->count++;
quicklistNodeUpdateSz(new_node);
__quicklistInsertNode(quicklist, node, new_node, after);
} else if (full) {
/* otherwise , The current node is full , We need to split it into two new nodes , Generally used to insert into the current node ziplist Somewhere in the middle */
D("\tsplitting node...");
quicklistDecompressNodeForUse(node);
new_node = _quicklistSplitNode(node, entry->offset, after);
new_node->zl = ziplistPush(new_node->zl, value, sz,
after ? ZIPLIST_HEAD : ZIPLIST_TAIL);
new_node->count++;
quicklistNodeUpdateSz(new_node);
__quicklistInsertNode(quicklist, node, new_node, after);
_quicklistMergeNodes(quicklist, node);
}
quicklist->count++;
}

The code is long , Summarized below :

  • If the currently inserted node is not satisfied , Directly inserted into the .
  • If the currently inserted node is full , The position to insert is the tail of the current node , And the latter node has space , Then plug it into the head of the next node .
  • If the currently inserted node is full , The position to insert is the head of the current node , And the previous node has space , Then insert it at the end of the previous node .
  • If the currently inserted node is full , The front and back nodes are also full , The position to insert is the head or tail of the current node , Then create a new node and plug it in .
  • otherwise , The current node is full , And the position to be inserted is in the middle of the current node , We need to split the current node into two new nodes , Then insert .

Data deletion

Data deletion is the opposite of insertion , After reading the following code, you will find that it is not completely :

void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry) {
quicklistNode *prev = entry->node->prev;
quicklistNode *next = entry->node->next;
int deleted_node = quicklistDelIndex((quicklist *)entry->quicklist,
entry->node, &entry->zi);
/* after delete, the zi is now invalid for any future usage. */
iter->zi = NULL;
/* If current node is deleted, we must update iterator node and offset. */
if (deleted_node) {
if (iter->direction == AL_START_HEAD) {
iter->current = next;
iter->offset = 0;
} else if (iter->direction == AL_START_TAIL) {
iter->current = prev;
iter->offset = -1;
}
}
}
REDIS_STATIC int quicklistDelIndex(quicklist *quicklist, quicklistNode *node,
unsigned char **p) {
int gone = 0;
node->zl = ziplistDelete(node->zl, p);
node->count--;
if (node->count == 0) {
gone = 1;
__quicklistDelNode(quicklist, node);
} else {
quicklistNodeUpdateSz(node);
}
quicklist->count--;
/* If we deleted the node, the original node is no longer valid */
return gone ? 1 : 0;
}

Deleting is much easier than inserting , I'll look at the insertion logic first , There is node splitting in the insertion , But there is no node merging in the deletion ,quicklist Maximum capacity with nodes , But there is no minimum capacity limit .

other API

I understand quicklist Data structure design , You can basically guess every api The concrete realization of , I'm not going to list the code here , If you are interested, please refer to .

quicklist *quicklistCreate(void); // establish quicklist
quicklist *quicklistNew(int fill, int compress); // Create a new one with some specified parameters quicklist
void quicklistSetCompressDepth(quicklist *quicklist, int depth); // Set the compression depth
void quicklistSetFill(quicklist *quicklist, int fill); // Set capacity cap
void quicklistSetOptions(quicklist *quicklist, int fill, int depth);
void quicklistRelease(quicklist *quicklist); // Release quicklist
int quicklistPushHead(quicklist *quicklist, void *value, const size_t sz); // Head insertion
int quicklistPushTail(quicklist *quicklist, void *value, const size_t sz); // Tail insertion
void quicklistPush(quicklist *quicklist, void *value, const size_t sz,
int where); // Specify head or tail insertion
void quicklistAppendZiplist(quicklist *quicklist, unsigned char *zl); // Put one ziplist Put it in quicklist in
quicklist *quicklistAppendValuesFromZiplist(quicklist *quicklist,
unsigned char *zl); // hold ziplist Put all the data in quicklist in
quicklist *quicklistCreateFromZiplist(int fill, int compress,
unsigned char *zl); // from ziplist Generate a quicklist
void quicklistInsertAfter(quicklist *quicklist, quicklistEntry *node,
void *value, const size_t sz);
void quicklistInsertBefore(quicklist *quicklist, quicklistEntry *node,
void *value, const size_t sz);
void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry); // Data deletion
int quicklistReplaceAtIndex(quicklist *quicklist, long index, void *data,
int sz); // Data substitution
int quicklistDelRange(quicklist *quicklist, const long start, const long stop); // Scope delete
quicklistIter *quicklistGetIterator(const quicklist *quicklist, int direction); // iterator
quicklistIter *quicklistGetIteratorAtIdx(const quicklist *quicklist,
int direction, const long long idx); // Iterators starting at the specified position
int quicklistNext(quicklistIter *iter, quicklistEntry *node); // The next position of the iterator
void quicklistReleaseIterator(quicklistIter *iter); // Release iterators
quicklist *quicklistDup(quicklist *orig); // duplicate removal
int quicklistIndex(const quicklist *quicklist, const long long index,
quicklistEntry *entry); // find entry The subscript index of
void quicklistRewind(quicklist *quicklist, quicklistIter *li);
void quicklistRewindTail(quicklist *quicklist, quicklistIter *li);
void quicklistRotate(quicklist *quicklist); // choice quicklist
int quicklistPopCustom(quicklist *quicklist, int where, unsigned char **data,
unsigned int *sz, long long *sval,
void *(*saver)(unsigned char *data, unsigned int sz));
int quicklistPop(quicklist *quicklist, int where, unsigned char **data,
unsigned int *sz, long long *slong); // data pop
unsigned long quicklistCount(const quicklist *ql);
int quicklistCompare(unsigned char *p1, unsigned char *p2, int p2_len); // Compare the size
size_t quicklistGetLzf(const quicklistNode *node, void **data); // LZF node 

Reference material

This article is about Redis Source analysis series blog , At the same time, there are also corresponding Redis Chinese annotation version , I want to learn more about it Redis Classmate , welcome star And attention . Redis Chinese annotation version warehouse :https://github.com/xindoo/Redis Redis Source analysis column :https://zxs.io/s/1h If you found this article useful , welcome One key, three links .

Participation of this paper Tencent cloud media sharing plan , You are welcome to join us , share .

版权声明
本文为[xindoo]所创,转载请带上原文链接,感谢
https://javamana.com/2021/01/20210121234656675x.html

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云