对几项带有随机算法思想的工作的讨论
对几项带有随机算法思想的工作的讨论
（节选自上学期本人组内讨论课作业）
在某些类型的数值计算问题中，我们常使用随机算法，如数值概率算法（得到近似解）、拉斯维加斯算法（不一定有解，如果有解一定正确）、蒙特卡罗算法（一定有解，但解不一定正确）、舍伍德算法（一定有解，解一定正确）。这些随机算法的原理基于概率模型，用简单的随机因子代替精确但复杂度高的最优化求解。对于数值概率算法，通过增加计算次数逼近精确解；对于后三类算法，通过增加计算次数提高得到正确解的概率，总体上都可以得到比确定性算法更低的平均时间复杂度。数值概率算法牺牲了解的精确性（Accuracy），但在很多场合下精确性不是首要要求；后三类算法有失去正确性（Correctness）的风险，但由于有办法将失败化为小概率事件，故在实际应用中利远大于弊。
在计算机系统，特别是分布式系统的各类问题中，活性（Liveness）与安全性（Safety）往往是评价某种解决方案的关键因素，这类似于数值计算问题中的正确性，通常是不能含糊的，有必要做形式化证明。但这在实际中并不是绝对的。在本学期的讨论课上我们了解了不少工作，其中引入了概率模型，应用类似于随机算法的思想，牺牲某些情况下系统内部绝对的活性与安全性来换取性能的大幅提升，同时引入相关的机制将潜在的失败可控化，不影响系统对外的活性与安全性。这些工作包括：
Exterminator：一种能动态修复C、C++程序堆内存错误的运行时库。基于统计规律，在多次运行时重新安排内存布局来定位错误，对错误位置分配额外的内存来降低再次出错的概率，使得原本有内存缺陷的程序可对外表现正常，同时便于开发人员快速定位错误。
MetaTM/TxLinux：一类基于事务的内存管理模型。用允许并发访问临界区的事务管理算法代替严格的锁保护机制。同时检测临界区冲突，在发生冲突时回滚重试。它减少了系统同步操作中由严格的锁带来的性能瓶颈。
Zyzzyva：一种拜占庭容错协议。一般情况下乐观地采纳主服务器对请求处理顺序的判断，省去了三阶段提交（3PC）协议。同时在客户端检测服务器副本可能的不一致，在发现问题时通知其更正。这种方案减少了3PC协议带来的开销。
● 我得到的一些启发
这些工作中的随机算法思想
Exterminator的做法带有数值概率算法的思想。设想一类能够精确地对运行时程序内存进行分析、预测和修复的机制，它应该覆盖所有可能的执行路径，并对有关变量的值域、边界条件等做细致分析，其复杂度有可能是指数级的。但Exterminator仅分析了特定的，也是实际工作中典型的执行路径，通过多次运行随机安排内存布局的实例来找出可以正常运行的实例，并利用内存布局的信息计算每一块内存分配可能引发错误的概率，复杂度下降到了多项式级。在一些基本假设下，作者给出了Exterminator对内存操作问题位置判定正确性概率的公式。Exterminator这样的设计满足了作者所谓 “automatically correcting memory errors with high probability”的需求。作为一种运行时的、治标不治本的纠错机制，使用随机算法很好地平衡了其功能和性能。它所找到的问题位置对机器来说精确度并不高，修补方案也很粗糙，但其分析结果在程序员来看足以发现错误原因并在代码中修正了，具备可用性（尽管目前版本输出信息的可读性不高，但容易改进）。
MetaTM/TxLinux和Zyzzyva对原有机制的简化没有破坏它们的活性，但弱化了原有机制的安全性，从这个角度看，它们类似于蒙特卡罗算法。不同的是，数值计算可以通过多次运行来提高解的置信度，而系统算法是有副作用的，不能通过多次运行的方法提高其安全性。MetaTM/TxLinux 和Zyzzyva均采用额外的监督机制来发现错误，在情况不合预期时及时告知算法进程撤销错误操作，重新运行算法或者转而使用原有的安全机制运行。这样，作为一个整体，系统的安全性重新得到了保证。MetaTM/TxLinux的作者没有给出他们这种乐观的并发执行性能的理论证明，但通过在修改之后的 Linux内核上运行多个实际负载，用实验数据说明了事务内存的开销小于传统的锁机制。Zyzzyva的作者同样以实验数据说明为主。可以预测，其假设失败的概率与分布式系统中节点本身失效的概率相关。
完备性（Completeness）与可用性（Availability）的权衡
上面已经提到，Exterminator的算法肯定不能准确覆盖和修正所有内存错误，但作为一个辅助工具，对用户来说可用性是足够的。对它来说可用性的约束弱于完备性。在MetaTM/TxLinux中，监督机制的加入从理论上保证了系统的安全性，但测试表明对一类频繁更新文件系统同一结点的负载，事务内存的乐观估计失效，临界区冲突激增，系统可用性下降。在这种情况下可以认为可用性的约束强于理论上的完备性。可见，在有些时候系统的完备性与可用性的约束强度不能一概而论，需要针对具体上下文来分析。
面向方面程序设计（Aspect Oriented Programming）的思想
MetaTM/TxLinux对临界区的控制相比严格的锁要简单不少，但之所以能够对应用保证安全性，是因为它改变了对环境的假设，拓宽了系统边界，加入了外部的监督机制。Zyzzyva中客户端对服务器的监督和反馈也类似。这种通过适当修改外界条件假设，加入外部机制以解决在原有系统闭包内不能或难以解决的问题的方法是值得我们学习和应用的。
更进一步地看，将监督反馈机制、垃圾回收机制，乃至活性、安全性这样的抽象性质独立出来，作为一种系统“切面”机制，体现了一定的面向方面的程序设计思想。这类方法或许在GOS将来的设计中有积极意义。
● 我认为这些工作的不足
应用于数值计算的随机算法的平均复杂度和性能都是可以借助概率论证明的，但应用于系统问题的随机算法只能对理想负载计算其性能，在实际利用中负载的特性对系统的性能可能有显著的影响。MetaTM/TxLinux的事务内存的在某些负载下的临界区冲突激增的问题就是一例。作者叙述了这一现象并推测了原因，但没有给出这类问题共性的、内在的原因。如果能够进一步分析这类问题的本质，较为明确地找出不同内存管理模型的适用条件，则可能更具学术和实用意义。如果在此基础上引入一些启发式算法，根据负载的特性调整执行策略，有可能达到更好的效果。
MetaTM/TxLinux文章以及会议演示文稿均用相当的篇幅阐述其实验方法和评测结果，作者选择的几个测试用例基本覆盖了Linux内核几大模块的主要原语，但这只是在静态层面上的。内存管理可能遇到的诸多问题只有在不同类型的原语以不同序列组合的动态运行过程中才能充分暴露。因此，如何提高测试用例的说服力是一个问题。
● 总结
我从上述工作中学习到的算法以及其中蕴含的随机算法等思想可以说是一类技术，在初始了解到其巧妙之处后，我曾设想在其它一些经典的系统问题中如何应用这一工具，例如在共识问题（Consensus）中如何快速取得一致。但我觉得有一条原则需要注意，不能为了使用工具而使用工具，要以应用的需求为出发点，合理地分析应用对系统性质的需求，选择最适合的技术方案。这几项带有随机算法思想的工作之所以比较成功，我认为就是因为作者对问题需求把握得好，适时地放弃一些次要目标，另辟蹊径来换取首要问题的高效解决。
