Okapi is a new causally consistent geo-replicated key-value store. Okapi leverages two key design choices to achieve high performance. First, it relies on hybrid logical physical clocks to achieve low latency even in the presence of clock skew. Second, Okapi achieves higher resource efficiency and better availability, at the expense of a slight increase in update visibility latency. To this end, Okapi implements a new stabilization protocol that uses a combination of vector and scalar clocks and makes a remote update visible when its delivery has been acknowledged by every data center. We evaluate Okapi with different workloads on Ama- zon AWS, using three geographically distributed regions and 96 nodes. We compare Okapi with two recent ap- proaches to causal consistency, Cure and GentleRain. We show that Okapi delivers up to two orders of magnitude better performance than GentleRain and that Okapi achieves up to 3.5x lower latency and a 60 reduction of the meta-data overhead with respect to Cure.
Dependency tracking. The systems based on logical clocks keep detailed dependency information, encoded as a dependency list @cite_18 @cite_32 @cite_21 @cite_19 or matrix @cite_33 . black The techniques proposed to reduce the resulting overhead have downsides like per-update acknowledgement messages among replicas @cite_33 , call-backs to the client @cite_33 , or delay the visibility of updates also in the local data center @cite_8 @cite_10 . GentleRain and Cure track dependencies at a coarser granularity. GentleRain uses a single timestamp to achieve minimal overhead but incurs high waiting times to serve read-only transactions. Cure uses dependency vectors to avoid this issue but incurs a dependency tracking overhead linear in the number of data centers. uses dependency vectors too but reduces the meta-data for remote updates at the cost of slightly delaying their visibility at remote sites.
@cite_18 @cite_33 @cite_8 @cite_21 @cite_32 @cite_19 @cite_10
2112612200 2111113897 1925953220 2013708313
We propose two protocols that provide scalable causal consistency for both partitioned and replicated data stores using dependency matrices (DM) and physical clocks. The DM protocol supports basic read and update operations and uses two-dimensional dependency matrices to track dependencies in a client session. It utilizes the transitivity of causality and sparse matrix encoding to keep dependency metadata small and bounded. The DM-Clock protocol extends the DM protocol to support read-only transactions using loosely synchronized physical clocks. We implement the two protocols in Orbe, a distributed key-value store, and evaluate them experimentally. Orbe scales out well, incurs relatively small overhead over an eventually consistent key-value store, and outperforms an existing system that uses explicit dependency tracking to provide scalable causal consistency. GentleRain is a new causally consistent geo-replicated data store that provides throughput comparable to eventual consistency and superior to current implementations of causal consistency. GentleRain uses a periodic aggregation protocol to determine whether updates can be made visible in accordance with causal consistency. Unlike current implementations, it does not use explicit dependency check messages, resulting in a major throughput improvement at the expense of a modest increase in update visibility. Furthermore, GentleRain tracks causal consistency by attaching to updates scalar timestamps derived from loosely synchronized physical clocks. Clock skew does not cause violations of causal consistency, but may delay the visibility of updates. By encoding causality in a single scalar timestamp, GentleRain reduces storage and communication overhead for tracking causality. We evaluate GentleRain using Amazon EC2, and demonstrate that it achieves throughput equal to about 99 of eventual consistency, and 120 better than previous implementations of causal consistency. It is well known that causal consistency is more expensive to implement than eventual consistency due to its requirement of dependency tracking and checking for causality. To close the performance gap between the two consistency models, we propose a new protocol that implements causal consistency for both partitioned and replicated data stores. Our protocol trades the visibility latency of updates across different client sessions for higher throughput. An update, either from a local client or a remote replica, is only visible to other clients after it is replicated by all replicas. As a result, a read operation never introduces dependencies to its client session. Only update operations introduce dependencies. By exploiting the transitive property of causality and total order update propagation, an update always has at most one dependency. By reducing the number of tracked dependencies and the number of messages for dependency checking down to one, we believe our protocol can provide causal consistency with similar cost to eventual consistency. Recovery from tracking failure is essential in any simultaneous localization and tracking system. In this context, we explore an efficient keyframe-based relocalization method based on frame encoding using randomized ferns. The method enables automatic discovery of keyframes through online harvesting in tracking mode, and fast retrieval of pose candidates in the case when tracking is lost. Frame encoding is achieved by applying simple binary feature tests which are stored in the nodes of an ensemble of randomized ferns. The concatenation of small block codes generated by each fern yields a global compact representation of camera frames. Based on those representations we define the frame dissimilarity as the block-wise hamming distance (BlockHD). Dissimilarities between an incoming query frame and a large set of keyframes can be efficiently evaluated by simply traversing the nodes of the ferns and counting image co-occurrences in corresponding code tables. In tracking mode, those dissimilarities decide whether a frame pose pair is considered as a novel keyframe. For tracking recovery, poses of the most similar keyframes are retrieved and used for reinitialization of the tracking algorithm. The integration of our relocalization method into a hand-held KinectFusion system allows seamless continuation of mapping even when tracking is frequently lost.