zco*_*rts 9 algorithm p2p protocols distributed-computing message-queue
我一直在读"算法入门",并开始在我脑海里浮现出一些想法和问题.最令我困惑的是你如何设计一种算法来安排分发队列中的项目/消息.
我的想法让我浏览维基百科,主题包括排序,消息队列,调度,分布式哈希表,等等.
场景: 假设你想要一个排队消息的系统(例如字符串或一些序列化对象).该系统的一个关键特性是避免任何单点故障.系统必须分布在某个集群中的多个节点上,并且必须始终(或尽可能最好)甚至集群中每个节点的工作负载以避免热点.
您希望避免使用主/从设计进行复制和扩展(没有单点故障).该系统完全避免写入盘并保持在存储器数据结构中.
由于这是一种某种类型的队列,系统应该能够使用不同的调度算法(FIFO,最早期限,循环等......)来确定在下一个请求中应该返回哪个消息,而不管哪个节点在请求所针对的集群.
我最初的想法, 我可以想象这将如何在一台机器上工作,但当我开始思考你如何分配像这样的问题,如:
我如何散列每条消息？
我怎么知道邮件发送到哪个节点？
我如何安排每个项目,以便我可以确定下一个应该返回哪个消息和哪个节点？
我开始阅读有关分布式哈希表以及像Apache Cassandra这样的项目如何使用某种一致性散列来分发数据但我认为,因为查询不会提供密钥,我需要知道下一个项目的位置并且只是提供它.这导致阅读有关对等协议以及它们如何跨节点处理同步问题.
所以我的问题是,你将如何处理上述问题,或者这是一个太过牵强,只是一个愚蠢的想法......？
只是一个概述,指针,不同的方法,陷阱和每个的好处.可能适用的技术/概念/设计/理论.基本上任何可以用来理解这样的东西可能有用的东西.
如果你想知道,不,我不打算实施这样的事情,它只是在阅读时突然出现在我脑海中(碰巧的是,当我读一本好书时,我会被狂野的想法分心).
UPDATE
另一个有趣的问题是分布式删除.我知道像Cassandra这样的系统已经通过实施HintedHandoff,Read Repair和AntiEntropy解决了这个问题,它似乎运行良好,但有没有其他(可行和有效)的方法解决这个问题？
分布式算法有一些流行的技术，例如使用时钟、波或通用路由算法。
您可以在Tel 的分布式算法简介和Lynch 的分布式算法书籍中找到这些内容。
由于一般的分布式算法可能变得相当复杂，因此它们特别有用。您也许可以将其简化为更简单、更具体的情况。
例如，如果您想避免单点故障，但对称分布式算法太复杂，您可以使用（领导者）选举的标准分布式算法，然后使用更简单的非对称算法，即可以使使用大师。
同样，您可以使用同步器将同步网络模型转换为异步网络模型。
您可以使用快照进行离线分析，而不必处理不同的在线流程状态。