Scalable coordination in tightly-coupled distributed systems
MetadataShow full item record
In tightly-coupled distributed systems, coordination among processes for shared resources is critical for system performance. While centralized approaches are easier to implement and manage, decentralized schemes can be more appealing due to the lack of a single point of failure and low latency in geographically-distributed applications. This thesis aims to characterize the conditions and scenarios in which centralized coordination is useful by showing its benefits in applications where global coordination is required. In order to investigate the possibilities introduced by centralized coordination, this thesis proposes a centralized lock broker architecture for efficient distributed transactions called Panopticon. A major advantage of the centralized design is the reduced latency compared to decentralized systems based on two-phase locking which suffer from inefficient lock acquisition and coordination. In an n-server system, serial lock acquisition of a transaction coordinator in decentralized systems requires n round-trip times because of requesting locks one by one from every lock holder sequentially. On the other hand, a centralized approach requires just 2 round-trip times; one for the request from coordinator to central broker and one for the request from the broker to lock holders in parallel. In Panopticon, scalability is achieved by divorcing locks from the data items and striving to improve lock access locality. The lock broker in Panopticon mediates the access to data shared across servers by migrating the associated locks like tokens, and in the process learns and improves the access locality of transactions. While Panopticon provides good performance and scalability for distributed transactions, overhead of using transactions is still high and should be avoided as much as possible. Therefore the centralized approach in Panopticon is extended to general tightly-synchronized distributed applications to design the Maestro framework. Maestro takes a preventive approach by examining the program actions of the workers before deployment and then automatically determining which actions can be executed locally (without contacting the master) and which actions require synchronization through the master. The lessons learned from Maestro is also applied to distributed graph processing. When locality improves, it is possible to improve the performance by separation of local coordination from inter-process coordination. For this purpose, this thesis proposes Giraphx, a modification to the bulk-synchronous parallel (BSP) model of Apache Giraph, to implement sequential consistency without reducing the highly-scalable nature of BSP. For ensuring consistency, Giraphx uses two coordination mechanisms: a dining philosopher based solution called d-Giraphx and a simple token-based solution called t-Giraphx. For providing fast and scalable operation, Giraphx bypasses the message queue and reads directly from workers memory for the internal vertex executions.