high_scalability high_scalability-2008 high_scalability-2008-357 knowledge-graph by maker-knowledge-mining
Source: html
Introduction: This is an unusually well written and useful paper . It talks in detail about experiences implementing a complex project, something we don't see very often. They shockingly even admit that creating a working implementation of Paxos was more difficult than just translating the pseudo code. Imagine that, programmers aren't merely typists! I particularly like the explanation of the Paxos algorithm and why anyone would care about it, working with disk corruption, using leases to support simultaneous reads, using epoch numbers to indicate a new master election, using snapshots to prevent unbounded logs, using MultiOp to implement database transactions, how they tested the system, and their openness with the various problems they had. A lot to learn here. From the paper: We describe our experience building a fault-tolerant data-base using the Paxos consensus algorithm. Despite the existing literature in the field, building such a database proved to be non-trivial. We describe selected alg
sentIndex sentText sentNum sentScore
1 They shockingly even admit that creating a working implementation of Paxos was more difficult than just translating the pseudo code. [sent-3, score-0.491]
2 From the paper: We describe our experience building a fault-tolerant data-base using the Paxos consensus algorithm. [sent-7, score-0.363]
3 Despite the existing literature in the field, building such a database proved to be non-trivial. [sent-8, score-0.315]
4 We describe selected algorithmic and engineering problems encountered, and the solutions we found for them. [sent-9, score-0.433]
5 A common approach is to use a consensus algorithm [7] to ensure that all replicas are mutually consistent [8, 14, 17]. [sent-12, score-0.695]
6 By repeatedly applying such an algorithm on a sequence of input values, it is possible to build an identical log of values on each replica. [sent-13, score-0.551]
7 If the values are operations on some data structure, application of the same log on all replicas may be used to arrive at mutually consistent data structures on all replicas. [sent-14, score-0.401]
8 For instance, if the log contains a sequence of database operations, and if the same sequence of operations is applied to the (local) database on each replica, eventually all replicas will end up with the same database content (provided that they all started with the same initial database state). [sent-15, score-0.892]
9 As a result, the consensus problem has been studied extensively over the past two decades. [sent-17, score-0.377]
10 There are several well-known consensus algorithms that operate within a multitude of settings and which tolerate a variety of failures. [sent-18, score-0.655]
11 The Paxos consensus algorithm [8] has been discussed in the theoretical [16] and applied community [10, 11, 12] for over a decade. [sent-19, score-0.541]
12 We used the Paxos algorithm (“Paxos”) as the base for a framework that implements a fault-tolerant log. [sent-20, score-0.292]
13 Despite the existing literature on the subject, building a production system turned out to be a non-trivial task for a variety of reasons: While Paxos can be described with a page of pseudo-code, our complete implementation contains several thousand lines of C++ code. [sent-22, score-0.702]
14 The blow-up is not due simply to the fact that we used C++ instead of pseudo notation, nor because our code style may have been verbose. [sent-23, score-0.258]
15 Converting the algorithm into a practical, production-ready system involved implementing many features and optimizations – some published in the literature and some not. [sent-24, score-0.62]
16 • The fault-tolerant algorithms community is accustomed to proving short algorithms (one page of pseudo code) correct. [sent-25, score-0.613]
17 • Fault-tolerant algorithms tolerate a limited set of carefully selected faults. [sent-28, score-0.3]
18 Finally, a system might “fail” due to a misunderstanding that occurred during its specification phase. [sent-34, score-0.254]
19 This paper discusses a selection of the algorithmic and engineering challenges we encountered in moving Paxos from theory to practice. [sent-35, score-0.409]
20 We divide our experiences into three categories and discuss each in turn: algorithmic gaps in the literature, software engineering challenges, and unexpected failures. [sent-40, score-0.347]
wordName wordTfidf (topN-words)
[('paxos', 0.386), ('pseudo', 0.258), ('literature', 0.248), ('consensus', 0.246), ('algorithm', 0.228), ('algorithmic', 0.159), ('sequence', 0.143), ('variety', 0.135), ('replicas', 0.12), ('describe', 0.117), ('encountered', 0.109), ('algorithms', 0.106), ('measurements', 0.105), ('tolerate', 0.105), ('values', 0.103), ('mutually', 0.101), ('implementation', 0.101), ('specification', 0.097), ('indicate', 0.096), ('selected', 0.089), ('despite', 0.087), ('system', 0.079), ('anduseful', 0.078), ('accustomed', 0.078), ('misunderstanding', 0.078), ('refresher', 0.078), ('robustly', 0.078), ('unusually', 0.078), ('log', 0.077), ('contains', 0.074), ('epoch', 0.073), ('paper', 0.073), ('leases', 0.07), ('studied', 0.07), ('engineering', 0.068), ('shockingly', 0.067), ('applied', 0.067), ('database', 0.067), ('implementing', 0.065), ('proving', 0.065), ('translating', 0.065), ('lines', 0.065), ('base', 0.064), ('multitude', 0.063), ('experiences', 0.061), ('extensively', 0.061), ('election', 0.061), ('openness', 0.061), ('consequently', 0.059), ('gaps', 0.059)]
simIndex simValue blogId blogTitle
same-blog 1 0.99999982 357 high scalability-2008-07-26-Google's Paxos Made Live – An Engineering Perspective
Introduction: This is an unusually well written and useful paper . It talks in detail about experiences implementing a complex project, something we don't see very often. They shockingly even admit that creating a working implementation of Paxos was more difficult than just translating the pseudo code. Imagine that, programmers aren't merely typists! I particularly like the explanation of the Paxos algorithm and why anyone would care about it, working with disk corruption, using leases to support simultaneous reads, using epoch numbers to indicate a new master election, using snapshots to prevent unbounded logs, using MultiOp to implement database transactions, how they tested the system, and their openness with the various problems they had. A lot to learn here. From the paper: We describe our experience building a fault-tolerant data-base using the Paxos consensus algorithm. Despite the existing literature in the field, building such a database proved to be non-trivial. We describe selected alg
2 0.22343262 1243 high scalability-2012-05-10-Paper: Paxos Made Moderately Complex
Introduction: If you are a normal human being and find the Paxos protocol confusing, then this paper, Paxos Made Moderately Complex , is a great find. Robbert van Renesse from Cornell University has written a clear and well written paper with excellent explanations. The Abstract: For anybody who has ever tried to implement it, Paxos is by no means a simple protocol, even though it is based on relatively simple invariants. This paper provides imperative pseudo-code for the full Paxos (or Multi-Paxos) protocol without shying away from discussing various implementation details. The initial description avoids optimizations that complicate comprehension. Next we discuss liveness, and list various optimizations that make the protocol practical. Related Articles Paxos on HighScalability.com
3 0.21139561 529 high scalability-2009-03-10-Paper: Consensus Protocols: Paxos
Introduction: Update: Barbara Liskov’s Turing Award, and Byzantine Fault Tolerance . Henry Robinson has created an excellent series of articles on consensus protocols. We already covered his 2 Phase Commit article and he also has a 3 Phase Commit article showing how to handle 2PC under single node failures. But that is not enough! 3PC works well under node failures, but fails for network failures. So another consensus mechanism is needed that handles both network and node failures. And that's Paxos . Paxos correctly handles both types of failures, but it does this by becoming inaccessible if too many components fail. This is the "liveness" property of protocols. Paxos waits until the faults are fixed. Read queries can be handled, but updates will be blocked until the protocol thinks it can make forward progress. The liveness of Paxos is primarily dependent on network stability. In a distributed heterogeneous environment you are at risk of losing the ability to make updates. Users hate t
4 0.19371779 1374 high scalability-2012-12-18-Georeplication: When Bad Things Happen to Good Systems
Introduction: Georeplication is one of the standard techniques for dealing when bad things--failure and latency--happen to good systems. The problem is always: how do you do that? Murat Demirbas , Associate Professor at SUNY Buffalo, has a couple of really good posts that can help: MDCC: Multi-Data Center Consistency and Making Geo-Replicated Systems Fast as Possible, Consistent when Necessary . In MDCC: Multi-Data Center Consistency Murat discusses a paper that says synchronous wide-area replication can be feasible. There's a quick and clear explanation of Paxos and various optimizations that is worth the price of admission. We find that strong consistency doesn't have to be lost across a WAN: The good thing about using Paxos over the WAN is you /almost/ get the full CAP (all three properties: consistency, availability, and partition-freedom). As we discussed earlier (Paxos taught), Paxos is CP, that is, in the presence of a partition, Paxos keeps consistency over availability. But, P
5 0.17992176 510 high scalability-2009-02-09-Paper: Consensus Protocols: Two-Phase Commit
Introduction: Henry Robinson has created an excellent series of articles on consensus protocols. Henry starts with a very useful discussion of what all this talk about consensus really means: The consensus problem is the problem of getting a set of nodes in a distributed system to agree on something - it might be a value, a course of action or a decision. Achieving consensus allows a distributed system to act as a single entity, with every individual node aware of and in agreement with the actions of the whole of the network. In this article Henry tackles Two-Phase Commit, the protocol most databases use to arrive at a consensus for database writes. The article is very well written with lots of pretty and informative pictures. He did a really good job. In conclusion we learn 2PC is very efficient, a minimal number of messages are exchanged and latency is low. The problem is when a co-ordinator fails availability is dramatically reduced. This is why 2PC isn't generally used on highly distributed
6 0.1733937 710 high scalability-2009-09-20-PaxosLease: Diskless Paxos for Leases
7 0.14224249 1345 high scalability-2012-10-22-Spanner - It's About Programmers Building Apps Using SQL Semantics at NoSQL Scale
8 0.14134064 1451 high scalability-2013-05-03-Stuff The Internet Says On Scalability For May 3, 2013
9 0.12472314 507 high scalability-2009-02-03-Paper: Optimistic Replication
10 0.11551641 687 high scalability-2009-08-24-How Google Serves Data from Multiple Datacenters
11 0.10790115 1305 high scalability-2012-08-16-Paper: A Provably Correct Scalable Concurrent Skip List
12 0.10586502 1498 high scalability-2013-08-07-RAFT - In Search of an Understandable Consensus Algorithm
13 0.10380463 1527 high scalability-2013-10-04-Stuff The Internet Says On Scalability For October 4th, 2013
14 0.098267891 1529 high scalability-2013-10-08-F1 and Spanner Holistically Compared
15 0.098115683 527 high scalability-2009-03-06-Cloud Programming Directly Feeds Cost Allocation Back into Software Design
16 0.094320893 1459 high scalability-2013-05-16-Paper: Warp: Multi-Key Transactions for Key-Value Stores
17 0.089169249 575 high scalability-2009-04-21-Thread Pool Engine in MS CLR 4, and Work-Stealing scheduling algorithm
18 0.088764474 233 high scalability-2008-01-30-How Rackspace Now Uses MapReduce and Hadoop to Query Terabytes of Data
19 0.08468537 920 high scalability-2010-10-15-Troubles with Sharding - What can we learn from the Foursquare Incident?
20 0.08428663 705 high scalability-2009-09-16-Paper: A practical scalable distributed B-tree
topicId topicWeight
[(0, 0.153), (1, 0.078), (2, -0.006), (3, 0.048), (4, 0.035), (5, 0.079), (6, 0.018), (7, -0.011), (8, -0.067), (9, 0.014), (10, -0.004), (11, 0.031), (12, -0.042), (13, -0.053), (14, 0.049), (15, 0.005), (16, 0.041), (17, 0.004), (18, 0.029), (19, -0.021), (20, 0.074), (21, 0.014), (22, -0.06), (23, 0.053), (24, -0.077), (25, -0.01), (26, -0.005), (27, 0.016), (28, 0.01), (29, -0.009), (30, -0.044), (31, 0.002), (32, -0.085), (33, -0.002), (34, -0.056), (35, -0.068), (36, -0.033), (37, -0.023), (38, 0.076), (39, 0.027), (40, -0.074), (41, 0.041), (42, -0.002), (43, 0.019), (44, -0.001), (45, 0.003), (46, -0.007), (47, 0.039), (48, 0.005), (49, -0.051)]
simIndex simValue blogId blogTitle
same-blog 1 0.93149149 357 high scalability-2008-07-26-Google's Paxos Made Live – An Engineering Perspective
Introduction: This is an unusually well written and useful paper . It talks in detail about experiences implementing a complex project, something we don't see very often. They shockingly even admit that creating a working implementation of Paxos was more difficult than just translating the pseudo code. Imagine that, programmers aren't merely typists! I particularly like the explanation of the Paxos algorithm and why anyone would care about it, working with disk corruption, using leases to support simultaneous reads, using epoch numbers to indicate a new master election, using snapshots to prevent unbounded logs, using MultiOp to implement database transactions, how they tested the system, and their openness with the various problems they had. A lot to learn here. From the paper: We describe our experience building a fault-tolerant data-base using the Paxos consensus algorithm. Despite the existing literature in the field, building such a database proved to be non-trivial. We describe selected alg
2 0.83774567 1243 high scalability-2012-05-10-Paper: Paxos Made Moderately Complex
Introduction: If you are a normal human being and find the Paxos protocol confusing, then this paper, Paxos Made Moderately Complex , is a great find. Robbert van Renesse from Cornell University has written a clear and well written paper with excellent explanations. The Abstract: For anybody who has ever tried to implement it, Paxos is by no means a simple protocol, even though it is based on relatively simple invariants. This paper provides imperative pseudo-code for the full Paxos (or Multi-Paxos) protocol without shying away from discussing various implementation details. The initial description avoids optimizations that complicate comprehension. Next we discuss liveness, and list various optimizations that make the protocol practical. Related Articles Paxos on HighScalability.com
3 0.82361931 1273 high scalability-2012-06-27-Paper: Logic and Lattices for Distributed Programming
Introduction: Neil Conway from Berkeley CS is giving an advanced level talk at a meetup today in San Francisco on a new paper: Logic and Lattices for Distributed Programming - extending set logic to support CRDT-style lattices. The description of the meetup is probably the clearest introduction to the paper: Developers are increasingly choosing datastores that sacrifice strong consistency guarantees in exchange for improved performance and availability. Unfortunately, writing reliable distributed programs without the benefit of strong consistency can be very challenging. In this talk, I'll discuss work from our group at UC Berkeley that aims to make it easier to write distributed programs without relying on strong consistency. Bloom is a declarative programming language for distributed computing, while CALM is an analysis technique that identifies programs that are guaranteed to be eventually consistent. I'll then discuss our recent work on extending CALM to support a broader range of
4 0.81068182 507 high scalability-2009-02-03-Paper: Optimistic Replication
Introduction: To scale in the large you have to partition. Data has to be spread around, replicated, and kept consistent (keeping replicas sufficiently similar to one another despite operations being submitted independently at different sites). The result is a highly available, well performing, and scalable system. Partitioning is required, but it's a pain to do efficiently and correctly. Until Quantum teleportation becomes a reality how data is kept consistent across a bewildering number of failure scenarios is a key design decision. This excellent paper by Yasushi Saito and Marc Shapiro takes us on a wild ride (OK, maybe not so wild) of different approaches to achieving consistency. What's cool about this paper is they go over some real systems that we are familiar with and cover how they work: DNS (single-master, state-transfer), Usenet (multi-master), PDAs (multi-master, state-transfer, manual or application-specific conflict resolution), Bayou (multi-master, operation-transfer, epidemic
5 0.76785606 844 high scalability-2010-06-18-Paper: The Declarative Imperative: Experiences and Conjectures in Distributed Logic
Introduction: The Declarative Imperative: Experiences and Conjectures in Distributed Logic is written by UC Berkeley's Joseph Hellerstein for a keynote speech he gave at PODS . The video version of the talk is here . You may have heard about Mr. Hellerstein through the Berkeley Orders Of Magnitude project ( BOOM ), whose purpose is to help people build systems that are OOM (orders of magnitude) bigger than are building today, with OOM less effort than traditional programming methodologies . A noble goal which may be why BOOM was rated as a top 10 emerging technology for 2010 by MIT Technology Review . Quite an honor. The motivation for the talk is a familiar one: it's a dark period for computer programming and if we don't learn how to write parallel programs the children of Moore's law will destroy us all. We have more and more processors, yet we are stuck on figuring out how the average programmer can exploit them. The BOOM solution is the Bloom language which is based on Dedalus:
6 0.76778835 963 high scalability-2010-12-23-Paper: CRDTs: Consistency without concurrency control
7 0.75265282 890 high scalability-2010-09-01-Paper: The Case for Determinism in Database Systems
8 0.74860704 705 high scalability-2009-09-16-Paper: A practical scalable distributed B-tree
9 0.74391484 529 high scalability-2009-03-10-Paper: Consensus Protocols: Paxos
10 0.73869503 510 high scalability-2009-02-09-Paper: Consensus Protocols: Two-Phase Commit
11 0.72240889 1463 high scalability-2013-05-23-Paper: Calvin: Fast Distributed Transactions for Partitioned Database Systems
12 0.71736801 1498 high scalability-2013-08-07-RAFT - In Search of an Understandable Consensus Algorithm
13 0.71025711 1374 high scalability-2012-12-18-Georeplication: When Bad Things Happen to Good Systems
14 0.70680463 1146 high scalability-2011-11-23-Paper: Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS
15 0.7057696 1459 high scalability-2013-05-16-Paper: Warp: Multi-Key Transactions for Key-Value Stores
16 0.70079362 1305 high scalability-2012-08-16-Paper: A Provably Correct Scalable Concurrent Skip List
17 0.69965482 958 high scalability-2010-12-16-7 Design Patterns for Almost-infinite Scalability
18 0.69009179 1629 high scalability-2014-04-10-Paper: Scalable Atomic Visibility with RAMP Transactions - Scale Linearly to 100 Servers
19 0.68921423 1299 high scalability-2012-08-06-Paper: High-Performance Concurrency Control Mechanisms for Main-Memory Databases
20 0.68091685 1611 high scalability-2014-03-12-Paper: Scalable Eventually Consistent Counters over Unreliable Networks
topicId topicWeight
[(1, 0.121), (2, 0.193), (10, 0.052), (30, 0.025), (40, 0.033), (47, 0.018), (51, 0.024), (61, 0.099), (79, 0.104), (85, 0.024), (92, 0.12), (94, 0.094)]
simIndex simValue blogId blogTitle
1 0.96781874 352 high scalability-2008-07-18-Robert Scoble's Rules for Successfully Scaling Startups
Introduction: Robert Scoble in an often poignant FriendFeed thread commiserating PodTech's unfortunate end, shared what he learned about creating a successful startup. Here's a summary of a Robert's rules and why Machiavelli just may agree with them: Have a story. Have everyone on board with that story. If anyone goes off of that story, make sure they get on board immediately or fire them. Make sure people are judged by the revenues they bring in. Those that bring in revenues should get to run the place. People who don't bring in revenues should get fewer and fewer responsibilities, not more and more. Work ONLY for a leader who will make the tough decisions. Build a place where excellence is expected, allowed, and is enabled. Fire idiots quickly. If your engineering team can't give a media team good measurements, the entire company is in trouble. Only things that are measured ever get improved. When your stars aren't listened to the company is in trouble. Getting rid of t
2 0.94964904 1636 high scalability-2014-04-23-Here's a 1300 Year Old Solution to Resilience - Rebuild, Rebuild, Rebuild
Introduction: How is it possible that a wooden Shinto shrine built in the 7th century is still standing? The answer depends on how you answer this philosophical head scratcher: With nearly every cell in your body continually being replaced, are you still the same person? The Ise Grand Shrine has been in continuous existence for over 1300 years because every twenty years an exact replica has been rebuilt on an adjacent footprint. The former temple is then dismantled. Now that's resilience. If you want something to last make it a living part of a culture. It's not so much the building that is remade, what is rebuilt and passed down from generation to generation is the meme that the shrine is important and worth preserving. The rest is an unfolding of that imperative. You can see echoes of this same process in Open Source projects like Linux and the libraries and frameworks that get themselves reconstructed in each new environment. The patterns of recurrence in software are the result of Darw
same-blog 3 0.93255973 357 high scalability-2008-07-26-Google's Paxos Made Live – An Engineering Perspective
Introduction: This is an unusually well written and useful paper . It talks in detail about experiences implementing a complex project, something we don't see very often. They shockingly even admit that creating a working implementation of Paxos was more difficult than just translating the pseudo code. Imagine that, programmers aren't merely typists! I particularly like the explanation of the Paxos algorithm and why anyone would care about it, working with disk corruption, using leases to support simultaneous reads, using epoch numbers to indicate a new master election, using snapshots to prevent unbounded logs, using MultiOp to implement database transactions, how they tested the system, and their openness with the various problems they had. A lot to learn here. From the paper: We describe our experience building a fault-tolerant data-base using the Paxos consensus algorithm. Despite the existing literature in the field, building such a database proved to be non-trivial. We describe selected alg
4 0.93202287 839 high scalability-2010-06-09-Paper: Propagation Networks: A Flexible and Expressive Substrate for Computation
Introduction: Alexey Radul in his fascinating 174 page dissertation Propagation Networks: A Flexible and Expressive Substrate for Computation , offers to help us break free of the tyranny of linear time by arranging computation as a network of autonomous but interconnected machines . We can do this by organizing computation as a network of interconnected machines of some kind, each of which is free to run when it pleases, propagating information around the network as proves possible. The consequence of this freedom is that the structure of the aggregate does not impose an order of time. The abstract from his thesis is : In this dissertation I propose a shift in the foundations of computation. Modern programming systems are not expressive enough. The traditional image of a single computer that has global effects on a large memory is too restrictive. The propagation paradigm replaces this with computing by networks of local, independent, stateless machines interconnected with stateful storage
5 0.91583329 988 high scalability-2011-02-11-Stuff The Internet Says On Scalability For February 11, 2011
Introduction: Submitted for your reading pleasure... A good night's sleep is why Facebook CTO Bret Taylor says Friendfeed should have gone cloud , let others take the midnight watch, even if it costs a bit more. James Urquhart with an information packed interview on a wide range of cloud topics: Cloud Expert Inside theCube at Stata Conference . Highlights: cloud is an operations model, it is not a technology, it is a way to apply technology to problems; the faster you can get the resources into the hands of the people who use it the more money you save overall; cloud is a cash flow story, not a savings story; services aren't about servers or storage, they are about applications. Quotable Quotes: Ryan Tomayko: Frameworks don’t solve scalability problems, design solves scalability problems. Via @GregSkloot @zuno : The golden rule of scalability: "it can probably wait" look for other areas to save resources. @bihzad : joinserv hit a scalability wall, but I'm pretty s
6 0.91341096 1180 high scalability-2012-01-24-The State of NoSQL in 2012
7 0.9095518 532 high scalability-2009-03-11-Sharding and Connection Pools
8 0.90332401 301 high scalability-2008-04-08-Google AppEngine - A First Look
9 0.90320277 1649 high scalability-2014-05-16-Stuff The Internet Says On Scalability For May 16th, 2014
10 0.8998239 1402 high scalability-2013-02-07-Ask HighScalability: Web asset server concept - 3rd party software available?
11 0.89976221 528 high scalability-2009-03-06-Product: Lightcloud - Key-Value Database
12 0.89910799 976 high scalability-2011-01-20-75% Chance of Scale - Leveraging the New Scaleogenic Environment for Growth
13 0.89865607 517 high scalability-2009-02-21-Google AppEngine - A Second Look
14 0.89855772 1516 high scalability-2013-09-13-Stuff The Internet Says On Scalability For September 13, 2013
15 0.89766395 645 high scalability-2009-06-30-Hot New Trend: Linking Clouds Through Cheap IP VPNs Instead of Private Lines
16 0.89583623 1112 high scalability-2011-09-07-What Google App Engine Price Changes Say About the Future of Web Architecture
17 0.89570397 266 high scalability-2008-03-04-Manage Downtime Risk by Connecting Multiple Data Centers into a Secure Virtual LAN
18 0.89551806 776 high scalability-2010-02-12-Hot Scalability Links for February 12, 2010
19 0.89430845 885 high scalability-2010-08-23-Building a Scalable Key-Value Database: Project Hydracus
20 0.89429432 980 high scalability-2011-01-28-Stuff The Internet Says On Scalability For January 28, 2011