改进的key/value数据存储设计方案

何 文

(东北电力大学信息工程学院，吉林吉林132012)

缓存系统的应用是网站架构的核心，因此，要提高网站的性能和稳定性，必须选择优秀的缓存系统。现在的缓存系统大多以key/value存储数据，比较典型的缓存系统有:Memached、Oscache、Ehcache、redis等。其中Memached因其简单高效、稳定性好等特点，被广泛应用到互联网缓存系统架构中。但是Memached在key/value存储方案中存在数据冲突和rehash导致数据迁移两大问题，将其应用到互联网缓存系统架构中也间接导致了网站访问速度慢和系统崩溃等问题。本文所提的改进缓存系统有效地弥补了如今web缓存系统本身存在海量数据速度访问慢，满足不了应用需求的不足［1］。实验表明，改进的缓存系统提高了访问速度。

1 key/value存储模型

key/value典型实现的数据结构一般为数组链表，利用hash算法均匀分布在hash桶中即存放在数组中，而hash冲突解决方法是开放链表法。

1.1 数组链表数据结构

图1 key/value存储结构:先通过hashcode找到数组的某一个位置(通过hash算法得出hashcode)，然后插入链表的第一个位置;数据的查找过程:通过hashcode找到数组的某一个元素，然后通过key的相等方法在链表中找到key对应的value元素。

1.2 解决冲突的方法

缓存系统解决冲突的方法是开放链表法，将所有为同义词的结点链接在同一个单链表中。

优点:拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短;由于拉链法中各链表上的结点空间是动态申请的，故它更适合于无法确定表长的情况;开放链表法为了减少冲突，故而引入装填因子α，拉链法中α值可取1＞α＞0。

缺点:指针需要额外的空间，故当结点规模较小时，开放链表法较为浪费存储空间。

图1 key/value存储结构

2 key/value存储方案的改进

key/value存储方案在软件工程中有大量的应用，尤其是在缓存系统中的应用。由于添加的元素越来越多的时候key/value存储发生碰撞的几率越来越大，本节给出一种改进的存储方案，主要包括权重因子、小数据量的存储方案、改进rehash三方面内容，最后给出测试结果。

2.1 权重因子的改进

当数组中的元素越来越多的时候，添加一个元素发生碰撞的几率也就越来越高。因为数组的长度是固定的，所以为了提高查询的效率，必须在数组里面留出一些空闲的位置，即权重因子α(0＜α＜1)，也就是权重因子设置的过大发生的碰撞的概率就会越大而设置过小存储空间会十分的浪费，由于key/value存储方案设计没有专门的接口来动态的调整权重因子，所以在缓存应用中要根据适当的权重因子来满足需求，进而需要给用户提供相应的接口来调整权重因子的大小［2］。

2.2 小数据量存储方案

该方案是为了在缓存系统中更大的节约内存提出来的一种折中方案，该设计方案只适用于当存放hash桶中元素比较少时(存放少于254个元素)适用。本文引入的数据结构zipmap，一个元素(key/value)在zipmap中有5部分组成，如图2 zipmap存储结构所示:

len:表示key/value字符串的长度，如果字符串的长度小于254使用一个字节保存，否则就使用5个字节来保存;free:当修改已有的key1对应的value值且新的value值小于已有value值时不会对空间进行回收，只有当free为4即空闲的字节数为4个字节时才会回收空闲的空间。这样设计的目的是为了避免大量的修改key中value值时，造成不必要的元素移动从而影响性能。

2.3 rehash 改进

由于数组里面的元素装载过多，hash算法就会发生碰撞，所以数组里面的元素达到了权重因子的比率就要对数组扩容，最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置，并放进新的数组里。这个也是在当今key/value存储处理的一个瓶颈，如何让它平缓的滑动元素，所以就引入了一个对rehash改进的思想。本文使用了两个数组，目的是为了在rehash的时候可以平滑地迁移新的数组里，而对比现有的key/value存储方案将全部数据迁移到新的数组中，此操作是key/value存储的瓶颈［3］。

图2 zipmap存储结构

下文提出一个rehash改进事方案来解决key/value数据迁移问题，如图3 rehash的数据结构。

大的长方形表示dictht数据结构，小的长方形表示dicth数据结构即数组链表，dictht的数据结构由size、dictEntry、sizemask、used 组成，dictht的数据结构是由 rehashidx、两个 dicth 组成。

图4对添加一个key/value元素流程图的分析:

图3 rehash数据结构

图4 添加元素流程图

它实际上是一个指针数组，数组的个数由size决定，每个元素(bucket)指向一个dictEntry的单链表来解决hash冲突。查询某个key，需要先hash，定位到数组某一个元素然后再通过链表遍历找到key对应的value值。图5是针对rehash的流程图:

第二个 hash桶就是为了rehash而产生，新的hash桶的大小是旧hash桶的两倍，每一次元素的添加和元素的查找都会进行一次rehash:旧hash桶的每个bucket会rehash加入到新的hash桶里。rehashidx是旧的hash桶需要rehash即迁移到新的hash桶中bucket的索引，从0开始直到旧的hash桶的used等于0。

rehash期间:由于新的hash桶是旧hash桶大小的2倍，每次添加元素时候都会rehash一次，不会出现新的hash桶满了后而旧的hash桶还有数据。元素的查询会先查旧的hash桶再查询新的hash桶，在rehash的过程中，不会出现再次扩容［4］。

2.4 改进key/value存储方案的测试

图5 rehash的流程图

本文对改进的key/value存储进行了测试，测试环境:Windows XP2000、1G内存。

表1 测试插入数据结果对比

由表1可知，当插入元素个数较少时，改进key/value消耗时间稍长，但是当插入过多的元素时，改进key/value消耗的时间明显比未改进key/value耗时短。当插入80 000个元素时，未改进key/value存储耗时大约是改进key/value存储的3倍，从而验证了大数量添加的时候数据平滑的移动。

表2 测试权重因子结果对比

由表2可知，不同的权重因子耗时是不一样，进而得出需要一个合适的权重因子提高存储效率，表中得出的结论权重因子0.75存储速度耗时最少。

表3 小数据量方案存储和未改进的key/value存储对比结果

表3可知，小的数据量对于改进和未改进的key/value存储，存储的速度没有变化，但是小数据量存储方案节约内存。

3 结 论

key/value存储是缓存系统的核心。由于缓存系统应用在很多互联网公司，优秀健壮的缓存系统已成为研究热点之一。本文在标准key/value存储方案基础上提出了一种改进的key/value存储，通过对测试数据分析，表明改进的key/value存储速度明显加快且，对于小数据量节约内存，为公司成本减少开销。

［1］乐立鸾，李明.Web应用系统性能优化［J］.科技信息，2007，13(22):294- 295.

［2］张柏礼，吕建华，姚蓓等.Web代理服务器缓存置换算法研究［J］.计算机科学与探索，2010，4(11):112-114.

［3］吴继楠.浅论计算贡缓存工作机制［J］，科技信息，2007，27(6):650-652.

［4］石磊，叶海琴，卫琳等.Web缓存命中率与字节命中率关系［J］.计算机工程，2007，9(18):84-86.