Distributed Method of Web Services

Abstract

In this paper, the Web Services on the Internet are distributed in a general low-cost way. The specific method is to reduce the coupling between Web Services tasks, and then use the written data as concurrency basis to determine whether different Web Services process can be distributed. Finally, according to the decision, different Web Services process can be flexibly distributed to the hardware cluster.

Index Terms

Distributed programming, Distributed objects, components, containers, Concurrency, Web Services, Deadlocks, Distributed systems.

I. Introduce

In the Internet industry, there has been a high degree of enthusiasm for how to distribute complex Web Services to hardware clusters using simple methods. With the increasing number of corporate users in the Internet boom, the number of users who need support from Web Services is also increasing. Increasing the uncertainty risk and capital cost of hardware is much less than reconstructing software system. There are three important research directions in the general distributed field. In pure theory, the FLP theory in [1] proves that it is impossible to reach a consensus using asynchronous communication. A method is described in reference [2]. The developer follows the actor model to develop the software in a distributed way. Another method is described in reference [3]. According to the data shard rules, the data is shard to different servers. The former is too flexible and the latter too rigid. Compared with the general distributed method, this paper proposes a method of partitioning Web Services as small as possible and assigning them to different hardware to improve the carrying capacity of the system. The method introduced in this paper has good universality and operability in the field of Internet.

II. Asynchronous Environment

We use an asynchronous environment. The asynchronous network model is formally proposed by Lynch in [4]. Environment refers to a highly discrete information network, formally proposed by Carl Hewitt in [5], which is based on the relationship between modern physics and sociology. In the asynchronous environment, the Web Services run in a hardware cluster consisting of multiple hardware Mφ, where φ is a positive integer from 1 to infinity. Mφ is formally defined by Herlihy and Wing in [6]. It has linearization and atomicity. The hardware Mφ receives random messages from the information network and calls the corresponding processing process. The Web Services is composed of a number of processes Pλ, where λ is a positive integer from 1 to infinity. Pλ calls multiple data sets Dδ to complete the message, where δ is a positive integer from 1 to infinity. We define all processes as P (1…λ) and all data as D (1…δ). The mode of P (1…λ) and D (1…δ) running in any Mφ is called single M mode. Compared with the single M model, we get the requirements of this paper:

Demand 1. How to distribute any combination of Pλ and Dδ into Mφ while keeping Pλ unchanged?

III. Question 1

Assuming that Pλ is randomly distributed to Mφ and then triggered by random messages, if the deadlock condition defined in [7] is reached, the deadlock problem will inevitably arise. See Figure 1.

The deadlock condition is that P1 locked data set D1 and requests data set D2, P2 locked D2 and requests D1.

IV. Solution 1

Create the shadow data set Sμ of the data set Dδ, in which μ is a positive integer from 1 to infinity. When the data set Dδ changes, it updates Sμ synchronously, and keeps the consistency between Dδ data and Sμ data. It can be seen that the update delay time is t. The definition of consistency is the same as the delay t consistency defined by reference [8]. We define the minimum time interval for data set Dδ to be modified as mt (Dδ). The effective range of delay is defined as 0 < t <= mt (Dδ). When t > mt (Dδ) causes Sμ to lose data without triggering updates. See Figure 2.

Because P1 does not wait when requesting S2 data, P2 does not wait when requested S1 data. Break the deadlock condition "Hold and wait or resource holding". There will be no deadlock problem in the system with Sμ. Because of the uncertainty in the environment of the information network, the error system caused by the delay in obtaining data of any Pλ does not need to be handled, but directly returns to the user to decide whether to re-initiate the requested or not.

The way we create shadow data Sμ for Dδ and keep its sequential consistency is called "Availability partition Relation&operation" for short AP.

V. Question 2

Suppose that in Solution 1, when both P1 and P2 attempt to write to D2, a write conflict occurs. See Figure 3.

This conflict situation is the same as the write conflict generated by Git, the version tool we often use. It will cause the problem of new data loss or old data covering new data.

VI. Solution 2

In order to solve Question 2, we put Pλ with the same write requirement into the same Mφ. See Figure 4.

The method of dividing Pλ into different types according to whether the written data intersects or not is called "rip partition relation&operation" abbreviated as RP.

As shown in the figure, both P1 and P2 read data D1 and write it to D2, which is recorded as P1{ r:D1D2,w:D2 }, P2{ r:D1D2,w:D2 }. P3 is written to D1 and recorded as P3{ r:D1D2,w:null } or P3{ r:D1D2,w:D1 }. Because P1 and P2 have write conflict, they can only be placed in the same Mφ. P3 and P1, P2 do not write conflict, so they can be placed in any Mφ. This Web Services consisting of P1, P2 and P3 can be divided into the following four parts: see Figure 5.

And put it in four Mφ, So Demand 1 is solved.

VII. Conclusion

The transmission of information on the Internet is realized through long distance networks. After such a long and unstable network, the accuracy of information and data acquired by users will be delayed and uncertain. The requirement of data accuracy is subdivided into two cases: reading and writing. For the lowest accuracy of information read, delay or even error can be allowed. The requirement for writing data is relatively high, allowing delays but not obvious errors. So-called obvious errors, such as old data overwriting new data. But the definition of old and new is ambiguous. Therefore, the comparison between the old and the new has evolved into priority scheduling, which is usually solved by FIFO queuing. When user requirements extend from the Internet to Web Services, the accuracy requirements between processes in Web Services triggered by user requests can also be reduced appropriately. Because of the high precision requirement, the process cannot be separated because of the high order dependence.Therefore, this paper uses AP (allowing delayed t consistency) to reduce the accuracy of reading and RP (sorting the process of writing conflicts) to improve the accuracy of writing. Finally, some process of the Web Services can be distributed to the hardware cluster.

References

[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]