【Redis 设计与实现】String 的数据结构如何实现的？

博主介绍： 博主从事应用安全和大数据领域，有8年研发经验，5年面试官经验，Java技术专家，WEB架构师，阿里云专家博主，华为云云享专家，51CTO 专家博主

️ 个人社区：个人社区
个人主页：个人主页
专栏地址： Java 中级
八股文专题：剑指大厂，手撕 Java 八股文

1. Redis 有哪些数据结构

Redis 是一个开源的、基于内存的数据结构存储系统，它可以用作数据库、缓存和消息中间件。Redis 支持多种数据结构，这使得它可以非常灵活地处理不同类型的应用场景。以下是 Redis 支持的主要数据结构：

1. 字符串（String）

   • 最简单的类型，可以用来存储文本或二进制数据。
   • 支持原子操作如增加数值、设置过期时间等。

2. 列表（List）

   • 有序的字符串元素集合。
   • 可以在列表两端高效地插入或删除元素。
   • 常用于实现队列和栈。

3. 集合（Set）

   • 无序且不重复的字符串元素集合。
   • 支持交集、并集、差集等集合运算。

4. 有序集合（Sorted Set）

   • 类似于集合，但是每个成员关联一个分数（score），用于排序。
   • 成员是唯一的，但分数可以重复。
   • 适用于排行榜、范围查询等场景。

5. 哈希（Hash）

   • 字段与值之间的映射关系，适合存储对象。
   • 每个哈希可以存储多个字段-值对。
   • 适用于需要快速访问对象属性的场景。

6. 位图（Bitmaps）

   • 实际上是字符串的一种特殊用法，通过一系列位操作来处理。
   • 适用于高效的统计和分析功能。

7. HyperLogLog

   • 用于基数估计，即估算集合中不同元素的数量。
   • 使用很小的空间就可以进行大规模的计数。

8. 地理空间索引（Geospatial Indexing）

   • 允许存储地理位置信息，并执行距离计算、查找附近位置等操作。

9. 流（Streams）

   • 一种新的数据结构，从 Redis 5.0 版本开始引入。
   • 用于构建复杂的日志记录和消息传递系统。

这些数据结构让 Redis 能够适应各种应用场景，从简单的键值存储到复杂的消息处理和实时数据分析。

2. String 的数据结构如何实现的？

Redis 中的字符串（String）是其最基本的数据类型之一，可以用来存储文本或二进制数据。在内部实现上，Redis 的字符串实际上是通过一个名为 sds (Simple Dynamic String) 的结构来表示的。这个结构不仅提供了字符串的功能，还增加了一些额外的特性，如动态调整大小、内存预分配等，以提高效率和减少内存碎片。

sds 结构通常包含以下几个部分：

1. len：记录了当前字符串的实际长度。
2. alloc：记录了为字符串分配的总空间大小。
3. flags：用于标记字符串的一些属性，比如是否压缩等。
4. buf[]：实际存放字符串数据的字符数组。

具体来说，sds 的定义可能类似于以下 C 语言结构体（简化版）：

struct sdshdr {
    int len; // 字符串的实际长度
    int alloc; // 分配的总空间
    char buf[]; // 存放字符串数据
};

主要特点

• 动态扩展：当需要增长字符串时，sds 会自动分配更多的内存，并将旧的内容复制到新的缓冲区中。这比直接使用 C 语言的字符串更加灵活和安全。
• 内存预分配：为了避免频繁的内存分配，sds 在每次重新分配内存时都会多分配一些空间，这样在接下来的几次操作中就无需再次分配内存。
• 二进制安全：与 C 语言中的字符串不同，sds 可以存储任意二进制数据，因为它不依赖于空字符 \0 来标识字符串的结束。
• 高效的空间利用：sds 通过 len 和 alloc 字段有效地管理内存，减少了内存碎片问题。

例子

在 Redis 中，你可以使用以下命令来操作字符串：

• SET key value 设置键值对。
• GET key 获取键对应的值。
• INCR key 将键对应的整数值加 1。
• APPEND key value 将给定的值追加到现有字符串后面。

这些命令背后都涉及到对 sds 结构的操作。例如，APPEND 命令就需要检查当前分配的空间是否足够，如果不够则需要重新分配更大的空间并复制原有内容。

Redis 的字符串类型通过 sds 结构提供了一个高效且功能丰富的字符串处理机制，非常适合用来存储简单的文本信息或是作为其他复杂数据结构的基础构建块。

3. 为什么要这样设计 String 的数据结构？

Redis 的字符串（String）数据结构通过 sds (Simple Dynamic String) 实现，这样的设计有几个关键的原因和优势：

1. 二进制安全性：

   • 传统的 C 字符串是以空字符 \0 结尾的。这意味着在存储含有 \0 的二进制数据时会出现问题。而 sds 使用 len 字段明确记录字符串的实际长度，因此可以安全地存储任意二进制数据，不会因为遇到 \0 而提前结束。

