分布式系统中数据结构的算法

Question

哈希表数据结构可以很容易地分布在多台机器上，只需一个简单的算法就可以分发密钥：

machine_to_query = item_key % machine_count

当您想要读取和写入键值对时，可以使用键来计算出存储数据的机器，然后与该机器对话。如果您想要一个项目总数的计数，您需要从每个服务器请求计数并将它们加起来。

有哪些算法可以有效地管理数据结构，在多台机器上对数据进行分区？分布式算法，而不是并行算法。

像排序数组这样的东西如何以分布式方式工作呢？很有效率。

Answer 1

下面是一个类似问题的链接：

https://stackoverflow.com/questions/3927537/how-do-you-implement-sorting-and-paging-on-distributed-data

此外，T-79.4001理论计算机科学研讨会的最后一篇文章似乎很有用：

http://www.tcs.hut.fi/Studies/T-79.4001/2007SPR/

关于这一主题的一些书籍：

• 分布式算法- Kaufmann
• 分布式算法的设计与分析

Answer 2

我不知道出版的书有这种东西，但有一些现实世界的例子，你可以看看。Scala有一个Parallel">http://www.scala-lang.org/api/current/index.html#scala.collection.parallel.immutable.package">Parallel不变集合包。他们有一些哈希支持的东西，但也有一个向量(实现为一个浅树source">http://xuwei-k.github.com/scala-library-sxr/scala-library-2.10.0-M1/scala/collection/parallel/immutable/ParVector.scala.html">source代码可用)和序列。

我认为Java 8正在重写集合，将其作为Project">http://openjdk.java.net/projects/lambda/">Project Lambda的一部分，以便您也可以研究这一点。我希望源代码可以在某个地方使用，但经过简短的搜索，我找不到它。我认为一个关键因素(我认为你在你的问题中假设了这一点)是拥有一个集合来做它自己的并发管理是一个巨大的胜利。集合不是在每个用户必须管理并发性的外部迭代集合，而是执行某种map()或减()操作，其中传递一个对每个项或每个项进行筛选的函数，并且集合在内部管理其并发性。

我认为其中的大多数都采用了分而治之的方法，将各部分分配给不同的处理器。您可以将谷歌Ahmdal's">http://en.wikipedia.org/wiki/Amdahl%27s_法“>阿姆达尔法法则作为一个起点，因为它控制着在多个处理器上运行任何算法可能获得的最大性能增益。此外，地图减少和大数据。