我在以前的博客《sdk的windows版本》点击打开链接 中稍微的介绍了一些多级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关键字。