1

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

基本流程是：

插入

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

取回

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

1 回答 1

1

关于作者的意图，我在该页面上没有看到任何明确的答案。我认为这基本上是对读者的练习。这里有一些想法：

  1. 按照描述实现它，使用哈希表样式的冲突解决方案。也就是说，在创建 URL 时，如果它已经匹配了某些内容，请以某种方式处理它。重新散列或算术变换（例如，加 1）都是可能的。天真地，这意味着理论上最坏的情况是必须访问服务器 n 次以试图找到可用的密钥。

有很多方法可以采用这个基本概念并使其更智能，例如，只需在同一服务器上搜索另一个可用密钥，例如，通过迭代重新散列，直到找到服务器上的一个。

  1. 允许服务器相互交谈，并在自动增量 ID 上进行协调。

  2. 这可能不是一个很好的解决方案，但它可能在某些情况下工作得很好：给每个服务器（或一组服务器）单独的命名空间，例如，前 16 位选择一个服务器。创建时，随机选择一个。然后，您只需要弄清楚您希望该名称空间如何映射。命名空间只对允许谁创建什么 ID 很重要，所以如果你想稍后添加节点或重新平衡，这没什么大不了的。

让我知道您是否需要更多详细信息。我认为这个有很多方法可以走。令人讨厌的是作者没有详细说明这一点；我对这类算法的经验是，冲突解决和类似问题往往是分布式系统实际实现的核心。

于 2015-01-15T06:00:54.973 回答