April 27, 2017
Google has recently announced that its flagship wide-area database named Spanner has been made available on the Google Cloud. Google Spanner is the next generation globally-distributed database built inside Google and announced to the world through the paper published in OSDI 2012 . This article explores the implication of Google Spanner, in particular to the NoSQL world.
Several other distributed systems such as Kafka also implement Paxos algorithms indirectly by using Zookeeper. Zookeeper implements an atomic broadcast protocol (it has been shown that consensus and atomic broadcast are equivalent problems in distributed systems) known as Zookeeper Atomic Broadcast (ZAB) . Many NoSQL datastores, including HDFS and Hive, use Paxos algorithms as they store metadata in a Zookeeper cluster.
 James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, J. J. Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson Hsieh, Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura, David Nagle, Sean Quinlan, Rajesh Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak, Christopher Taylor, Ruth Wang, and Dale Woodford. 2012. Spanner: Google’s Globally-Distributed Database. In Proceedings of the 10th USENIX conference on Operating Systems Design and Implementation (OSDI’12). USENIX Association, Berkeley, CA, USA, 251-264.
 Seth Gilbert and Nancy Lynch. 2002. Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News 33, 2 (June 2002), 51-59. DOI: https://doi.org/10.1145/564585.564601.
 Maurice P. Herlihy and Jeannette M. Wing. 1990. Linearizability: A Correctness Condition for Concurrent Objects. ACM Transactions on Programming Languages and Systems 12, 3 (July 1990), 463-492.
 Leslie Lamport. 1998. The Part-time Parliament. ACM Transactions on Computer Systems 16, 2 (May 1998), 133-169. DOI=http://dx.doi.org/10.1145/279227.279229
 Eric Brewer, “Spanner, TrueTime and the CAP Theorem”, available at https://research.google.com/pubs/pub45855.html
 Flavio P. Junqueira, Benjamin C. Reed, and Marco Serafini. 2011. Zab: High-performance broadcast for primary-backup systems. In Proceedings of the 2011 IEEE/IFIP 41st International Conference on Dependable Systems&Networks (DSN ’11). IEEE Computer Society, Washington, DC, USA, 245-256.
 Butler Lampson. 2001. The ABCD’s of Paxos. In Proceedings of the twentieth annual ACM symposium on Principles of distributed computing (PODC ’01). ACM, New York, NY, USA, 13-. DOI=http://dx.doi.org/10.1145/383962.383969.
 Diego Ongaro and John Ousterhout. 2014. In Search of an Understandable Consensus Algorithm. In Proceedings of the 2014 USENIX conference on USENIX Annual Technical Conference (USENIX ATC’14), Garth Gibson and Nickolai Zeldovich (Eds.). USENIX Association, Berkeley, CA, USA, 305-320.
 A. Ailijiang, A. Charapko and M. Demirbas, “Consensus in the Cloud: Paxos Systems Demystified,” 2016 25th International Conference on Computer Communication and Networks (ICCCN), Waikoloa, HI, 2016, pp. 1-10. doi: 10.1109/ICCCN.2016.7568499.
 Butler W. Lampson. 1981. Atomic Transactions. In Distributed Systems – Architecture and Implementation, An Advanced Course, Butler W. Lampson, M. Paul, and H. J. Siegert (Eds.). Springer-Verlag, London, UK, UK, 246-265.
 Spencer Kimball, “Living Without Atomic Clocks”, CockroachDB Blog, available from: https://www.cockroachlabs.com/blog/living-without-atomic-clocks/.
 Andrew Pavlo and Matthew Aslett. 2016. What’s Really New with NewSQL?. SIGMOD Record, 45, 2 (September 2016), 45-55. DOI: http://dx.doi.org/10.1145/3003665.3003674
 Barbara Liskov. 1991. Practical uses of synchronized clocks in distributed systems. In Proceedings of the tenth annual ACM symposium on Principles of distributed computing (PODC ’91). ACM, New York, NY, USA, 1-9. DOI=http://dx.doi.org/10.1145/112600.112601
 Leslie Lamport, Robert Shostak, and Marshall Pease. 1982. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems 4, 3 (July 1982), 382-401. DOI=http://dx.doi.org/10.1145/357172.357176.
 Crosby, M., Pattanayak, P., Verma, S., & Kalyanaraman, V. (2016). Blockchain technology: Beyond bitcoin. Applied Innovation, 2, 6-10.
 Seth Proctor, “Google Cloud Spanner & NuoDB: A Comparison of Distributed, ACID-Compliant Database”, available from https://www.nuodb.com/techblog/google-cloud-spanner-nuodb-comparison-distributed-acid-compliant-databases.
Copyright @ 2017, Vijay Srinivas Agneeswaran, All rights reserved.
February 9, 2017
Comments are closed