江苏龙网

  1. 首页 > 生活 > >

怎样判定一个分布式错误探测算法（failure detector）的准确性（accuracy）

最近刚好在关注这方面问题。 Failure Detection是分布式系统中基础性问题，也是一个很困难的问题。困难在于初始阶段crash server 与 slow server很难区分（是指节点通过网络互连的场景下，各个节点很难区分其他节点是crash server还是slow server）。正因为如此，分布式系统中的Failure Detector都是不可靠的。通常情况下，Failure Dectector 判断一个节点是否dead，输入一个集群节点， 输出一个值，要么是一个BOOL量（表示dead 或者alive)；要么是一个标量（表示一个节点是alive的置信度，如值越高，表示活着的概率越大，值越低表示dead概率越大，cassandra/scylladb就是采用这种方案）。对于后者，通过阈值可以将标量转为为BOOL量。回到问题，无论哪种情况，都可以用算法中常用到的准确率(precision)、召回率(recall)来描述 Failure Detector的准确程度。那如何用precision, recall来描述我们的算法准确程度呢？记：True Positives（TP）：状态是dead的节点，算法判断为dead 节点； False Positives（FP）：状态是alived的节点，算法判断为dead 节点； True Negatives（FN） ： 状态是dead的节点，算法判断为 alive 节点； False Negatives（TN）：状态是alive 的节点，算法判断为alive节点；那么，准确率（precision) = TP/(TP + FP), 召回率(Recall) = TP/(TP + FN);然后假设题主有一堆不同的算法，在相同条件下去做实验，采集数据，然后按照上面公司来计算precision 和 recall。----如果这是一道老师留的作业题，那么按上面处理应该就差不多了。如果这是生产系统中的一个问题，那么还需要考虑更多细节问题。
■网友
学院派路过.吐槽：看问题title，心想很久没看到那么学院派的问题了，然而问题描述又摇身一变回民科。科班和民科的差距大概就是有没有看懂书吧。不讨论系统模型讨论Consensus问题没有意义。Synchronized的分布式系统可以实现reliable的Failure Detector，设置timeout就行。Asynchronized的问题别人说过我不重复。Completeness和Accuracy是Failure Detector的属性。看下两属性的定义：Completeness, every crashed process is suspected.Accuracy, no correct process is suspected.属性是固有的. 你既然说是Failure Detector, 那么一定会有Accuracy.前属性定义了能测到（liveness）后属性定义了别测错（safety），具备两者才算detector，单有completeness基本没__用。插播吐槽：你的问题描述就像问，酸有没有pH值. 另一位工程派前辈就回答如何用pH试纸检验酸的pH值. （摊手.jpgCompleteness分两种：Strong and Weak.Accuracy分四种：Strong, Weak, Eventually Strong, Eventually Weak.（Strong, Weak没什么工程应用，因为实际不太可能achieve，纯粹学术严谨需求。后两种Eventually引入了时间，可工程实现）所以Failure Detector有（2*4）八款.（其实我的回答是酸肯定有pH值，分强酸还是弱酸作业来了：请参考另一位工程派答主提及的算法，判断是哪款Failure Detector.以上并没有很详细说明，因为我懒。具体Reference（都是书）：Distributed Systems an Algorithmic Approach 2ndDistributed System Principles and ParadigmsDistributed Computing Principles Algorithms and Systems书里面有论文推荐。这道题其他人已经没有回答的必要了，因为我答完了。（纯粹没理清定义而已）如此。装完逼赶紧逃.jpg


    推荐阅读


    上一篇：“刚正面”这个说法的起源以及传播过程

    下一篇：大学生花呗额度只能给1500