我有许多密钥需要跨多台机器存储数据。我已经使用 Ketama 一致的散列库来完成这项工作,但是对于每个密钥,我希望 2 台机器来存储该密钥的数据,一个主要的和一个辅助的。
我可以想象逆时针而不是顺时针(例如floorEntry而不是ceilingEntry)来查找辅助机器,但这需要在我没有编写的库中进行更改。
有没有办法在不修改 lib 的情况下实现这一点?一个想法是将散列围绕环旋转 180“度”,但不确定如何做到这一点。
奖励/可选:除了给定密钥的主要和次要机器外,如何找到第三台机器?
我有许多密钥需要跨多台机器存储数据。我已经使用 Ketama 一致的散列库来完成这项工作,但是对于每个密钥,我希望 2 台机器来存储该密钥的数据,一个主要的和一个辅助的。
我可以想象逆时针而不是顺时针(例如floorEntry而不是ceilingEntry)来查找辅助机器,但这需要在我没有编写的库中进行更改。
有没有办法在不修改 lib 的情况下实现这一点?一个想法是将散列围绕环旋转 180“度”,但不确定如何做到这一点。
奖励/可选:除了给定密钥的主要和次要机器外,如何找到第三台机器?
从一篇关于分布式密钥存储的论文The PRO key-value store 中找到了一个简单的解决方案。
当存储键值对时,从哈希值顺时针方向(大于或等于)的下一个服务器是主节点,而下一个不同的节点(后继节点)是辅助节点。
我通过保留主要->次要节点的索引来找出“下一个”节点。对备份节点的支持就像以类似方式n
构建地图一样简单。Node->List[Node]
在 Scala 中,使用 Twitter 的KetamaDistributor可能如下所示:
import Partitioner._
case class Partition(page: String, primary: String, secondary: String)
class Partitioner(pagesIds: Seq[String], nodes: SortedSet[String]) {
val ketamaNodes = nodes.map { host => KetamaNode(host, defaultNodeWeight, host) }
val ketamaDistributor = new KetamaDistributor(ketamaNodes, numReps)
// Build a map of primary->secondary nodes
val nodeIndex: Map[String, String] = nodes.sliding(2).foldLeft(Map[String, String]()) {
case (acc, Vector(x,y)) => acc.updated(x, y)
} ++ Map(nodes.last -> nodes.head)
def partitions = {
pages.map { page =>
val hash = KeyHasher.KETAMA.hashKey(page)
val primary = ketamaDistributor.nodeForHash(hash)
Partition(page, primary, nodeIndex(primary)
}
}
}
object Partitioner {
val numReps = 160
val defaultNodeWeight = 100
}
用法如下:
def uuid = java.util.UUID.randomUUID.toString
val nodes = (1 to 6).map { i => new Backend(s"machine-$i") }
val pages = (1 to 100).map { _ => uuid }
val partitioner = new Partitioner(pages, nodes)
val partitions = partitioner.partitions
// find the primary and secondary server for a given page
partitions(page.head)
// => Partition(f7eba506-e366-4cf3-ad72-4992fc5431b0,machine-5,machine-6)