Redis有以下几种常用的数据类型:

redis数据是如何组织的
为了实现从键到值的快速访问,Redis 使用了一个哈希表来保存所有键值对。
Redis全局哈希表(Global Hash Table)是指在Redis数据库内部用于存储所有键值对的主要数据结构。它的实现原理涉及到哈希表、字典、渐进式rehash等技术,以下是Redis全局哈希表的实现原理和查询流程:
实现原理:
哈希表(Hash Table):
Redis的全局哈希表是由多个哈希表构成的,每个哈希表称为一个数据库(DB)。数据库的数量可以通过配置进行设置,默认是16个。每个数据库都是一个独立的哈希表,负责存储键值对。
字典(Dictionary):
每个数据库都使用字典(Dictionary)来实现键值对的存储。字典是一种高效的键值对存储结构,它使用哈希表来支持快速的查找、插入和删除操作。
渐进式rehash:
当数据库的键值对数量较多时,为了保持查询性能,Redis会在不中断服务的情况下,逐步将旧的数据库哈希表中的数据迁移到新的数据库哈希表中,这个过程叫做渐进式rehash。这样,Redis能够平滑地将数据从旧的哈希表迁移到新的哈希表,避免大规模的数据迁移对性能造成影响。

查询流程:
整个查询流程涉及到多次哈希计算和哈希表查找,这使得Redis能够在平均时间复杂度为O(1)的情况下,高效地进行键值对的查询操作。由于Redis的全局哈希表是一个核心组件,其优化和设计对于保障Redis的性能和可用性非常重要。
如果你只是了解了哈希表的 O(1) 复杂度和快速查找特性,那么,当你往 Redis 中写入大量数据后,就可能发现操作有时候会突然变慢了。这其实是因为你忽略了一个潜在的风险点,那就是哈希表的冲突问题和 rehash 可能带来的操作阻塞。
为什么哈希表操作变慢了?
Redis 解决哈希冲突的方式,就是链式哈希。链式哈希也很容易理解,就是指同一个哈希桶中的多个元素用一个链表来保存,它们之间依次用指针连接。

哈希冲突是指在使用哈希函数将键映射到哈希表中的索引时,两个或多个键被映射到相同的索引位置。在Redis中,哈希表是通过哈希函数将键映射到一个固定数量的桶(bucket)中的。
Redis使用MurmurHash2算法作为默认的哈希函数,它是一种快速且低碰撞率的哈希函数。然而,即使使用了高质量的哈希函数,仍然存在哈希冲突的可能性。
当发生哈希冲突时,Redis使用链地址法(chaining)来解决。具体来说,每个桶中存储的是一个链表,链表中的每个节点都包含了键值对。当多个键被映射到同一个桶时,它们会被添加到链表中,形成一个键值对的集合。
当执行哈希表的读取操作时,Redis会遍历链表,直到找到匹配的键值对或者链表结束。这个过程的时间复杂度取决于链表的长度,因此,如果哈希冲突较多,链表会变得很长,导致读取操作的性能下降。
为了减少哈希冲突的发生,可以采取以下措施:
哈希冲突是不可避免的,但可以通过选择合适的哈希函数和调整哈希表的大小来减少其发生的概率,并且Redis的链地址法能够有效地解决哈希冲突带来的问题。
但是,这里依然存在一个问题,哈希冲突链上的元素只能通过指针逐一查找再操作。如果哈希表里写入的数据越来越多,哈希冲突可能也会越来越多,这就会导致某些哈希冲突链过长,进而导致这个链上的元素查找耗时长,效率降低。对于追求“快”的 Redis 来说,这是不太能接受的。
所以,Redis 会对哈希表做 rehash 操作。rehash 也就是增加现有的哈希桶数量,让逐渐增多的 entry 元素能在更多的桶之间分散保存,减少单个桶中的元素数量,从而减少单个桶中的冲突。
那具体怎么做rehash呢?
Redis的rehash是指在哈希表扩容或缩小时,重新计算并重新分配所有键值对的过程。rehash的目的是为了保持哈希表的负载因子在一个合理的范围内,以提高哈希表的性能。
在Redis中,rehash是一个渐进式的过程,它不会一次性地将所有键值对重新分配到新的哈希表中,而是分多次进行,每次处理一小部分键值对。这种渐进式的rehash过程可以保证在rehash期间,Redis仍然可以正常处理读取和写入操作,不会阻塞客户端请求。
具体的rehash过程如下:
通过渐进式的rehash过程,Redis可以平滑地将键值对从旧哈希表迁移到新哈希表,避免了一次性的大规模迁移带来的性能问题。同时,由于读取操作可以同时在两个哈希表中进行,所以即使在rehash过程中,Redis仍然可以提供正常的读取服务。
需要注意的是,rehash过程是一个相对耗时的操作,特别是在哈希表中存储了大量键值对的情况下。因此,在进行rehash时,应该避免对Redis进行大量的写入操作,以免影响性能。

底层实现复杂度总结

一、字符串(String)
适用场景
字符串(String)类型在Redis中是最常用的数据类型之一,适用于以下场景:
底层实现是什么
当我们在Redis中存储字符串时,Redis使用了一种称为简单动态字符串(Simple Dynamic String,SDS)的数据结构来表示字符串。
SDS是Redis自己实现的一种字符串表示方式,相比于传统的C语言字符串,SDS具有许多优势和特点。