问题标签 [consistent-hashing]

散列和索引都用于在某些预定义公式上对数据进行分区。但我无法理解两者之间的关键区别。

与散列一样，我们根据一些键值对来划分数据，类似地，在索引中，我们也在一些预定义的值上划分数据。

谁能帮我弄清楚散列和索引之间的区别，以及如何决定是使用散列还是索引。

网上有很多关于一致性哈希的资料，以及可用多种语言的实现。该主题的 Wikipedia 条目引用了另一个具有相同目标的算法：

集合散列

这个算法看起来更简单，并且不需要在环周围添加副本/虚拟来处理不均匀的加载问题。正如文章所提到的，它似乎在 O(n) 中运行，这对于大 n 来说是一个问题，但参考了一篇论文，指出它可以被构造为在 O(log n) 中运行。

对于在这方面有经验的人，我的问题是，为什么要选择一致的哈希而不是 HRW，或者相反？是否存在其中一种解决方案是更好选择的用例？

非常感谢。

我一整天都在尝试用 PHP 理解 Memcache 并编写代码，但我在某些方面感到困惑。我浏览了很多文章，几乎所有与此相关的 SO 问题，但找不到确切的答案。

1) 在 PHP 中创建一致散列密钥的代码是什么？我必须安装哪些库以及我真正需要做什么？有什么好文章可以看吗？

2）假设，我已经成功存储了一个一致的散列密钥，现在如果我的任何服务器关闭或添加了一个新服务器，即使我使用的是一致的散列密钥等也会有什么不同吗？

3)如果在http://ru.php.net/manual/en/memcached.addserver.php中所述的一致哈希的情况下，使用 Memcached::addServers() 而不是 Memcached::addServer() 会产生任何影响不是那是什么意思？

4) 使用上述代码是否足以进行一致哈希，然后添加/删除服务器不会对密钥产生任何影响？

5) 什么是 Ketama 图书馆？如果 Memcached::DISTRIBUTION_CONSISTENT 可以更好地工作，为什么要使用它？以下http://www.last.fm/user/RJ/journal/2007/04/10/rz_libketama_-_a_consistent_hashing_algo_for_memcache_clients

6) 我是否必须以某种方式对我的密钥进行哈希处理，或者只提供我的密钥并让 Memcached 处理其余的？

请各位，我需要你们的真正支持，以便尽快了解并实施我的生产环境。你的回答会让我明白我应该更好地编码什么。

我已经阅读了几篇解释一致性哈希背后的理论的文章。但是它们中的大多数都没有提供有关如何处理添加/删除节点的详细信息。我知道如果它用于像memcached这样的缓存层，我们可能不需要做任何事情，但如果它用于分布式存储，将一些数据移动到正确的节点是非常关键的。当我们需要添加/删除一个节点时到底发生了什么？

其他几个问题是：

1. 处理不同大小的服务器的最佳方法是什么
2. 如何一次添加和删除多台机器
3. 如何应对复制和容错

希望有人能给我指出一篇解释这些的文章。

我有许多密钥需要跨多台机器存储数据。我已经使用 Ketama 一致的散列库来完成这项工作，但是对于每个密钥，我希望 2 台机器来存储该密钥的数据，一个主要的和一个辅助的。

我可以想象逆时针而不是顺时针（例如floorEntry而不是ceilingEntry）来查找辅助机器，但这需要在我没有编写的库中进行更改。

有没有办法在不修改 lib 的情况下实现这一点？一个想法是将散列围绕环旋转 180“度”，但不确定如何做到这一点。

奖励/可选：除了给定密钥的主要和次要机器外，如何找到第三台机器？

Cassandra 是否适合这种情况？

1. 只有一个表（键/值）。
2. 超多行，例如 10 万亿行。
3. 拥有 1000 台服务器的集群
4. 50%:50% 范围/列表和键获取。（范围/列表的TPS会随着它的增长而增加）

我知道 Cassandra 可以很好地扩展用于繁重的写入和读取查询，因为密钥是由哈希环自然分布的。而且我也知道在分区上会付出最少的努力。

但从他们的白皮书中，我的见解是它只会扩大直接匹配键的查询。并且并没有真正扩大范围/列表查询，因为键索引将像任何其他键一样存储在几个服务器中。而且，单个范围查询也有可能会访问集群中的每台服务器以获取密钥。如果是这种情况，随着我添加更多服务器，范围查询会变慢。

我想知道我的理解是否正确，还想知道范围查询是否随着我添加更多服务器而与键一起线性扩展。

我试图找出我在未来像谷歌规模一样成长时所面临的真正挑战。

我已阅读文章： http: //n00tc0d3r.blogspot.com/ 关于一致散列的想法，但我对多台机器上的方法感到困惑。

基本流程是：

插入

1. 将输入的长 url 散列为单个整数；
2. 在环上找到一个服务器，并将密钥--longUrl存储在服务器上；
3. 使用基本转换（从 10-base 到 62-base）计算缩短 url 并将其返回给用户。（这一步如何工作？在单机中，有一个自动增加的 id 来计算缩短 url，但是在多台机器上计算缩短 url 的值是多少？没有自动增加的 id。）

取回

1. 使用基转换（从 62 基到 10 基）将缩短 url 转换回密钥；
2. 找到包含该密钥的服务器并返回 longUrl。（我们如何才能找到包含密钥的服务器？）

我正在尝试实现一个最小的完美散列函数，实现这一目标的主要方法之一是能够获取已知的密钥宇宙并将它们拆分成相当均匀的小尺寸桶（在合理范围内越小越好）。问题是我不知道如何分配这些字节数组。整个密钥集在算法开始时可用。有人对我能做什么有任何建议吗？

谢谢！

对于分片，我需要好的哈希算法。我需要为 0-2^31 范围内的字符串生成哈希整数值。这可能吗 ？

以下答案给出了一种从 md5 算法生成整数的方法。

在 PostgresSQL 中将字符串散列为数值

但是有没有办法在一个范围内生成这个值？

假设我有一个Orders具有自动递增 id 的表，例如 1、2、3、4...，并且它们当前被查询为http://www.example.com/order?id= {1,2,3 ..}

现在，我想将主键 [1, 2, 3, ..] 散列到另一个称为订单号的数字中，以便我们的客户可以在他们的请求中引用它们，例如

我想要以下内容：

• 无法通过查看自动增量 ID 来猜测我每天创建了多少订单
• 不需要额外的数据库查找，完全由 PHP 哈希（和预定义的盐）
• 无碰撞

可能吗？