介绍一种服务器缓存结构 --- 多级 Hash

       现在的服务器网络数据收发与存储没有不做缓存的。如果公司的重要数据存储在磁盘中,且数据接近静态但每天局有部更新而且也有大量访问,不做缓存不能发挥机器的高性能。

       一般地,公司内部都有集中固定型号的服务器,每种都有其性能极限,一般包括但不限于CPU计算能力、网卡收发包能力、内存容量以及磁盘容量和他的读写速度。多级hash即与内存容量有关。假设一台dell服务器内存是8G,如果用多级hash做缓存,那么就可以考虑给缓存的容量是6G,即一般内存容量的3 / 4 或者 2 / 3考虑用作缓存的极大容量。某种服务器为某种业务服务,简单的认为业务的值是key-value形式,一般地,key肯定有固定大小Ksize,value最大值也有极限值Vsize_max。

        由上面的一段文字,如果把多级hash作为服务器的缓存,你应该明白这个缓存有两个特点:第一,缓存有极限容量;第二,每个key-value元素有固定大小(Ksize + Vsize_max)。

       如果不考虑多级hash,只考虑上面两个特点,数据结构中最简单的hash表就可以胜任,不是么?不考虑在大内存中CPU对不懂缓存单元的寻址并把数据load到CPU cache中的时间差异(局部性原理),即认为在任何时刻CPU对缓存所有单元的访问速度是一个常数,hash表确实是极为完美的。

      一个简单的数组型hash表确实完美,但是hash表天生缺陷之一就是存储位置冲突。不考虑不同的值计算出同一个key值,我们认为不同的值有不同的key。若一个hash表的元素都存在其数组arr[hash.size]中,在简单的hash表中必有函数计算一个元素的存储位置时候,其简单的计算公式如key / hash.size。此时由于hash.size大小固定,必然存在若干个元素计算出同样的存储位置。不同的人针对这个难题有不同的解决方法。

    我的lisk中就有两种hash结构可以用来解决这个问题,一种是可伸缩的hashtable(以下称之为lisk_hashtable),一种就是多级hash(以下称之为lisk_mul_hash)。lisk_hashtable的特点以后予以介绍,现在先提下它的缺点。在内存允许的情况下lisk_hashtable可以自动扩大或缩小它自身的大小,它的极限大小的计算是不方便的。若极限大小不能方便计算出来存在的情况下,它就不方便作为服务器对外服务的缓存。而结构简单的缓存结构也方便别人维护。额外话题,服务器的特点第一是稳定,第二才是性能,一个性能很好的服务器但是她的服务时好时坏,用户会经常骂娘的,它能服务谁呢?而lisk_mul_hash是不考虑伸缩性的,你可以认为这是它的缺点,但是在服务器缓存极限容量存在的情况下,可伸缩性又有什么用?

    多级hash就能够实现上面提到的服务器缓存的两个特性。多级hash可提供插入、查找和删除操作。

    简单地,我们可以认为多级hash就是一个多维数组,行数一般在10到100之间,列数则不固定,元素大小固定。
    一般网上有一些多级hash实现,你会发现它们的关键实现就是一个多维数组。假若其关键结构是arr[3][10000],若一个元素的key是99995554,则寻找插入过程如下:
1 在arr[0]的存储位置是99995554 / 10000 = 5554;
      2 如果arr[0]的5554位置已经被占用了,则使用arr[1]的5554位置;
3 如果arr[1]的5554位置也被占用,则使用使用arr[2]的5554位置。
    上面每行都能存储10000个元素,同一个元素如果计算存储位置,在每一个行可以计算出同样的计算位置。考虑到离散数学中同余原理,每行最大元素数目不同且数字取质数为宜,每行的数字可依次递减。譬如第一行取比10000稍小的质数9973,第二行大小取值9969,第三行取值9949。
    所以若再次计算元素存储位置,则计算过程就稍微改变。计算过程如下:
    1 在arr[0]的存储位置是99995554 % 9973;
    2 如果arr[0]的存储位置99995554 % 9969 被占用,则使用arr[1]的99995554 %  9969位置;
    3 如果同样也被占用,则使用使用arr[2]的99995554 % 9949位置。
    考虑一个问题,上面计算key为99995554的元素的存储位置时, 如果三行的三个位置都被占用了,那么它将被存储到那里呢?这就是多级hash的一个特点,不保证所有元素都被存储下来。如果多级hash设计的好,只有很少量的元素找不到存储位置,他们被称为奇异值,这部分你可以另考虑别的方法来解决。譬如你就直接把他们存到磁盘上,文件分为索引文件和数据文件,分别存储key和value,并把索引文件通过linux的mmap接口映射到内存中来,以方便快速查找。
     即使多级hash中已经插不进新的元素,多级hash内部也肯定还有没有存储元素的位置。
     或者呢?我们可以接受多层hash不能饱和地存下所有元素的特点,其利用率达到85%就可以了,若达到90%就可以认为这个多级hash就可以被缓存不可用了。你需要升级服务器了。
    
    多级hash行数越多,其空间利用率越高,然查找速度便逐渐减慢。反之,行数越少,则多级hash查找速度越快,然空间利用率低下。所以行数应该被控制在50行以内,一般在20至35行之间为宜。


    lisk中多级hash也是一个多维数组,每行数目可以不同。如第一行实际存储数目极限是9973,则只申请9973个位置,可以不用申请10000个位置,以减少元素浪费。

    lisk中多级hash的每行列数目是递增的,lisk/exam/mul_hash_test.c利用随机数测试,这个多级hash几乎可以把所有元素存下来,即利用率几乎可达到100%。但它没有考虑如何存储奇异值。

 

      其实,关于缓存还有一些额外的话题。不管缓存的内存区是通过共享内存还是其他的os接口获得的,其中少被访问的数据几乎可能将被os swap out到虚拟内存中,一旦有访问者要访问这个数据,os需要先将数据swap in到内存中,然后再返回给访问者。如果平均访问响应时间是100ms,那么对这个数据的相应就可能在1s至2s之间。如果你认为这是不可接受的(其实我也这么认为),就可以通过mprotect接口禁止缓存中的数据被swap out。

        另外,如果银行等部门用C设计缓存时候,其对缓存中数据的可靠性是非常高的,即宁愿访问响应时间稍长一点也不会接受不可靠的数据。不考虑多线程情况,建议对共享内存数据的读取都使用volatile关键字。

        2月份曾经简要的谢过一篇多级hash的blog,里面介绍了一个windows上用vs2012编写的程序,可查看blog http://blog.csdn.net/menggucaoyuan/article/details/8617117。 

        如果对lisk感兴趣,请点击博客链接 http://blog.csdn.net/menggucaoyuan/article/details/8879898。 最近正在把它改成多线程版本,估计得半个月时间。        

有关编译器优化的更完整信息,请参阅优化通知