优化 NoSql 键值存储中的重复值
Optimize duplicate values in NoSql key-value storage
我正在构建一个地图切片存储，需要存储 15 亿 ~3KB 的 blob。其中超过 95% 是重复的。是否有 NoSQL 存储引擎可以避免存储相同的值？
我当然可以实现双重取消引用，例如键->散列->值。如果哈希是 MD5，则 16 字节哈希仅用于哈希就将占用 24GB，再加上每个项目的开销，这可能更多。还有更高效的吗？
谢谢！
双重取消引用是可行的方法 - 如果不存储重复数据，您将节省 4-5TB 的数据，因此存储 24GB 的哈希集是值得的。此外，您只需计算插入和更新的哈希函数，而不是查找或删除。
为了降低查找时双重取消引用的成本，您可以使用内存中的缓存来补充磁盘上的键值数据库，例如Redis - 您可以缓存经常访问的 key->hash 对以避免在主数据库上进行两次查找，或者您可以直接将整个 key->hash->blob 结构存储在缓存中（前者要简单得多实施是因为您不需要从主数据库复制双重取消引用，而如果只有一小部分 blob 处于活动状态，后者更有意义。
您可以使用 simpler/smaller 散列 - probability of a hash collision is 1 - e^(-k^2 / 2N) where k is the number of values being hashed and N is the size of the hash, so a good 64-bit hash has about a 12% chance of having a collision and a good 128-bit hash has an infinitesimal chance of having a collision. MurmurHash has 64 and 128-bit versions so you can experiment between the two, and it's faster than MD5 largely owing to MD5 being a cryptographic hash function whereas Murmur doesn't have the added expense/complexity of being cryptographically secure (I'm assuming that you're not concerned about anybody attempting to intentionally generate hash collisions or anything like that). Some key-value stores also make it relatively easy to make your design collision-tolerant, for example you could store the hash in a Riak Map 带有一个标志，指示该散列值是否存在任何冲突 - 如果为假，则只需 return blob，否则退回到选项 2（例如，索引的 blob 成为具有散列冲突 zipped/tarred 的两个 blob 以及一个 CSV，其中的键对应于哪个 blob；即使使用 64 位散列，此代码路径也会不会经常使用，因此实现简单性可能胜过性能）；问题是减少的 memory/hashing 开销是否弥补了碰撞容忍的复杂性。
我正在构建一个地图切片存储，需要存储 15 亿 ~3KB 的 blob。其中超过 95% 是重复的。是否有 NoSQL 存储引擎可以避免存储相同的值？
我当然可以实现双重取消引用，例如键->散列->值。如果哈希是 MD5，则 16 字节哈希仅用于哈希就将占用 24GB，再加上每个项目的开销，这可能更多。还有更高效的吗？
谢谢！
双重取消引用是可行的方法 - 如果不存储重复数据，您将节省 4-5TB 的数据，因此存储 24GB 的哈希集是值得的。此外，您只需计算插入和更新的哈希函数，而不是查找或删除。
为了降低查找时双重取消引用的成本，您可以使用内存中的缓存来补充磁盘上的键值数据库，例如Redis - 您可以缓存经常访问的 key->hash 对以避免在主数据库上进行两次查找，或者您可以直接将整个 key->hash->blob 结构存储在缓存中（前者要简单得多实施是因为您不需要从主数据库复制双重取消引用，而如果只有一小部分 blob 处于活动状态，后者更有意义。
您可以使用 simpler/smaller 散列 - probability of a hash collision is 1 - e^(-k^2 / 2N) where k is the number of values being hashed and N is the size of the hash, so a good 64-bit hash has about a 12% chance of having a collision and a good 128-bit hash has an infinitesimal chance of having a collision. MurmurHash has 64 and 128-bit versions so you can experiment between the two, and it's faster than MD5 largely owing to MD5 being a cryptographic hash function whereas Murmur doesn't have the added expense/complexity of being cryptographically secure (I'm assuming that you're not concerned about anybody attempting to intentionally generate hash collisions or anything like that). Some key-value stores also make it relatively easy to make your design collision-tolerant, for example you could store the hash in a Riak Map 带有一个标志，指示该散列值是否存在任何冲突 - 如果为假，则只需 return blob，否则退回到选项 2（例如，索引的 blob 成为具有散列冲突 zipped/tarred 的两个 blob 以及一个 CSV，其中的键对应于哪个 blob；即使使用 64 位散列，此代码路径也会不会经常使用，因此实现简单性可能胜过性能）；问题是减少的 memory/hashing 开销是否弥补了碰撞容忍的复杂性。