2. 空间预分配：

   • 当需要扩展字符串时，sds 会尝试分配比实际所需更多的内存，这样可以减少频繁的内存重新分配操作。例如，如果当前字符串长度为 100 字节，而需要增加 50 字节，那么可能会分配 150 或更多字节的空间。这种策略减少了内存碎片，并提高了性能。

3. 高效修改：

   • 由于 sds 知道其内部缓冲区的大小 (alloc) 和已使用的部分 (len)，它可以快速地进行追加、删除等操作，而不需要像 C 字符串那样扫描整个字符串来找到结尾。
   • 这种设计使得 Redis 可以更高效地执行诸如 APPEND 和 SETRANGE 这样的命令。

4. 避免缓冲区溢出：

   • 传统的 C 字符串容易发生缓冲区溢出，当写入的数据超过分配的缓冲区大小时会导致未定义行为。sds 通过明确的长度信息避免了这种情况，提供了更好的安全性。

5. 内存效率：

   • 通过使用 alloc 字段，sds 可以更好地管理内存。它允许在不改变指针的情况下调整字符串内容，这有助于减少内存拷贝次数并提高性能。

6. 兼容性和一致性：

   • sds 提供了一个统一的接口来处理字符串，无论是在 Redis 内部还是对于外部开发者来说，都更容易理解和使用。同时，它也保持了与标准 C 库函数的兼容性，使得某些情况下可以直接使用这些函数。

7. 原子操作支持：

   • Redis 支持对字符串的一些原子操作，如 INCR、DECR 等。这些操作依赖于能够直接访问和修改字符串中的数值，sds 的设计简化了这些操作的实现。

sds 的设计旨在提供一个既高效又安全的字符串处理机制，适用于高性能键值存储系统的需求。它解决了传统 C 字符串存在的许多问题，同时引入了一些优化来提升整体性能。

4. 我们用 java 如何实现 Redis 的 String 的数据结构？

我们可以创建一个类来封装字符串数据，并提供一些方法来处理字符串的动态扩展、内存预分配等特性。实现示例：

public class SimpleDynamicString {
    private byte[] buf; // 存储实际的数据
    private int len; // 当前使用的长度
    private int alloc; // 分配的总空间

    public SimpleDynamicString() {
        this(16); // 默认分配 16 字节
    }

    public SimpleDynamicString(int initialCapacity) {
        if (initialCapacity < 0) throw new IllegalArgumentException("Initial capacity must be non-negative");
        this.alloc = initialCapacity;
        this.buf = new byte[alloc];
        this.len = 0;
    }

    public SimpleDynamicString(String s) {
        this(s.getBytes());
    }

    public SimpleDynamicString(byte[] bytes) {
        this(bytes, 0, bytes.length);
    }

    public SimpleDynamicString(byte[] bytes, int offset, int length) {
        this.alloc = Math.max(length, 16); // 至少分配 16 字节
        this.buf = new byte[alloc];
        System.arraycopy(bytes, offset, this.buf, 0, length);
        this.len = length;
    }

    public int length() {
        return len;
    }

    public void append(byte b) {
        ensureCapacity(len + 1);
        buf[len++] = b;
    }

    public void append(byte[] bytes) {
        append(bytes, 0, bytes.length);
    }

    public void append(byte[] bytes, int offset, int length) {
        ensureCapacity(len + length);
        System.arraycopy(bytes, offset, buf, len, length);
        len += length;
    }

    public byte[] getBytes() {
        return Arrays.copyOf(buf, len);
    }

    @Override
    public String toString() {
        return new String(buf, 0, len);
    }

    private void ensureCapacity(int newLen) {
        if (newLen > alloc) {
            // 新容量为旧容量的两倍或新需要的容量（取较大者）
            int newAlloc = Math.max(alloc * 2, newLen);
            buf = Arrays.copyOf(buf, newAlloc);
            alloc = newAlloc;
        }
    }

    public static void main(String[] args) {
        SimpleDynamicString sds = new SimpleDynamicString();
        sds.append("Hello".getBytes());
        sds.append(' ');
        sds.append("World!".getBytes());

        System.out.println(sds.toString()); // 输出: Hello World!
    }
}

• 构造函数：提供了几种初始化方式，包括默认构造、指定初始容量、从字符串或字节数组初始化。
• length()：返回当前字符串的实际长度。
• append()：用于追加单个字节或字节数组。当需要的空间超过已分配空间时，会自动扩展缓冲区。
• getBytes()：获取当前字符串内容的字节数组副本。
• toString()：将内部的字节数组转换为 Java 字符串并返回。
• ensureCapacity()：确保有足够的空间容纳新的数据，如果没有足够的空间，则重新分配更大的数组。

这个实现模仿了 Redis 的 sds 结构的一些关键特性，如二进制安全性和动态扩展。它还通过 ensureCapacity 方法实现了内存预分配，以减少频繁的内存分配操作。

精彩专栏推荐订阅：在下方专栏
2023年华为OD机试真题（A卷&B卷）+ 面试指导
精选100套 Java 项目案例
面试需要避开的坑（活动）
你找不到的核心代码
带你手撕 Spring
Java 初阶