Title: K2: Lower Latency for Partial Replication Across Many Datacenters
Abstract:
The infrastructure available to large-scale web services now spans dozens of geographically dispersed datacenters. Utilizing this large number of datacenters to scale storage capacity requires a backend storage system to partially replicate data, i.e., to store only a subset of data in each datacenter. Partial replication, however, sacrifices the low latency benefits of having many datacenters: accessing data that is not replicated in a local datacenter incurs higher delay from contacting far-away datacenters.
K2, a causally-consistent data store with read-only transactions and write-only transactions, shows it is possible for a partially-replicated storage system to provide local datacenter latency in many settings. This is powered by our novel replication approach, MetaDC, and a novel read-only transaction algorithm. With only simple writes, MetaDC provides the best possible worst-case latency for read-only transactions in K2: a single round trip to remote datacenters. The novel read-only transaction algorithm allows many read-only transactions to execute entirely in their local datacenters by exploiting a small data cache. Our evaluation shows that K2 achieves much lower latency than a baseline that directly adapts causal consistency for partial replication.
Reading List
Textbook:
TANENBAUM, A. S., AND vAN STEEN, M. Distributed Systems: Principles and Paradigms (2nd Edition).Pearson Education, 2006.
Paper list:
AHAMAD, M., NEIGER, G., KOHLI, P., BURNS, J., AND HUTTO, P. Causal Memory: Definitions, Implementation, and Programming. Distributed Computing 9, 1 (1995).
ANNAMALAI, M., RAVICHANDRAN, K., SRINIVAS, H., ZINKOVSKY, I., PAN, L., SAVOR, T., NAGLE, D., AND STUMM, M. Sharding the Shards: Managing Datastore Locality at Scale with Akkio. In Proc. OSDI (2018).
BELARAMANI, N., DAHLIN, M., GAO, L., NAYATE, A., VENKATARAMANI, A., YALAGANDULA, P., AND ZHENG, J. PRACTI replication. In Proc. NSDI (2006).
CORBETT, J. C., DEAN, J., EPSTEIN, M., FIKES, A., FROST, C., FURMAN, J., GHEMAWAT, S., GUBAREV, A., HEISER, C., HOCHSCHILD, P., HSIEH, W., KANTHAK, S., KOGAN, E., LI, H., LLOYD, A., MELNIK, S., MWAURA, D., NAGLE, D., QUINLAN, S., RAO, R., ROLIG, L., SAITO, Y., SZYMANIAK, M., TAYLOR, C., WANG, R., ANDWOODFORD, D. Spanner: Google’s Globally-Distributed Database. In Proc. OSDI (2012).
DECANDIA, G., HASTORUN, D., JAMPANI, M., KAKULAPATI, G., LAKSHMAN, A., PILCHIN, A., SIVASUBRAMANIAN, S., VOSSHALL, P., AND VOGELS , W. Dynamo: Amazon’s highly available key-value store. In Proc. SOSP (2007).
LAMPORT, L. Time, clocks, and the ordering of events in a distributed system. Comm. ACM 21, 7 (1978).
LAMPORT, L. The Part-Time Parliament. ACM TOCS 16, 2 (1998).
LLOYD, W., FREEDMAN, M. J., KAMINSKY, M., AND ANDERSEN, D. G. Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS. In Proc. SOSP (2011).
LLOYD, W., FREEDMAN, M. J., KAMINSKY, M., AND ANDERSEN, D. G. Stronger Semantics for Low- Latency Geo-Replicated Storage. In Proc. NSDI (2013).
MAHMOOD, T., NARAYANAN, S. P., RAO, S., VIJAYKUMAR, T. N., AND THOTTETHODI, M. Karma: Cost-effective geo-replicated cloud storage with dynamic enforcement of causal consistency. IEEE TCC (2018).
PETERSEN, K., SPREITZER, M., TERRY, D., THEIMER, M., AND DEMERS, A. Flexible update propagation for weakly consistent replication. In Proc.SOSP (1997).
ZAWIRSKI, M., PREGUIC ̧A, N., DUARTE, S., BIENIUSA, A., BALEGAS, V., AND SHAPIRO, M. Write Fast, Read in the Past: Causal Consistency for Client-Side Applications. In ACM/IFIP/USENIX International Middleware Conference (2015).