Web Services的分布式方法

摘要

此文将互联网中的Web Services以通用低成本的方法进行了分布式。具体方法为先通过降低Web Services过程间的耦合，再以写入的数据作为并发依据，用于判定不同Web Services过程能否进行分布式。最终依据判定可以灵活的将不同Web Services过程分布到硬件集群中的方法。

介绍

在互联网业界对于如何将复杂的Web Services，使用简单方法分布到硬件集群运行一直保有高度的热情。随着互联网热潮中公司用户量不断的攀升，需要Web Services所支持的用户量也再不断攀升。其中增加硬件所带来的不确定性风险和资金付出要比重构软件系统小的多。在通用的分布式领域中有三个重要的研究方向。在纯理论方面引用[1]中的FLP理论证明了使用异步通信不可能达成共识。在引用[2]中描述了一种方法。由开发者遵循演员模型对软件进行分布式开发。在引用[3]中描述了另一种方法。根据数据分片规则将数据分片到不同服务器。其前者过于灵活而后者又太过死板。与通用的分布式方法相比，本文提出了一种尽可能小的分割Web Services，并将其分配到不同的硬件上，以提高系统的承载能力的方法。所介绍的方法在互联网领域具有较好的通用性和可操作性。

异步环境

我们使用的是异步环境。其中的异步网络模型是由Lynch在[3]中正式提出的。环境则是指由卡尔·休伊特在[4]中正式提出的，建立在现代物理学和社会学关系基础上的的，具有高度离散性质的信息关系网。在异步环境的关系网中的Web Services，运行在多个硬件Mφ组成的硬件集群中，其中φ为从1到无穷大的正整数。Mφ是由Herlihy和Wing在[5]所正式定义的，具有线性化和原子性。硬件Mφ接收来自信息关系网中的随机消息并调用对应的处理过程。Web Services是多个处理过程Pλ组成，其中λ为从1到无穷大的正整数。Pλ调用多个数据集合Dδ完成消息，其中δ为从1到无穷大的正整数。我们定义将所有过程表示为P(0…λ)和所有数据表示为D(0…δ)。将P(0…λ)和D(0…δ)全部放入到任意Mφ中运行的模式称为单M模式。相对于单M模式我们得到本文的需求：

需求1，在保持Pλ不变的前提下，如何将任意Pλ与Dδ的组合分布到Mφ中？

问题1

假设将Pλ随机分布到Mφ然后随机消息触发运行，如果达成[6]所定义的死锁的条件就必然会产生死锁问题。见图1。

其死锁情况为P1锁住数据集D1并请求数据集D2,P2锁住D2并请求D1。

方案1

创建数据集Dδ的影子数据集Sμ其中μ为从1到无穷大的正整数,当数据集Dδ数据变更时就同步更新Sμ，保持Dδ数据与Sμ数据的一致性,可知其更新延迟时间为t。其一致性的定义与引用[7]所定义的延迟t一致性相同。我们定义数据集Dδ被修改的最短间隔时间为mt(Dδ)。则延迟的有效范围定义为0<t<=mt(Dδ)。当t>mt(Dδ)时会导致Sμ不触发更新而丢失数据。见图2。

因为其中P1在请求S2数据时不会产生等待，同理P2在请求S1数据时也不会产生等待。破坏了产生死锁的条件“占有且等待”。在有Sμ存在的系统内不会出现死锁问题。因为在信息关系网的环境本身就具有不确定性，所以数据延迟导致的错误系统都不必处理。只需简单返回给用户，由用户决定是否再次发起请求。

我们对Dδ创建影子数据Sμ，并保持其顺序一致的方法称为"Availability partition Relation&operation"简称AP。

问题2

假设方案1中当P1和P2都试图写入D2就会产生写入冲突。见图3。

这种冲突状况与我们常常使用的版本工具Git产生的写入冲突是一样的。其会产生新数据丢失或旧数据覆盖新数据的问题。

方案2

为了解决问题2，我们将有相同写入需求的Pλ放到同一个Mφ中。见图4。

这里将Pλ按写入数据是否交集划分为不同类型的方法称为" rip partition Relation&operation" 简称RP

如图所示P1和P2都读取数据D1并写入D2，记为P1{r:D1D2,w:D2},P2{r:D1D2,w:D2}。P3写入D1记为P3{r:D1D2,w:null}或P3{r:D1D2,w:D1}。因为P1与P2有写入冲突所以只能放在同一个Web Services内，P3与P1，P2没有写入冲突所以可以放在任意Mφ内。这个由P1,P2,P3组成的Web Services就可以拆分为如下四个部分：见图5。

并放入到四个Mφ内，所以需求1得解。

结论

在互联网中信息的地传递通过长途网络实现。用户获取的信息数据精度经过这样漫长而不稳定的网络后就会具有延迟和不确定性。对于数据精度的要求又细分为读写两种情况。对于读取到的信息精度要求最低，可以允许延迟甚至错误。而对于写入数据要求比较高，允许延迟但不能有明显的错误。所谓明显错误，例如旧的数据覆盖新的数据。但新旧本身的定义就是模糊不定的。所以对新旧的比较就演变成为优先级的调度，通常调度的算法使用FIFO排队的方式来解决。当用户需求从互联网延伸到Web Services后，使得基于用户请求触发的Web Services内的过程之间精度要求也可以适当降低。因为较高的精度要求使得过程之间存在较高的顺序依赖而无法拆分。所以本文分别使用AP方式（允许延迟t一致性）降低读的精度和RP方式（对写冲突的过程进行排序）提高写的准确性。最终得以将Web Services的部分过程分布到硬件集群中。

引用

[1] Fischer, M. J.; Lynch, N. A.; Paterson, M. S. (1985). "Impossibility of distributed consensus with one faulty process" (PDF). Journal of the ACM. 32 (2): 374–382. doi:10.1145/3149.214121

[2] Carl Hewitt; Peter Bishop; Richard Steiger (1973). "A Universal Modular Actor Formalism for Artificial Intelligence". IJCAI.

[3] P. Maymounkov and D. Mazieres. Kademlia: A peer-to-peer information system based on the xor metric. In Proceedings of IPTPS02, Cambridge, USA, Mar. 2002.

[4] Nancy Lynch. "Distributed Algorithms". pages 199–231. Morgan Kaufman, 1996.

[5] Carl Hewitt. (2006). "What is Commitment? Physical, Organizational, and Social". COINS@AAMAS. 2006

[6] Herlihy, Maurice P.; Wing, Jeannette M. (1990). "Linearizability: A Correctness Condition for Concurrent Objects". ACM Transactions on Programming Languages and Systems. 12 (3): 463–492. CiteSeerX 10.1.1.142.5315. doi:10.1145/78969.78972.

[7] Coffman, Edward G., Jr.; Elphick, Michael J.; Shoshani, Arie (1971). "System Deadlocks". ACM Computing Surveys. 3 (2): 67–78. doi:10.1145/356586.356588.

[8] Seth Gilbert, Nancy Lynch. "Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services". ACM SIGACT News, v.33 n.2, June 2002 [doi>10.1145/564585.564601]