Redis核心技术01-基础数据结构

# Redis核心技术01-基础数据结构

Redis快的重要表现在：它接收到一个键值对操作后，能以微秒级别的速度找到数据，并快速完成操作。

一方面，这是因为它是内存数据库，所有操作都在内存上完成，内存的访问速度本身就很快。另一方面，这要归功于它的数据结构。这是因为，键值对是按一定的数据结构来组织的，操作键值对最终就是对数据结构进行增删改查操作，所以高效的数据结构是 Redis 快速处理数据的基础。

# 键值用什么结构组织

为了实现从键到值的快速访问，Redis使用一个哈希表来保存所有键值对。一个哈希表，其实就是一个数组，数组的每个元素为一个哈希桶，每个哈希桶保存了键值对数据。

但是哈希桶保存的键值对数据并非真正的数据，而是数据的指针，也就是说哈希桶中的元素都是指向它们的指针。

哈希表的最大好处很明显，就是让我们可以用 O(1) 的时间复杂度来快速查找到键值对——我们只需要计算键的哈希值，就可以知道它所对应的哈希桶位置，然后就可以访问相应的 entry 元素，而entry元素中存储的键值地址。

# 哈希冲突

哈希表有一个问题：当数据量越来越多的时候，某两个数据计算出的哈希值可能相同，那么这两个值就会落到同一个哈希桶中。

Redis解决哈希冲突的方式就是链式哈希，也就是哈希表和链表相结合的方式。

# Rehash和渐进式 rehash

哈希冲突链上的元素只能通过指针逐一查找再操作。如果哈希表里写入的数据越来越多，哈希冲突可能也会越来越多，这就会导致某些哈希冲突链过长，进而导致这个链上的元素查找耗时长，效率降低。

Redis 会对哈希表做 rehash 操作。rehash 也就是增加现有的哈希桶数量，让逐渐增多的 entry 元素能在更多的桶之间分散保存，减少单个桶中的元素数量，从而减少单个桶中的冲突。

为了使rehash操作更高效，Redis默认使用了两个全局哈希表：哈希表1和哈希表2。

一开始，当你刚插入数据时，默认使用哈希表 1，此时的哈希表 2 并没有被分配空间。随着数据逐步增多，Redis 开始执行 rehash，这个过程分为三步：

给哈希表 2 分配更大的空间，例如是当前哈希表 1 大小的两倍；
把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中；
释放哈希表 1 的空间。

到此，我们就从哈希表1切换到哈希表2能够存储更多的数据，而原来的哈希表1留作下一次rehash扩容备用。

这个过程还存在一个问题：如果一次性把哈希表 1 中的数据都迁移完，会造成 Redis 线程阻塞，无法服务其他请求。此时，Redis 就无法快速访问数据了。

因此就要引入渐进式rehash，简单来说就是在第二步拷贝数据时，Redis 仍然正常处理客户端请求，每处理一个请求时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entries。