Redis-Studiennotizen-Listen-Prinzip

Diagramm von: https://www.cnblogs.com/amyzhu/p/13466311.html

Einfach verknüpfte Liste

Bevor wir die Listenimplementierung von Redis lernen, werfen wir einen Blick darauf Zunächst einmal So implementieren Sie eine einfach verknüpfte Liste:

Jeder Knoten hat einen Rückwärtszeiger (Referenz), der auf den nächsten Knoten zeigt, der letzte Knoten zeigt auf NULL, um das Ende anzuzeigen, und es gibt einen Kopfzeiger, der auf den zeigt erster Knoten, der den Start anzeigt.

Ähnlich wie hier, aber neu und gelöscht benötigen nur O(1)O(1)，但是查找需要 O(n), aber die Suche erfordert O(n)

Zeit; Rückwärtssuche ist nicht möglich und Sie müssen beginnen von Anfang an, falls Sie es verpassen.

Einen Knoten löschen:

Eine doppelt verknüpfte Liste wird auch als doppelt verknüpfte Liste bezeichnet. Es handelt sich um eine Art verknüpfte Liste hat zwei Zeiger, die auf den unmittelbaren Nachfolger bzw. den unmittelbaren Vorgänger zeigen. Daher können Sie ausgehend von jedem Knoten in der doppelt verknüpften Liste problemlos auf dessen Vorgänger- und Nachfolgerknoten zugreifen.

Jedes Mal, wenn ein Knoten eingefügt oder gelöscht wird, müssen vier statt zwei Knotenreferenzen verarbeitet werden. Dies ist schwieriger zu implementieren Eine einseitig verknüpfte Liste wird definitiv mehr Speicherplatz beanspruchen.

1. Es kann vom Anfang bis zum Ende und vom Schwanz bis zum Kopf durchlaufen werden

2. Dies scheint das Problem von Redis zu lösen, das sowohl vorher als auch nachher implementiert werden kann Es ist ein Durchquerungsproblem.

3. Dann schauen wir uns die verlinkte Liste von

   redis an

Wie man damit umgeht:

Werfen wir einen Blick auf den Quellcode der Strukturdefinition? Bidirektional azyklisch: verknüpfter Listenknoten Mit Frontantrieb Die zeitliche Komplexität des Erhaltens der Vorgänger- und Nachfolgerknoten eines Knotens durch den Nachfolgerzeiger beträgt O(1). Der Vorgängerzeiger des Kopfknotens und der Nachfolgerzeiger des Schwanzknotens zeigen beide auf NULL und greifen auf zu Die verknüpfte Liste endet mit NULL.

Längenzähler: Die Zeitkomplexität zum Abrufen der Anzahl der Knoten über das len-Attribut der Listenstruktur beträgt O(1).

• Redis-komprimierte Liste

