value数据存储设计方案.pdfVIP

第32卷第 4期 东 北 电 力 大 学 学 报 Vo1．32．No．4 2012年 8月 JournalOfNortheastDianiiUniversity Aug．，2012 文章编号：1005—2992(2012)04—0026—04 改进的 key／value数据存储设计方案 何 文 (东北电力大学 信息工程学院，吉林 吉林 132012) 摘 要：针对现有key／value缓存系统海量数据的访问速度慢，满足不了应用的需求，提出一种改进 的key／value数据存储方案并将其应用于缓存系统中。通过小数据量存储方案的提出，及对 rehash算 法 、rehash权重因子W的改进，十分有效地解决了hash冲突、rehash迁移数据导致的系统变慢问题，加快 了缓存系统的速度 ，提高了缓存系统的命中率。 关 键 词 ：key／value数据结构；rehash；hash算法；hashcode；hash桶；缓存系统 中图分类号 ：TP391 文献标识码：A 缓存系统的应用是网站架构的核心，因此，要提高网站的性能和稳定性，必须选择优秀的缓存系统。 现在的缓存系统大多以key／value存储数据，比较典型的缓存系统有：Memached、Oscache、Ehcache、redis 等。其中Memached因其简单高效、稳定性好等特点，被广泛应用到互联网缓存系统架构中。但是 Memached在key／value存储方案中存在数据冲突和rehash导致数据迁移两大问题，将其应用到互联网 缓存系统架构中也间接导致了网站访问速度慢和系统崩溃等问题。本文所提的改进缓存系统有效地弥 补了如今web缓存系统本身存在海量数据速度访 问慢，满足不了应用需求的不足…。实验表明，改进 的缓存系统提高了访问速度。 1 key／value存储模型 key／value典型实现的数据结构一般为数组链表，利用 hash算法均匀分布在hash桶中即存放在数 组中，而hash冲突解决方法是开放链表法。 1．1 数组链表数据结构 图1key／value存储结构：先通过 hashcode找到 数组的某一个位置 (通过 hash算法得出hashcode)， 然后插入链表的第一个位置；数据的查找过程：通过 hashcode找到数组的某一个元素，然后通过key的相 等方法在链表中找到key对应的value元素。 1．2 解决冲突的方法 缓存系统解决冲突的方法是开放链表法，将所 有为同义词的结点链接在同一个单链表中。 图1key／value存储结构 优点：拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短； 由于拉链法中各链表上的结点空间是动态申请的，故它更适合于无法确定表长的情况；开放链表法为了 减少冲突，故而引入装填因子 ，拉链法中 值可取 I 0。 缺点：指针需要额外的空间，故当结点规模较小时，开放链表法较为浪费存储空间。 收稿 日期：2011—11—14 作者简介：何 文(1986一)，男，湖南省岳阳市人，东北电力大学信息工程学院在读研究生，主要研究方向：海量数据存储 28 东北电力大学学报 第 32卷 它实际上是一个指针数组，数组的个数 由size 发生rehsh期间 决定，每个元素 (bucket)指 向一个 dictEntry的单链 表来解决hash冲突。查询某个 key，需要先hash，定 建立两倍的原因是 新建一个 比原 防止数据迁移时候， 来两倍的数组 位到数组某一个元素然后再通过链表遍历找到key 数据再次遇到冲突； 链表