Web 服务的分布式方法

摘要

本文以一种通用的低成本方式，在互联网上分发Web服务。具体方法是降低Web服务任务之间的耦合度，然后以已写入的数据作为并发基础，判断不同的Web服务进程是否可以分发。最后，根据判断结果，可以将不同的Web服务进程灵活地分发到硬件集群。

索引术语

分布式编程、分布式对象、组件、容器、并发、Web服务、死锁、分布式系统。

一、引言

在互联网行业，如何用简单的方法将复杂的Web服务分发到硬件集群，一直备受关注。随着互联网热潮中企业用户数量的不断增加，需要Web服务支持的用户数量也日益增多。增加硬件的不确定性风险和资本成本远低于重建软件系统。在通用分布式领域，有三个重要的研究方向。在纯理论方面，[1]中的FLP理论证明了使用异步通信无法达成共识。[2]中描述了一种方法，开发人员遵循Actor模型以分布式方式开发软件。[3]中描述了另一种方法，根据数据分片规则将数据分片到不同的服务器。前者过于灵活，后者过于僵硬。与通用分布式方法相比，本文提出一种尽可能小地划分Web服务并将其分配到不同硬件以提高系统承载能力的方法。本文介绍的方法在互联网领域具有良好的通用性和可操作性。

二、异步环境

我们使用异步环境。异步网络模型由Lynch在[4]中正式提出。环境指的是一个高度离散的信息网络，由Carl Hewitt在[5]中正式提出，其基于现代物理学和社会学之间的关系。在异步环境中，Web服务运行在由多个硬件Mφ组成的硬件集群中，其中φ是1到无穷大的正整数。Mφ由Herlihy和Wing在[6]中正式定义。它具有线性化和原子性。硬件Mφ接收来自信息网络的随机消息并调用相应的处理进程。Web服务由多个进程Pλ组成，其中λ是1到无穷大的正整数。Pλ调用多个数据集Dδ来完成消息，其中δ是1到无穷大的正整数。我们定义所有进程为P (1…λ)，所有数据为D (1…δ)。P (1…λ)和D (1…δ)在任何Mφ中运行的模式称为单M模式。与单M模型相比，我们得到了本文的需求

需求1. 如何将Pλ和Dδ的任意组合分配到Mφ中，同时保持Pλ不变？

三、问题1

假设Pλ随机分配到Mφ，然后由随机消息触发，如果达到[7]中定义的死锁条件，必然会产生死锁问题。见图1。

死锁条件是P1锁定了数据集D1并请求数据集D2，P2锁定了D2并请求D1。

四、解决方案1

创建数据集Dδ的影子数据集Sμ，其中μ是1到无穷大的正整数。当数据集Dδ改变时，它同步更新Sμ，并保持Dδ数据和Sμ数据之间的一致性。可以看出，更新延迟时间为t。一致性的定义与[8]中定义的延迟t一致性相同。我们将数据集Dδ被修改的最小时间间隔定义为mt (Dδ)。延迟的有效范围定义为0 < t <= mt (Dδ)。当t > mt (Dδ)时，Sμ会丢失数据而不会触发更新。见图2。

因为P1请求S2数据时不等待，P2请求S1数据时不等待。打破死锁条件“占有并等待或资源占有”。系统中使用Sμ将不会出现死锁问题。由于信息网络环境的不确定性，任何Pλ获取数据延迟引起的错误系统不需要处理，而是直接返回给用户，由用户决定是否重新发起请求。

我们为Dδ创建影子数据Sμ并保持其顺序一致性的方法称为“可用性分区关系与操作”，简称AP。

五、问题2

假设在解决方案1中，当P1和P2都尝试写入D2时，发生写入冲突。见图3。

这种冲突情况与我们常用的版本工具Git产生的写入冲突相同。它会导致新数据丢失或旧数据覆盖新数据的问题。

六、解决方案2

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

根据写入数据是否交叉将Pλ划分为不同类型的方法称为“rip分区关系与操作”，简称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存在写入冲突，它们只能放在同一个Mφ中。P3与P1、P2没有写入冲突，因此可以放在任何Mφ中。由P1、P2和P3组成的Web服务可以分为以下四部分：见图5。

并将其放入四个Mφ中，这样需求1就解决了。

七、结论

互联网上的信息传输通过长距离网络实现。经过如此漫长而不稳定的网络，用户获取信息的准确性会延迟且不确定。数据准确性要求细分为两种情况：读取和写入。对于读取信息的最低准确性，允许延迟甚至错误。对写入数据的要求相对较高，允许延迟但不允许明显错误。所谓的明显错误，例如旧数据覆盖新数据。但是旧和新的定义是模糊的。因此，新旧比较演变为优先级调度，通常通过FIFO排队解决。当用户需求从互联网扩展到Web服务时，用户请求触发的Web服务中进程之间的准确性要求也可以适当降低。由于高精度要求，进程不能因高阶依赖而分离。因此，本文使用AP（允许延迟t一致性）来降低读取精度，使用RP（对写入冲突进程进行排序）来提高写入精度。最后，Web服务的部分进程可以分发到硬件集群。

参考文献

[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". Pages 235-245. 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]