做网站大概价格,网站备案填写,手机人才网,工业设计之父对于REDIS来讲 其实就是一个字典结构#xff0c;key ----value 就是一个典型的字典结构 【当然 对于vaule来讲的话#xff0c;有不同的内存组织结构 这是后话】 试想一个这样的存储场景#xff1a; key:city value:beijing 如果有若干个这样… 对于REDIS来讲 其实就是一个字典结构key ----value 就是一个典型的字典结构 【当然 对于vaule来讲的话有不同的内存组织结构 这是后话】 试想一个这样的存储场景 key:city value:beijing 如果有若干个这样的键值对你该怎么去存储它们呢 要保证写入和查询速度非常理想~ 抛开redis不说如果你想要存储 快速查找的话 Hash算法是最快的理想的哈希函数可以带来O(1)的查找速度你都这样想那么redis也的确采用这种方法来做~ 但是HASH算法有2个致命的弱点1填充因子不能太满 2不好的HASH算法可能会导致一个冲突率非常高。 填充因子不能太满 这个理论上一般为0.5左右 过高 就是哈希槽都被塞满了 即使在好的哈希分布算法 也无法避免key冲突。 不好的哈希分布算法 丢到第一个因素来讲 如果一个不好的哈希分布算法会导致了key分布不均匀也就是通过哈希函数计算出来的哈希槽都是落在了一个桶里这样的哈希分布算法是最不理想的最理想的情况下是 保证每个key都落在不同的哈希槽里【哈希槽key】 实际存储的哈希存储设计 1一般来讲哈希分布函数确定后可调控的因子就是这个填充因子 如果填充因子大于你卡的某个阈值那么你就要做哈希结构迁移工作迁移到一个更大的哈希槽中。而对用同用的这种哈希分布 函数有许多人用各种数学方法计算过这里也没有深入研究这个分布函数倒是在这个填充因子上面卡的阈值是需要仔细思考。 2 哈希槽迁移 哈希槽在迁移的过程中无论是单线程环境还是多线程环境都会造成一个短暂的停止服务过程。这个对生产环境会造成非常短暂的影响 我个人认为在服务器 特别存储服务器过程中本来就是面向大量高并发存储应该可以把哈希槽设置的更加大一些这样尽可能避免哈希槽的一个迁移。 REDIS哈希存储设计 前面说到的一些场景是一些哈希存储引擎都会面临到的问题REDIS的解决方面如下 1代码层面 我觉得REDIS的代码开发者写代码风格真的是太棒了 封装性易看性都是很值得学习的 一步一步的看看 用C写的redis但是里面有很多STL的那种设计理念 迭代器 动态内存管理 等 如果你写一个哈希存储最基本的几个子数据结构是必须的 每个基本的元素 struct DicElement{/* data */void* key;void* value;struct DicElement *next;}; 哈希槽 struct DicElement **HASHTABLE[HASHSOLT]; 这是redis的真实源码中间用了一个union联合体 要么是指针要么就是一个64位的数字。 typedef struct dictht { dictEntry **table; unsigned long size; unsigned long sizemask; unsigned long used; } dictht; dictht就是一个完整的哈希槽这里面记录了table有多少个哈希槽被用了【used】 已经哈希槽有多少个 【size】 一般对于静态的哈希存储结构来讲 上面2个数据结构就可以了但是redis有一个特性就是支持扩容动态扩容和stl的vector的策略是相似的 当达到临界阈值时就会增加的到一倍。 真正的dic结果如下 typedef struct dict { //这里封装了dic的函数指针结构体 典型的C写法 如果是c 就是一个类 更易读 dictType *type; void *privdata; //2个字典 一个空 一个是需要写入的 dictht ht[2]; //如果重新哈希 就是扩容 这个标记位就会改写 int rehashidx; int iterators; } dict; rehashidx 表示正在索引的索引值字典正在赋值的索引号。 题外话如果用C来写 代码片段更加容易看懂。 字典迭代器讨论 typedef struct dictIterator {// 正在迭代的字典 dict *d; int table, // 是哈希表1还是2 index, // 迭代那个哈希槽 safe; dictEntry *entry, // 现在哈希结点*nextEntry; // 后面一个} dictIterator; 这里的迭代器提出了safe字段迭代器的安全 迭代器安全REDIS不是一次性全部迁移过来的而是根据时间片来迁移这样的话也就是如果没有迁移完的话如果有插入迭代器或者删除迭代器存在的话可能会导致漏掉或者多复制现象存在。 这样的话 还是采用最好的战术模式记录操作这个dic的迭代器数量只有当全部是安全迭代器时才可以进行迁移工作。 在生产环境下如果是HASHTABLE是多线程的呢 多个线程进行读和写可控制性将会变得非常不可控啊~ 而且如果是多线程一致性怎么能够得到保证呢~ 在每次迁移完 ht[i]会释放内存 然后制空。 没迁移完之前就会查看2个字典桶。 关于REDIS哈希槽扩容设计 1 每次进行add dellookfor操作时都会做执行dicRehashStep函数一次在调用dictRehash(d,1)一次这里的一就是执行rehashidex那个下一个不为null的值一次也就是把一个槽给迁移到ht[1]中只执行一次 也是为了不会让redis出现太长时间的暂停服务而考虑的一种设计。 但是这里的前提就是安全iterator迭代器的数量为0 也就是不包含增 删 改这3个操作的iterator~! 如果含有增删改那么有可能会出现漏掉entry的情况。 2这里是提示用多少毫秒作为一个间隔来做rehash操作也就是把ht[0]迁移到ht[1]上每次的base值是100时间是由服务器来控制,这是第2种迁移方式这种迁移方式每次迁移的槽多相对来讲所需要的时间更多所以ms间隔是需要仔细评估如果没有弄好会造成一个时间上的空档。 int dictRehashMilliseconds(dict *d, int ms) {long long start timeInMilliseconds();int rehashes 0;while(dictRehash(d,100)) { rehashes 100;if (timeInMilliseconds()-start ms) break; }return rehashes;} 转载于:https://www.cnblogs.com/sfwtoms/p/3946554.html
