深入浅出：Redis查找原理
Redis是一种基于内存的高性能的键值型数据库，广泛应用于互联网、物联网等大型分布式系统中。它支持一系列数据结构，如字符串、哈希、列表、集合、有序集合等，并提供多种操作接口，如读、写、删除、查找等。在Redis中，查找是最常用的操作之一，而其查找的效率也极高，主要得益于其使用了类似于哈希表的数据结构来实现。下面将深入浅出地介绍Redis的查找原理。
Redis的查找原理
RedisIDC.com/xtywjcwz/27732.html" target="_blank">中的查找操作是通过哈希表来实现的，这个哈希表在Redis中被称为字典（dict）。字典中，每个节点都存储了一个键值对，其包含了键、值和下一个节点的指针。下面是字典节点的结构体定义：
typedef struct dictEntry {void *key;//键值union {void *val;uint64_t u64;int64_t s64;double d;} v;//值struct dictEntry *next;//下一个节点的指针} dictEntry;
字典采用链地址法来解决哈希冲突，即对于哈希值相同的键值对，将其放入同一个链表中。下面是字典的结构体定义：
typedef struct dict {dictType *type;//字典类型void *privdata;//私有数据uint64_t ht[2];//哈希表数组uint64_t rehashidx;//当前rehash索引int iterators;//字典遍历器个数} dict;
其中，ht[0]和ht[1]两个哈希表数组分别表示当前的哈希表和rehash后的哈希表。因为rehash操作是一种渐进式的操作，在rehash操作中，字典会将当前哈希表的所有键值对复制到一个新的哈希表中，并同时保留当前哈希表，这样可以避免一次性的复制操作导致的性能问题。
我们来看一下Redis中的查找操作具体是如何实现的。对于普通的查找操作，Redis首先会计算出键的哈希值，并利用哈希值得到对应的哈希表索引位置。然后，Redis会在哈希表的对应链表上遍历，找到匹配的键值对并返回值。代码如下：
void *dictFetchValue(dict *d, const void *key) {dictEntry *de;de = dictFind(d,key);return de ? de->v.val : NULL;}
其中，dictFind函数是查找操作的核心函数，其代码如下：
dictEntry *dictFind(dict *d, const void *key) {dictEntry *he;unsigned int h, idx, table;if (d->ht[0].size == 0) return NULL;if (dictIsRehashing(d)) _dictRehashStep(d);h = dictHashKey(d, key);for (table = 0; table idx = h & d->ht[table].sizemask;he = d->ht[table].table[idx];while(he) {if (dictCompareKeys(d, key, he->key))return he;he = he->next;}if (!dictIsRehashing(d)) return NULL;}return NULL;}
dictFind函数首先会计算出键的哈希值，然后根据当前是否正在进行rehash操作，分别在当前哈希表和rehash后的哈希表上进行查找。而哈希表的索引位置则是通过哈希值和哈希表大小的计算得到的。
dictFind函数的查找过程有几个需要注意的点。在链表中遍历时，需要通过dictCompareKeys函数来比较键值是否相等。当在多个字典中同时插入相同的键值对时，字典在查找时会先匹配前面插入的键值对。在进行rehash操作时，需要先进行单步rehash操作，以保证查找能够顺利地进行。在查找过程中，需要遍历两个哈希表，因为rehash操作是渐进式的操作，暂时存在两个哈希表中。
总结
本文深入浅出地介绍了Redis的查找原理，即通过哈希表来实现。我们从Redis中字典的结构体开始，逐步剖析了字典、哈希表以及查找操作的实现。在实际开发中，了解Redis内部的实现原理能够更好地优化代码，提升系统性能。
香港服务器首选树叶云，2H2G首月10元开通。树叶云（shuyeidc.com）提供简单好用，价格厚道的香港/美国云 服务器 和独立服务器。IDC+ISP+ICP资质。ARIN和APNIC会员。成熟技术团队15年行业经验。
memcached和redis的区别
medis与Memcached的区别传统MySQL+ Memcached架构遇到的问题 实际MySQL是适合进行海量数据存储的，通过Memcached将热点数据加载到cache，加速访问，很多公司都曾经使用过这样的架构，但随着业务数据量的不断增加，和访问量的持续增长，我们遇到了很多问题： 需要不断进行拆库拆表，Memcached也需不断跟着扩容，扩容和维护工作占据大量开发时间。 与MySQL数据库数据一致性问题。 数据命中率低或down机，大量访问直接穿透到DB，MySQL无法支撑。 4.跨机房cache同步问题。 众多NoSQL百花齐放，如何选择 最近几年，业界不断涌现出很多各种各样的NoSQL产品，那么如何才能正确地使用好这些产品，最大化地发挥其长处，是我们需要深入研究和思考的问题，实际归根结底最重要的是了解这些产品的定位，并且了解到每款产品的tradeoffs，在实际应用中做到扬长避短，总体上这些NoSQL主要用于解决以下几种问题 1.少量数据存储，高速读写访问。 此类产品通过数据全部in-momery 的方式来保证高速访问，同时提供数据落地的功能，实际这正是Redis最主要的适用场景。 2.海量数据存储，分布式系统支持，数据一致性保证，方便的集群节点添加/删除。 3.这方面最具代表性的是dynamo和bigtable 2篇论文所阐述的思路。 前者是一个完全无中心的设计，节点之间通过gossip方式传递集群信息，数据保证最终一致性，后者是一个中心化的方案设计，通过类似一个分布式锁服务来保证强一致性,数据写入先写内存和redo log，然后定期compat归并到磁盘上，将随机写优化为顺序写，提高写入性能。 free，auto-sharding等。 比如目前常见的一些文档数据库都是支持schema-free的，直接存储json格式数据，并且支持auto-sharding等功能，比如mongodb。 面对这些不同类型的NoSQL产品,我们需要根据我们的业务场景选择最合适的产品。 Redis适用场景，如何正确的使用 前面已经分析过，Redis最适合所有数据in-momory的场景，虽然Redis也提供持久化功能，但实际更多的是一个disk-backed的功能，跟传统意义上的持久化有比较大的差别，那么可能大家就会有疑问，似乎Redis更像一个加强版的Memcached，那么何时使用Memcached,何时使用Redis呢?如果简单地比较Redis与Memcached的区别，大多数都会得到以下观点： 1Redis不仅仅支持简单的k/v类型的数据，同时还提供list，set，zset，hash等数据结构的存储。 2Redis支持数据的备份，即master-slave模式的数据备份。 3Redis支持数据的持久化，可以将内存中的数据保持在磁盘中，重启的时候可以再次加载进行使用。 抛开这些，可以深入到Redis内部构造去观察更加本质的区别，理解Redis的设计。 在Redis中，并不是所有的数据都一直存储在内存中的。 这是和Memcached相比一个最大的区别。 Redis只会缓存所有的 key的信息，如果Redis发现内存的使用量超过了某一个阀值，将触发swap的操作，Redis根据“swappability = age*log(size_in_memory)”计 算出哪些key对应的value需要swap到磁盘。 然后再将这些key对应的value持久化到磁盘中，同时在内存中清除。 这种特性使得Redis可以 保持超过其机器本身内存大小的数据。 当然，机器本身的内存必须要能够保持所有的key，毕竟这些数据是不会进行swap操作的。 同时由于Redis将内存 中的数据swap到磁盘中的时候，提供服务的主线程和进行swap操作的子线程会共享这部分内存，所以如果更新需要swap的数据，Redis将阻塞这个 操作，直到子线程完成swap操作后才可以进行修改。 使用Redis特有内存模型前后的情况对比： VM off: 300k keys, 4096 bytes values: 1.3G used VM on:300k keys, 4096 bytes values: 73M used VM off: 1 million keys, 256 bytes values: 430.12M used VM on:1 million keys, 256 bytes values: 160.09M used VM on:1 million keys, values as large as you want, still: 160.09M used当 从Redis中读取数据的时候，如果读取的key对应的value不在内存中，那么Redis就需要从swap文件中加载相应数据，然后再返回给请求方。 这里就存在一个I/O线程池的问题。 在默认的情况下，Redis会出现阻塞，即完成所有的swap文件加载后才会相应。 这种策略在客户端的数量较小，进行 批量操作的时候比较合适。 但是如果将Redis应用在一个大型的网站应用程序中，这显然是无法满足大并发的情况的。 所以Redis运行我们设置I/O线程 池的大小，对需要从swap文件中加载相应数据的读取请求进行并发操作，减少阻塞的时间。 如果希望在海量数据的环境中使用好Redis，我相信理解Redis的内存设计和阻塞的情况是不可缺少的。
memcached可以持久化吗
memcached 是缓存系统，通过名字就可以看出来，官网也明确说了（Free & open source, high-performance, distributed memory object caching system），之所以是缓存系统，就说明它不会作为可靠的数据存储，所以并不支持持久化。 另一个是redis，他是一个存储系统，官网也说了。 只不过redis是在内存中存储的，所以速度快，因为是存储系统，所以可以作为一个可靠的数据存储系统。 支持持久化。
Redis和Memcache的区别分析
1、 Redis和Memcache都是将数据存放在内存中，都是内存数据库。 不过memcache还可用于缓存其他东西，例如图片、视频等等。 2、Redis不仅仅支持简单的k/v类型的数据，同时还提供list，set，hash等数据结构的存储。 3、虚拟内存--Redis当物理内存用完时，可以将一些很久没用到的value 交换到磁盘4、过期策略--memcache在set时就指定，例如set key1 0 0 8,即永不过期。 Redis可以通过例如expire 设定，例如expire name 105、分布式--设定memcache集群，利用magent做一主多从;redis可以做一主多从。 都可以一主一从6、存储数据安全--memcache挂掉后，数据没了；redis可以定期保存到磁盘（持久化）7、灾难恢复--memcache挂掉后，数据不可恢复; redis数据丢失后可以通过aof恢复8、Redis支持数据的备份，即master-slave模式的数据备份。
发表评论