• Im Gegensatz zu Arrays können die gespeicherten Listenelemente unterschiedliche Speicherplätze belegen. Wenn es um die Wortkomprimierung geht, denkt jeder als Erstes an die Einsparung von Speicherplatz. Der Grund, warum diese Speicherstruktur Speicher spart, liegt im Vergleich zu Arrays.

  Wir alle wissen, dass Arrays für jedes Element die gleiche Größe an Speicherplatz benötigen. Wenn wir Zeichenfolgen unterschiedlicher Länge speichern möchten, müssen wir den Speicherplatz verwenden, der von der Zeichenfolge mit der maximalen Länge als jedes Element des Zeichenfolgenarrays belegt wird. Die Größe des Speicherplatzes (wenn er 50 Byte beträgt).

  Wenn also eine Zeichenfolge mit einer Länge von weniger als 50 Bytes im Zeichennummernwert gespeichert wird, wird ein Teil des Speicherplatzes verschwendet. Der Vorteil von

  array besteht darin, dass es einen kontinuierlichen Speicherplatz einnimmt und den CPU-Cache gut nutzen kann, um schnell auf Daten zuzugreifen.

  Wenn wir diesen Vorteil des Arrays beibehalten und Speicherplatz sparen möchten, können wir das Array komprimieren:

  

  Es gibt jedoch ein Problem, das wir beim Durchlaufen des komprimierten Arrays nicht kennen list Wie groß ist die von jedem Element belegte Speichergröße, sodass es unmöglich ist, die spezifische Startposition des nächsten Elements zu berechnen?
  

  Aber dann habe ich darüber nachgedacht: Wenn wir die Länge jedes Elements kennen könnten, bevor wir darauf zugreifen, wäre dieses Problem dann nicht gelöst?

  

  Schauen wir uns als Nächstes an, wie Redis ZipList implementiert, um es zu kombinieren und gleichzeitig die Vorteile von Arrays beizubehalten und Speicher zu sparen.
  

  

  • zlbytes：压缩列表的字节长度，是uint32_t类型，占4字节，因此压缩列表最多有232-1字节，可以通过该值计算zlend的位置，也可以在内存重新分配的时候使用。

  • zltail：压缩列表尾元素相对于压缩列表起始地址的偏移量，是uint32_t类型，占4字节，可以通过该值快速定位到列表尾元素的位置。

  • zllen：压缩列表元素的个数，是uint16_t类型，占2字节，表示最多存储的元素个数为216-1=65 535，如果需要计算总数量，则需要遍历整个压缩列表。

  • entryx：压缩列表存储的元素，既可以是字节数组，也可以是整数，长度不限。

  • zlend：压缩列表的结尾，是uint8_t类型，占1字节，恒为0xFF。

  • previous_entry_length：表示前一个元素的字节长度，占1字节或者5字节，当前元素的长度小于254时用1字节，大于等于254时用5字节，previous_entry_length 字段的第一个字节固定是0xFE，后面的4字节才是真正的前一个元素的长度。

  • encoding：表示元素当前的编码，有整数或者字节数。为了节省内存，encoding字段长度可变。

  • content：表示当前元素的内容。

  ZipList变量的读取和赋值都是通过宏来实现的，代码片段如下：

  //返回整个压缩列表的总字节
  #define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))
  
  //返回压缩列表的tail_offset变量，方便获取最后一个节点的位置
  #define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
  
  //返回压缩列表的节点数量
  #define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
  
  //返回压缩列表的表头的字节数
  //（内存字节数zlbytes，最后一个节点地址ztail_offset,节点总数量zllength）
  #define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))
  
  //返回压缩列表最后结尾的字节数
  #define ZIPLIST_END_SIZE        (sizeof(uint8_t))
  
  //返回压缩列表首节点地址
  #define ZIPLIST_ENTRY_HEAD(zl)  ((zl)+ZIPLIST_HEADER_SIZE)
  
  //返回压缩列表尾节点地址
  #define ZIPLIST_ENTRY_TAIL(zl)  ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))
  
  //返回压缩列表最后结尾的地址
  #define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)

  Nach dem Login kopieren

  
  

  对此，可以通过定义的结构体和对应的操作定义知道大概 redis 设计 压缩list 的思路；

  这种方式虽然节约了空间，但是会存在每次插入和创建存在内存重新分配的问题。

  quicklist

  quicklist是Redis 3.2中新引入的数据结构，能够在时间效率和空间效率间实现较好的折中。Redis中对quciklist的注释为A doubly linked list of ziplists。顾名思义，quicklist是一个双向链表，链表中的每个节点是一个ziplist结构。quicklist可以看成是用双向链表将若干小型的ziplist连接到一起组成的一种数据结构。

  当ziplist节点个数过多，quicklist退化为双向链表，一个极端的情况就是每个ziplist节点只包含一个entry，即只有一个元素。当ziplist元素个数过少时，quicklist可退化为ziplist，一种极端的情况就是quicklist中只有一个ziplist节点。

  

  

  
  

  quicklist 结构定义:

  typedef struct quicklist {
      // 指向quicklist的首节点
      quicklistNode *head;
      // 指向quicklist的尾节点
      quicklistNode *tail;
      // quicklist中元素总数
      unsigned long count;        /* total count of all entries in all ziplists */
      // quicklistNode节点个数
      unsigned long len;          /* number of quicklistNodes */
      // ziplist大小设置，存放list-max-ziplist-size参数的值
      int fill : 16;              /* fill factor for individual nodes */
      // 节点压缩深度设置，存放list-compress-depth参数的值
      unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
      unsigned int bookmark_count: 4;
      quicklistBookmark bookmarks[];
  } quicklist;
  
  typedef struct quicklistBookmark {
      quicklistNode *node;
      char *name;
  } quicklistBookmark;

  Nach dem Login kopieren

  quicklistNode定义如下:

  typedef struct quicklistNode {
      struct quicklistNode *prev;
      struct quicklistNode *next;
      unsigned char *zl;
      unsigned int sz;             /* ziplist size in bytes */
      unsigned int count : 16;     /* count of items in ziplist */
      unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
      unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
      unsigned int recompress : 1; /* was this node previous compressed? */
      unsigned int attempted_compress : 1; /* node can't compress; too small */
      unsigned int extra : 10; /* more bits to steal for future usage */
  } quicklistNode;

  Nach dem Login kopieren

  redis为了节省内存空间，会将quicklist的节点用LZF压缩后存储，但这里不是全部压缩，可以配置compress的值，compress为0表示所有节点都不压缩，否则就表示从两端开始有多少个节点不压缩；compress如果是1，表示从两端开始，有1个节点不做LZF压缩。compress默认是0(不压缩)，具体可以根据你们业务实际使用场景去配置。

  redis 的配置文件可以配置该参数

  list-compress-depth 0

  Wert	Bedeutung
  0	Besonderer Wert bedeutet keine Komprimierung
  1	An jedem Ende der Quicklist befindet sich 1 Knoten, der nicht komprimiert ist, und der mittlere Knoten ist komprimiert sind nicht komprimiert und der mittlere Knoten ist komprimiert
  n	An beiden Enden der Quicklist gibt es n Knoten, die nicht komprimiert sind, und die Knoten in der Mitte sind komprimiert

  
  

  Es gibt auch ein Füllfeld, was bedeutet, dass die maximale Kapazität jedes Quicknode-Knotens unterschiedliche Bedeutungen hat kann auch auf andere Werte konfiguriert werden. ;list-max-ziplist-size -2

  Wenn der Wert eine positive Zahl ist, stellt er die Länge der Ziplist auf dem QuicklistNode-Knoten dar. Wenn der Wert beispielsweise 5 ist, enthält die Ziplist jedes QuicklistNode-Knotens höchstens 5 Datenelemente Begrenzt entsprechend der Anzahl der Bytes. Mögliche Werte sind -1 bis -5.