MeteorShower: geo-replicated strongly consistent NoSQL data store with low latency : Achieving sequentially consistent keyvalue store with low latency

Abstract: According to CAP theorem, strong consistency is usually compromised in the design of NoSQL databases. Poor performance is often observed when strong data consistency level is required, especially when a system is deployed in a geographical environment. In such an environment, servers need to communicate through cross-datacenter messages, whose latency is much higher than message within a data center. However, maintaining strong consistency usually involves extensive usage of cross-datacenter messages. Thus, the large cross-data center communication delay is one of the most dominant reasons, which leads to poor performance of most algorithms achieving strong consistency in a geographical environment. This thesis work proposes a novel data consistency algorithm – I-Write-One-Read-One based on Write-One-Read- All. The novel approach allows a read request to be responded by performing a local read. Besides, it reduces the cross-datacenter-consistency-synchronization message delay from a round trip to a single trip. Moreover, the consistency model achieved in I-Write-One-Read-One is higher than sequential consistency, however, looser than linearizability. In order to verify the correctness and effectiveness of IWrite- One-Read-One, a prototype, MeteoerShower, is implemented on Cassandra. Furthermore, in order to reduce time skews among nodes, NTP servers are deployed. Compared to Cassandra with Write-One-Read-All consistency setup, MeteoerShower has almost the same write performance but much lower read latency in a real geographical deployment. The higher cross-datacenter network delay, the more evident of the read performance improvement. Same as Cassandra, MeteorShower also has excellent horizontal scalability, where its performance grows linearly with the increasing number of nodes per data center.