张坤的个人博客

  • 首页
  • 分类
  • 标签
  • 日志

  • 搜索
Jenkins RabbitMQ Zookeeper IDEA Logstash Kibana ELK NIO Netty Spring Cloud Golang DataX Elasticsearch React Native Mysql H2 Socket Spring Boot Kafka Mybatis Sqlmap Vue Postgresql Docker Vert.x Flutter Flink Redis

Redis 压缩列表

发表于 2020-05-30 | 分类于 Redis | 0 | 阅读次数 32

压缩链表简介

压缩列表(ziplist)是List类型和Hash类型的底层编码实现之一。比如List底层的编码有两种:ziplist和linkedlist,hash类型也有两种:ziplist和hashtable。这两种Redis的基本类型都用到了ziplist编码。

为什么List和Hash都用到了ziplist去做底层实现呢?因为ziplist对空间的利用节省到了极致,先来看下ziplist的数据结构,在源码ziplist.c文件中注释中可以看到,但是我并没有找到相关结构体的定义,只找到了entry节点的结构体定义。ziplist是个连续的entry节点组成的列表。

压缩列表数据结构

ziplist结构:
ziplist_2.png

<zlbytes><zltail><zllen><entry><entry><zlend>
  • zlbytes:记录着ziplist总大小(byte)
  • zltail:ziplist表尾的entry节点距ziplist起始位置有多少个字节,用zltail通过计算可以很快得出ziplist表尾的位置
  • zllen:压缩列表中entry节点的个数
  • entry:节点,在ziplist中连续排列
  • zlend:用于标记ziplist的结束位置,相当于字符串用'\0'来标记结束位置

entry结构:

typedef struct zlentry {
    unsigned int prevrawlensize, prevrawlen;	// prevrawlen前一个entry的长度
    unsigned int lensize, len;
    unsigned int headersize;
    unsigned char encoding;	// p的实际类型
    unsigned char *p;	// 节点的值
} zlentry;
  • p:节点内容,节点可以是个字节数组或者整数,它的类型和长度由encoding属性决定
  • prevrawlen:前一个entry的长度,如果前一节点的长度小于 254 字节, 那么 prevrawlen 属性的长度为 1 字节,如果前一节点的长度大于等于 254 字节, 那么prevrawlen属性的长度为 5 字节
  • encoding:p属性的实际类型,这个是ziplist节省空间的关键,如果可以动态调整p的类型大小
    ziplist_1.png

连锁更新

前面说过, 每个节点的 prevrawlen 属性都记录了前一个节点的长度:

  • 如果前一节点的长度小于 254 字节, 那么 prevrawlen 属性需要用 1 字节长的空间来保存这个长度值。
  • 如果前一节点的长度大于等于 254 字节, 那么 prevrawlen 属性需要用 5 字节长的空间来保存这个长度值。

ziplist_1.jpg

因为连锁更新在最坏情况下需要对压缩列表执行 N 次空间重分配操作, 而每次空间重分配的最坏复杂度为 O(N)

# Jenkins # RabbitMQ # Zookeeper # IDEA # Logstash # Kibana # ELK # NIO # Netty # Spring Cloud # Golang # DataX # Elasticsearch # React Native # Mysql # H2 # Socket # Spring Boot # Kafka # Mybatis # Sqlmap # Vue # Postgresql # Docker # Vert.x # Flutter # Flink # Redis
ReactNative实战
Redis 链表
  • 文章目录
  • 站点概览
会Coding的猴子

会Coding的猴子

57 日志
19 分类
28 标签
RSS
Github
Creative Commons
© 2021 会Coding的猴子
由 Halo 强力驱动
|
主题 - NexT.Gemini v5.1.4

湘ICP备18011740号