分类 "读书笔记" 下的文章

个人真的很喜欢这本书, 从对C语言一窍不通, 到发现C语言竟然如此简洁, 以至于我喜欢上了C! 对此前面的底层数据结构也读了几次, 大致整理了书里的内容, 后面的就粗略看了一下, 不再细细整理了.

Redis的设计与实现(1)-SDS简单动态字符串
Redis的设计与实现(2)-链表
Redis的设计与实现(3)-字典
Redis的设计与实现(4)-跳跃表
Redis的设计与实现(5)-整数集合
Redis的设计与实现(6)-压缩列表

整体的感悟吧, 觉得 Redis 的作者, 对每一块内存非常吝啬, 为了节省内存而制造出各种各样的编码和技巧. 阅读源码的过程中, 也学习到了宏的技巧, 比如说:

#define ZIP_ENTRY_ENCODING(ptr, encoding) do {  \
    (encoding) = (ptr[0]); \
    if ((encoding) < ZIP_STR_MASK) (encoding) &= ZIP_STR_MASK; \
} while(0)





阅读全文

压缩列表 (ziplist) 是列表键和哈希键的底层实现之一.

  1. 当一个列表键只包含少量列表项, 并且每个列表项要么就是小整数值, 要么就是长度比较短的字符串, 那么 Redis 就会使用压缩列表来做列表键的底层实现.
  2. 当一个哈希键只包含少量键值对, 并且每个键值对的键和值要么就是小整数值, 要么就是长度比较短的字符串, 那么 Redis 就会使用压缩列表来做哈希键的底层实现.

1. 压缩列表的构成

压缩列表是 Redis 为了节约内存而开发的, 由一系列特殊编码的连续内存块组成的顺序型 (sequential) 数据结构.
一个压缩列表可以包含任意多个节点 (entry) , 每个节点可以保存一个字节数组或者一个整数值.


阅读全文

整数集合(intset)是集合键的底层实现之一: 当一个集合只包含整数值元素, 并且这个集合的元素数量不多时, Redis 就会使用整数集合作为集合键的底层实现.

整数集合 (intset) 是 Redis 用于保存整数值的集合抽象数据结构, 它可以保存类型为 int16_t , int32_t 或者 int64_t 的整数值, 并且保证集合中不会出现重复元素.

1. 整数集合的定义

每个 intset.h/intset 结构表示一个整数集合:

typedef struct intset {
  // 编码方式
  uint32_t encoding;
  // 集合包含的元素数量
  uint32_t length;
  // 保存元素的数组
  int8_t contents[];
} intset;

阅读全文

跳跃表 (skiplist) 是一种有序数据结构, 它通过在每个节点中维持多个指向其他节点的指针, 从而达到快速访问节点的目的.

跳跃表支持平均 O(log N) 最坏 O(N) 复杂度的节点查找, 还可以通过顺序性操作来批量处理节点.

在大部分情况下, 跳跃表的效率可以和平衡树相媲美, 并且因为跳跃表的实现比平衡树要来得更为简单, 所以有不少程序都使用跳跃表来代替平衡树.

Redis 使用跳跃表作为有序集合键的底层实现之一: 如果一个有序集合包含的元素数量比较多, 又或者有序集合中元素的成员 (member) 是比较长的字符串时, Redis 就会使用跳跃表来作为有序集合键的底层实现.

和链表, 字典等数据结构被广泛地应用在 Redis 内部不同, Redis 只在两个地方用到了跳跃表, 一个是实现有序集合键, 另一个是在集群节点中用作内部数据结构, 除此之外, 跳跃表在 Redis 里面没有其他用途.

阅读全文

Redis 的数据库使用字典实现, 对数据库的增, 删, 查, 改也是构建在对字典的操作之上的.

字典是哈希键的底层实现之一: 当一个哈希键包含的键值对比较多, 又或者键值对中的元素都是比较长的字符串时, Redis 将会使用字典作为哈希键的底层实现.

1. 哈希表

Redis 的字典使用哈希表作为底层实现, 一个哈希表里面可以有多个哈希表节点, 而每个哈希表节点就保存了字典中的一个键值对.

Redis 字典所使用的哈希表由 dict.h/dictht 结构定义:

typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码,用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

阅读全文

链表在 Redis 中的应用非常广泛, 比如列表键的底层实现之一就是链表: 当一个列表键包含了数量比较多的元素, 又或者列表中包含的元素都是比较长的字符串时, Redis 就会使用链表作为列表键的底层实现.

除了链表键之外, 发布与订阅, 慢查询, 监视器等功能也用到了链表, Redis 服务器还使用链表保存多个客户端的状态信息, 以及使用链表来构建客户端输出缓冲区(output buffer).

1. 链表的定义

每个链表节点使用一个 adlist.h/listNode 结构来表示:

typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点的值
    void *value;
} listNode;

使用 adlist.h/list 来操作链表会更方便

typedef struct list {
    // 表头节点
    listNode *head;
    // 表尾节点
    listNode *tail;
    // 链表所包含的节点数量
    unsigned long len;
    // 节点值复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void (*free)(void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr, void *key);
} list;

可见, 它是一个双向链表.

阅读全文

1. 计算机系统漫游

还是从hello world开始(hello.c):

#include <stdio.h>

int main()
{
    printf("hello, world\n");
}

逐步介绍它的整个生命周期: 被程序员创建 -> 到在系统上运行 -> 输出简单的消息 -> 然后终止.

1.1 信息就是位 + 上下文

大部分的现代操作系统都使用ASCII标准来表示文本字符, 即使用一个单字节大小的整数值来表示每个字符. 具体来说:

  1. 第一个字节的整数值是35, 对应的是字符"#";
  2. 第二个字节的整数值是105, 对应的是字符"i";
  3. 每个文本行以不可见的字符(整数值为10), 换行符, "n"结尾.

此外, 由ASCII字符构成的文件成为文本文件, 所有其他文件都称为二进制文件.

阅读全文

现在在高铁上, 赶着春节回家过年, 无座站票, 电脑只能放行李架上, 面对着行李架撸键盘--看过<Redis的设计与实现>这本书, 突然想起, 便整理下SDS的内容, 相对后面的章节, 算是比较简单的~

大多数情况下, Redis使用SDS(Simple Dynamic String, 简单动态字符串)作为字符串表示, 比起C字符串, SDS具有以下优点:

  1. 常数复杂度获取字符串长度;
  2. 杜绝缓冲区溢出;
  3. 减少修改字符串时带来的内存重分配次数;
  4. 二进制安全;
  5. 兼容部分C字符串函数.

以上列举的优点, 也算是这篇文章的主要内容. 先从定义说起吧:

1. SDS的定义

SDS结构定义如下(sds.h/sdshdr):

struct sdshdr {
    // 记录buf数组中已使用字节的数量, 等于SDS所保存字符串的长度
    int len;
    // 记录buf数组中未使用字节的数量
    int free;
    // 字节数组, 用于保存字符串
    char buf[];
}
  1. len属性记录了已使用的字节数量(字符串长度);
  2. free属性的值为0, 表示这个SDS没有未使用的空间;
  3. free属性的值为5, 表示这个SDS保存了一个5字节长的字符串;
  4. buf属性是一个char类型的数组, 数组的最后一个字节保存了空字符0.

SDS遵循C字符串以空字符串结尾的惯例, 空字符不计入SDS的len属性, 即额外为空字符分配了1字节的空间, 并且添加空字符到字符串末尾均由SDS函数自动完成, 对使用者完全透明. 该特性带来的好处是, SDS可以直接复用C字符串函数库的部分函数.

阅读全文