改进的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。……