Table of Contents
概述
压缩双链表的具体实现
为什么要用 ziplist
Home Database Mysql Tutorial 深入剖析 redis 数据结构 ziplist

深入剖析 redis 数据结构 ziplist

Jun 07, 2016 pm 04:35 PM
re redis Analyze data structure Overview go deep

概述 在 redis 中,list 有两种存储方式:双链表(LinkedList)和压缩双链表(ziplist)。双链表即普通数据结构中遇到的,在 adlist.h 和 adlist.c 中实现。压缩双链表以连续的内存空间来表示双链表,压缩双链表节省前驱和后驱指针的空间(8B),这在小的 li

概述

在 redis 中,list 有两种存储方式:双链表(LinkedList)和压缩双链表(ziplist)。双链表即普通数据结构中遇到的,在 adlist.h 和 adlist.c 中实现。压缩双链表以连续的内存空间来表示双链表,压缩双链表节省前驱和后驱指针的空间(8B),这在小的 list 上,压缩效率是非常明显的;压缩双链表在 ziplist.h 和 ziplist.c 中实现。

这篇主要详述压缩双链表,普通双链表可以参看其他资料。

压缩双链表的具体实现

在压缩双链表中,节省了前驱和后驱指针的空间,共 8个字节,这让数据在内存中更为紧凑。只要清晰的描述每个数据项的边界,就可以轻易得到后驱数据项的位置;只要描述前驱数据项的大小,就可以定位前驱数据项的位置,redis 就是这么做的。

ziplist 的格式可以表示为:

<zlbytes><zltail><zllen><entry>...<entry><zlend></zlend></entry></entry></zllen></zltail></zlbytes>
Copy after login

zlbytes 是 ziplist 占用的空间;zltail 是最后一个数据项的偏移位置,这方便逆向遍历链表,也是双链表的特性;zllen 是数据项 entry 的个数;zlend 就是 255,占 1B.详细展开 entry 的结构。

entry 的格式即为典型的 type-lenght-value,即 TLV,表述如下:

|<prelen><len>><data>|
|---1----------------2--------------3---|</data></len></prelen>
Copy after login

域 1)是前驱数据项的大小。因为不用描述前驱的数据类型,描述较为简单。

域 2) 是此数据项的的类型和数据大小。为了节省空间,redis 预设定了多种长度的字符串和整数。

3种长度的字符串
#define ZIP_STR_06B (0 
<p>域 3)为真正的数据。</p>
<p>透过 ziplist 查找函数 ziplistFind(),熟悉 ziplist entry 对数据格式:</p>
<pre class="brush:php;toolbar:false">// 在 ziplist 中查找数据项
/* Find pointer to the entry equal to the specified entry. Skip 'skip' entries
* between every comparison. Returns NULL when the field could not be found. */
unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip) {
    int skipcnt = 0;
    unsigned char vencoding = 0;
    long long vll = 0;
    while (p[0] != ZIP_END) {
        unsigned int prevlensize, encoding, lensize, len;
        unsigned char *q;
        ZIP_DECODE_PREVLENSIZE(p, prevlensize);
        // 跳过前驱数据项大小,解析数据项大小
        // len 为 data 大小
        // lensize 为 len 所占内存大小
        ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
        // q 指向 data
        q = p + prevlensize + lensize;
        if (skipcnt == 0) {
            /* Compare current entry with specified entry */
            if (ZIP_IS_STR(encoding)) {
            // 字符串比较
                if (len == vlen && memcmp(q, vstr, vlen) == 0) {
                    return p;
                }
            } else {
            // 整数比较
                /* Find out if the searched field can be encoded. Note that
                 * we do it only the first time, once done vencoding is set
                 * to non-zero and vll is set to the integer value. */
                if (vencoding == 0) {
                    // 尝试将 vstr 解析为整数
                    if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) {
                        /* If the entry can't be encoded we set it to
                         * UCHAR_MAX so that we don't retry again the next
                         * time. */
                        // 不能编码为数字!!!会导致当前查找的数据项被跳过
                        vencoding = UCHAR_MAX;
                    }
                    /* Must be non-zero by now */
                    assert(vencoding);
                }
                /* Compare current entry with specified entry, do it only
                 * if vencoding != UCHAR_MAX because if there is no encoding
                 * possible for the field it can't be a valid integer. */
                if (vencoding != UCHAR_MAX) {
                    // 读取整数
                    long long ll = zipLoadInteger(q, encoding);
                    if (ll == vll) {
                        return p;
                    }
                }
            }
            /* Reset skip count */
            skipcnt = skip;
        } else {
            /* Skip entry */
            skipcnt--;
        }
        // 移动到 ziplist 的下一个数据项
        /* Move to next entry */
        p = q + len;
    }
    // 没有找到
    return NULL;
}
Copy after login

