实际上的MPH：快速紧凑的不可变键值存储
当您需要使用大量数据扩展应用程序时，如何决定存储解决方案？您如何既可以安全地存储大型数据集又可以与之有效交互？这通常会引发关于是否使用SQL或NoSQL的争论。每个都有优点和缺点。
消费者可能不需要每隔几分钟就更新一次。在这种情况下，能够将数据集加载到内存中可以极大地加快访问速度并实现巨大规模。这就是为什么对于Indeed的许多项目，我们将所需数据的完整副本分发给每个使用者，并使SQL或NoSQL辩论变得不必要。为了实现这一点，我们使用基于最小完美哈希函数的新键值存储来管理数据大小。我们已将此商店实现为Java库，名为Instant MPH。
通常，出于两个原因，将数据的完整副本分发给使用者是不切实际的。首先，数据必须大部分是只读的。其次，数据不能太大以至于无法进行分发或处理。
您可以通过实施批更新来克服第一个问题。每天，每小时或什至更频繁地重新分发数据，并且在确保数据仍然有用的同时将其保持为只读状态。但是，如何减小尺寸？事实证明，解决第一个问题的同一批处理更新策略也解决了第二个问题。
生成只读数据集意味着我们提前知道了该数据集的所有密钥。这使我们可以对数据集进行优化以减小其大小。对于哈希表，这种知识使我们能够计算出完美的哈希函数。
完美的哈希函数可将每个元素映射到一个无冲突的独特整数中-从数学上讲，这是一个内射函数。最小完美哈希（mph）函数将n个键映射到n个连续的整数[0，n-1]。通过这种结构，我们可以保证在磁盘上查找单个磁盘，同时又保持表中100％的负载，但是正如我们稍后将演示的那样，它还有更多的优势。
查找此类哈希函数可能很困难。实际上，这篇Wikipedia文章中描述的“生日悖论”告诉我们，即使m比n大几倍，也不可能发生零冲突。但是，最近的进步产生了有效的技术（如本摘要中所述）和高质量的库，用于生成最小的完美哈希。这些技术使我们的方法仅具有很小的缺点就可以成功：产生的哈希函数本身需要每个密钥约2.2位的查找表，因此它不占用恒定的大小。但是，此查找表仅是Bloom筛选器大小的一小部分，对于1亿个条目仅需要约26MB。实际上，与存储的数据大小相比，查找表的大小可以忽略不计。
mph函数为我们提供了从键到[0，n-1]的映射，但是我们仍然需要实现该表。在内存中，我们通常只将数据存储在一个数组中。要将其转换为脱机存储，我们需要使编程语言数组隐式地显示一些内容：内存偏移量。我们的表示形式是一个包含三个文件的目录：
offsets.bin：固定大小的数组，其中ith值是哈希为i的条目在data.bin中的字节偏移量
包含序列化哈希的文件每个密钥大约需要2位，而包含偏移量的文件则需要4个字节。原始序列化键/值对每个键需要46个字节。
这种表示的一个方便之处在于data.bin是可用于迭代的原始数据，与哈希函数无关。另外，我们可以有多个散列函数通过不同的键为同一data.bin编制索引，只要这些键始终是唯一的即可。
这种表示方法的缺点是条目很多。在这种情况下，偏移量的大小可以与数据本身相同甚至更大。举一个极端的例子，如果数据包含从int到半精度浮点的7.5亿个映射，则data.bin需要7.5e8 * 6 =〜4.2G，而offsets.bin需要7.5e8 * 8 =〜5.6G！在此示例中，我们可以利用每个具有固定大小的条目。我们不需要存储偏移量。我们可以直接索引到data.bin中。但是我们也想优化大小可变的情况。
这种高昂的成本特别是在我们处理小条目时出现的。如果条目很大，则通过比较可以忽略偏移量的大小。因为总大小很小，所以我们可以用等级（位计数）数据结构来表示它，它以每个条目的位数而不是字节的顺序排列。对于更多的开销，我们可以在相同的数据结构上恒定时间计算秩的倒数，即选择。为什么这样有用？如果为data.bin中每个条目的起始字节设置了位，则查找第i个条目的偏移量只是在计算select（i）。
结构如下。在这种情况下，我们现在必须按哈希值对data.bin进行排序。
进一步的优化来自我们数据中通常非常规则的结构。例如，要从一个long映射到long列表（使用单个字节进行计数），假设列表的长度，每个单独条目i（包括键和值）的大小可以表示为8 xi + 9是xi。第k个条目的偏移变为∑（8 xi + 9）= 9 k + ∑8 xi = 9 k + 8 x。换句话说，我们只需要存储x即可，它比实际偏移量小得多，并且使用select方法可以节省很多钱。在这种情况下，如果有1000万个条目平均包含列表中的2个元素，则data.bin的大小为10000000 *（9 + 16）=〜250M，但是压缩选择方法仅使用〜2.5M。
我们的实现计算偏移数组和选择方法的大小，然后进行相应选择。
如果我们没有碰撞，并且知道我们要查找的钥匙在桌子上，那么我们不需要验证它。或者，我们也许能够从值或给定值的其他来源验证密钥。最后，如果我们可以接受错误肯定查询的可能性很小，那么我们总是可以使用布隆过滤器来概率性地验证键是否在表中。
我们有一个更好的选择。由于我们已经将哈希值哈希化为原始密钥集中没有冲突的值，因此我们可以存储密钥的k位签名（任何通用哈希的低位都可以）。散列为相同值的不在原始集中的任何密钥将仅以2-k的概率与签名匹配。这比使用布隆过滤器的错误率好得多。
在所有这些情况下，我们都可以完全从表中省略键。当值较小时，键可能占很大一部分，甚至占表的大部分。
要将多个表链接在一起是很常见的做法-一个表的值要么是另一个表，要么包含另一个表的外键。
使用mph函数的另一个好处是它将密钥压缩到紧凑的整数范围。我们可以存储哈希值而不是密钥，对于大多数实际用途，该哈希值将适合4字节整数，而不是8字节长或更大的其他许多外键。这不仅更紧凑，而且读取速度也更快，因为我们不需要为第二次查找重新计算哈希值。
我们很高兴地宣布，我们已将mph代码开源。对于基准测试，我们将其与几种开源替代方案进行比较：
请注意，这些选项没有等效的功能集。 SQLite提供了完整的关系操作，lsm和LevelDB提供了范围查询，所有这三个都是可变的。在这里，我们仅关注这些选项的通用功能。
我们根据生产数据查看两个在概念上相关联的商店的结果。这使我们可以通过上述哈希优化来演示链接，并且还可以在SQLite中实现更自然的表示。第一个存储区是从5000万个64位哈希到一个小的“项”簇的映射，这些项是80位整数，表示为16位基数32字符串。第二个存储是从群集中的每个项目到与其关联的哈希的反向映射。
我们自己的键值存储的一个重要方面是它们通过插件基础结构对任意序列化的使用。因此，为了公平起见，在我们的LSM树和MPH表的大小中，我们既包括了不透明字符串到字符串映射的大小，又包括了两种优化。我们将密钥编码为固定的8字节长值，并将这些值编码为80位整数的短列表。对于SQLite，我们将键编码为整数。
在字符串映射的一般情况下，LevelDB，lsm和mph都具有可比较的大小，并且明显小于其他解决方案。如果我们应用更有效的序列化，则lsm和mph会变得更小，并且mph越来越能够利用大小的规则性成为最小的选择。
在这里，我们仅考虑lsm和mph的最佳序列化。对于mph，我们还显示了具有上述优化功能的大小，首先不存储键，然后通过完美的哈希值链接到上表。对于SQLite，我们在两个列上建立索引时都包含了大小，这使我们可以完全删除上一个表。在这种情况下，SQLite索引小于discodb和TinyCDB的组合大小，并且与LevelDB相当。但是，mph仍然比所有内容都小，并且在理想情况下，应用所有优化后，mph实际上要小一个数量级。
正如人们可能期望的那样，基于散列的解决方案往往会更快，因为它们需要的寻道次数更少。 Mph总体上是最快的，可以在2毫秒内完成哈希到项目的操作，在3毫秒内完成项目到哈希的操作。
写入性能显示lsm和mph具有最强的性能。 由于数据损坏，此时TinyCDB被排除在外-设计上有固定的4GB存储限制，但是即使是3GB，我们也无法检索到30％的密钥。 如果您已经将键值存储库运送到服务器，则我们的mph表可能能够提供较小的尺寸和更快的读取速度。 如果您尚未这样做，可以考虑将其作为集中式数据库的替代方案。 使用紧凑的表示形式，您可以在同一空间中存储更多数据，或者减小以前认为过大的数据大小。