注意,ziplist 每次插入新的数据都要 realloc。

为什么要用 ziplist

redis HSET 命令官网的描述是:

Sets field in the hash stored at key to value. If key does not exist, a new key holding a hash is created. If field already exists in the hash, it is overwritten.

实际上,HSET 底层所使用的数据结构正是上面所说的 ziplist,而不是平时所说的 hashtable。

那为什么要使用 ziplist,反对的理由是查找来说,(ziplist O(N))VS(hashtable O(1))?redis 可是为内存节省想破了头。首先 ziplist 比 hashtable 更节省内存,再者,redis 考虑到如果数据紧凑的 ziplist 能够放入 CPU 缓存(hashtable 很难,因为它是非线性的),那么查找算法甚至会比 hashtable 要快!。ziplist 由此有性能和内存空间的有事。

捣乱 2014-6-20

http://daoluan.net

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

How to build the redis cluster mode How to build the redis cluster mode Apr 10, 2025 pm 10:15 PM

Redis cluster mode deploys Redis instances to multiple servers through sharding, improving scalability and availability. The construction steps are as follows: Create odd Redis instances with different ports; Create 3 sentinel instances, monitor Redis instances and failover; configure sentinel configuration files, add monitoring Redis instance information and failover settings; configure Redis instance configuration files, enable cluster mode and specify the cluster information file path; create nodes.conf file, containing information of each Redis instance; start the cluster, execute the create command to create a cluster and specify the number of replicas; log in to the cluster to execute the CLUSTER INFO command to verify the cluster status; make

How to clear redis data How to clear redis data Apr 10, 2025 pm 10:06 PM

How to clear Redis data: Use the FLUSHALL command to clear all key values. Use the FLUSHDB command to clear the key value of the currently selected database. Use SELECT to switch databases, and then use FLUSHDB to clear multiple databases. Use the DEL command to delete a specific key. Use the redis-cli tool to clear the data.

How to read redis queue How to read redis queue Apr 10, 2025 pm 10:12 PM

To read a queue from Redis, you need to get the queue name, read the elements using the LPOP command, and process the empty queue. The specific steps are as follows: Get the queue name: name it with the prefix of "queue:" such as "queue:my-queue". Use the LPOP command: Eject the element from the head of the queue and return its value, such as LPOP queue:my-queue. Processing empty queues: If the queue is empty, LPOP returns nil, and you can check whether the queue exists before reading the element.

How to use the redis command How to use the redis command Apr 10, 2025 pm 08:45 PM

Using the Redis directive requires the following steps: Open the Redis client. Enter the command (verb key value). Provides the required parameters (varies from instruction to instruction). Press Enter to execute the command. Redis returns a response indicating the result of the operation (usually OK or -ERR).

How to use redis lock How to use redis lock Apr 10, 2025 pm 08:39 PM

Using Redis to lock operations requires obtaining the lock through the SETNX command, and then using the EXPIRE command to set the expiration time. The specific steps are: (1) Use the SETNX command to try to set a key-value pair; (2) Use the EXPIRE command to set the expiration time for the lock; (3) Use the DEL command to delete the lock when the lock is no longer needed.

How to configure Lua script execution time in centos redis How to configure Lua script execution time in centos redis Apr 14, 2025 pm 02:12 PM

On CentOS systems, you can limit the execution time of Lua scripts by modifying Redis configuration files or using Redis commands to prevent malicious scripts from consuming too much resources. Method 1: Modify the Redis configuration file and locate the Redis configuration file: The Redis configuration file is usually located in /etc/redis/redis.conf. Edit configuration file: Open the configuration file using a text editor (such as vi or nano): sudovi/etc/redis/redis.conf Set the Lua script execution time limit: Add or modify the following lines in the configuration file to set the maximum execution time of the Lua script (unit: milliseconds)

How to use the redis command line How to use the redis command line Apr 10, 2025 pm 10:18 PM

Use the Redis command line tool (redis-cli) to manage and operate Redis through the following steps: Connect to the server, specify the address and port. Send commands to the server using the command name and parameters. Use the HELP command to view help information for a specific command. Use the QUIT command to exit the command line tool.

How to set the redis expiration policy How to set the redis expiration policy Apr 10, 2025 pm 10:03 PM

There are two types of Redis data expiration strategies: periodic deletion: periodic scan to delete the expired key, which can be set through expired-time-cap-remove-count and expired-time-cap-remove-delay parameters. Lazy Deletion: Check for deletion expired keys only when keys are read or written. They can be set through lazyfree-lazy-eviction, lazyfree-lazy-expire, lazyfree-lazy-user-del parameters.

See all articles