From b2870df267d95cf93754165ced84e2be4cbfe50a Mon Sep 17 00:00:00 2001 From: James Larisch Date: Thu, 17 Nov 2016 17:30:00 -0500 Subject: FIRST DRAFT --- chapter/7/langs-consistency.md | 115 +++++++++++++++++++++++++++++++++++++++-- 1 file changed, 111 insertions(+), 4 deletions(-) (limited to 'chapter') diff --git a/chapter/7/langs-consistency.md b/chapter/7/langs-consistency.md index 3ac6ceb..6eddfc5 100644 --- a/chapter/7/langs-consistency.md +++ b/chapter/7/langs-consistency.md @@ -1,11 +1,118 @@ --- layout: page -title: "Languages for Consistency" -by: "Joe Schmoe and Mary Jane" +title: "Languages Built For Consistency" +by: "James Larisch" --- +# Languages Built For Consistency + +## What's the problem? + As processors become expensive and the limits of Moore's Law are pushed, programmers lately find themselves in situations where they need to connect multiple computers together using a network cable. Perhaps it's not even due to cost or performance constraints; perhaps your company has servers in New York and San Fransisco, and there is some global state that requires synchronization across the country. Problems requiring solutions of this nature can be described as "distributed systems" problems. Your data / processing power / entry points are distributed for some reason. In many ways, web developers deal with distributed systems problems every day: your client and your server are in two different geographical locations, and thus, some coordination is required. + + As Aviral discussed in the previous section, many computer scientists have done a lot of thinking about the nature of distributed systems problems. As such, we realize that it's impossible to completely emulate the behavior of a single computational machine using multiple machines. For example, the network simply is not reliable - and if we wait for it to be reliable, we sacrifice things like timeliness. After discussing the Consistency/Availability/Partition-tolerance theorem, Section 6 discussed how we can make drill down into the CAP pyramid and choose the properties of our systems. As stated, we can't perfectly emulate a single computer, but once we accept that fact... there are plenty of things we *can* do! + +## The Shopping Cart + Let's bring all these theorem talk back to reality. Let's say you're working at a new e-commerce startup, and you'd like to revolutionize the electronic shopping cart. You'd like to give the customer the ability to do the following: + * Log in to the site and add a candle to the cart while traveling Beijing. + * Take a HyperLoop train (3 hours) from Beijing to Los Angeles. + * Log back into the site, remove the candle from their cart, and add a skateboard to their cart. + * Take another HyperLoop train from Los Angeles to Paris (5 hours). + * Log back into the site, add another skateboard, and checkout. + + Let's assume you have a server in every single country, and customers connect to the geographically closest server. + + If you only had 1 user of your website, this wouldn't be too hard. You could constantly send out messages to all of your servers and personally make sure the state of the customer's shopping cart is consistent across every single server. But what happens when you have millions of customers and thus millions of shopping carts? That would be impossible to keep track of personally. Luckily, you're a programmer - this can be automated! You simply need to make sure that all of your computers stay i-sync, so if the customer checks her cart in Beijing, then in Paris, she sees the same thing. + + But as Section 6 already explained, this is not so trivial. Messages between your servers in Beijing and Paris could get dropped, corrupted, reordered, duplicated, or delayed. Since you have no guarantees about when you'll be able to synchronize state between two servers, it's possible that the customer could see two different cart-states depending on which server she asks. + + If you're confident that the servers' state will eventually converge, you could present the user with an error message until the states have converged. That way, you know the user is looking at consistent state. [I may be overlapping too much with Aviral's section here. will wait until I see his draft before continuing. + + Mention Amazon's Dynamo + shopping cart. + +### Example + + Let's take a look at the following Javascript. For simplicity's sake, let's pretend users can only add things to their shopping cart. + + ```javascript + class Cart { + constructor(peers, socket) { + this.mySocket = socket; + this.peers = peers; + this.items = new Set(); + } + + addItem(item) { + this.items.add(item); + } + + synchronize() { + peers.forEach(function(peer) { + peer.send(items); + }); + } + + receiveState(items) { + this.items = this.items.union(items); + } + + run() { + var clientAddition = Interface.receiveInput(); // contrived + this.addItem(clientAddition); + var receivedState = mySocket.nonBlockingRead(); // contrived + if (receivedState !== undefined) { + this.receiveState(receivedState); + } + synchronize(); + sleep(10); + run(); + } + } + + // theoretical usage + + var socket = new UDPSocket(); // contrived + var cart = new Cart(peerSockets, socket); // peerSockets is an array of UDP sockets + cart.run(); + ``` + + Here is an (almost) fully functional shopping cart program. You can imagine this code running across multiple nodes scattered over the world. The meat of the program lies in the `run()` method. Let's walk through that: + 1. Program receives an addition to the cart from the user. + 2. Program adds that item to the current local state. + 3. Program checks its UDP socket for any messages. + 4. If it received one, it's means another instance of this program has sent us its state. What is state in this case? Simply a set of cart items. Let's handle this set of items by unioning it with our current set. + 5. Synchronize our current state by sending our state to every peer that we know about. + 6. Sleep for 10 seconds. + 7. Repeat! + + Hopefully it's clear that if a client adds an item to her cart in Beijing and then 10 seconds later checks her cart in Paris, she should see the same thing. Well, not exactly - remember, the network is unreliable, and Beijing's `synchronize` messages might have been dropped. But no worries! Beijing is `synchronizing` again in another 10 seconds. + + This is the *Strong Eventual Consistency* concept that Aviral introduced in Section 6. It's *eventual* because given a long enough timeline the clients' states will sync up: they are constantly trying to synchronize. [mention you can't remove things trivially, this is actually a CRDT, union is a monotonic operation] + +### The Intern + Unfortunately Jerry, the intern, has found your code. He'd like to make a few changes. He messes it up somehow. I'm not entirely sure how yet. + +### Guarantees + The original Javascript we wrote down exhibits the property from Section 6 known as *monotonicity*. The union operation ensures that a given node's state is always "greater than or equal to" the states of the other nodes. However, how can we be *sure* that this property is maintained throughout the development of this program? As we've seen, there's nothing stopping an intern from coming along, making a mindless change, and destroying this wonderful property. Ideally, we want to make it impossible (or at least very difficult) to write programs that violate this property. Or, at the very least, we want to make it very easy to write programs that maintain these types of properties. + + But where should these guarantees live? In the above Javascript example, the guarantees aren't guarantees at all, really. There's no restriction on what the programmer is allowed to do - the programmer has simply constructed a program that mirrors guarantees that she has modeled in her brain. In order to maintain properties such as *monotonicity*, she must constantly check the model in her brain against the code. We haven't really helped the programmer out that much - she has a lot of thinking to do. + + At the disk hardward level, there are certain mechanisms in place to ensure that data does not become corrupted when multiple things attempt to write bits to the same physical location. This is considered a type of IO-consistency. It doesn't help much with our shopping cart, but it's certainly necessary. These important guarantees facilitate the higher level abstractions by ensuring low-level safety. It would be unreasonable to expect our disks to enforce monotonicity, for example, since this would restrict usage of disks to monotonic programs only (more on this later!). But on the other hand, as we've seen, pushing the consistency to the application/programmer level is also unreasonable. Our tools should work for us. + + Why not push the consistency guarantees in between? Is there any reason why you as the programmer couldn't program using tools that facilitate these types of monotonic programs? If you're familiar with formal systems -- why not construct a formal system (programming language / library) in which every theorem (program) is formally guarunteed to be monotonic? If it's *impossible* to express a non-monotonic program, the programmer needn't worry about maintaining a direct mapping between their code and their mental model. + + Wouldn't it be great if tools like this existed? + +### Bloom + The dudes/dudettes at Berkeley seem to think so too. + +#### Restriction & Danger + [Bloom restricts you, it's different, and it's dangerous] + +### Lasp + [Library not language, embeddable, not dangerous] + Instead of trying to do it all (and accepting danger), it tries to be embeddable (and truly restrictive.) + -Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. {% cite Uniqueness --file langs-consistency %} ## References -{% bibliography --file langs-consistency %} \ No newline at end of file +{% bibliography --file langs-consistency %} -- cgit v1.2.3 From f9a6cc50e91d4adc1817715fb265874eb7cb253a Mon Sep 17 00:00:00 2001 From: James Larisch Date: Fri, 9 Dec 2016 19:42:03 -0500 Subject: Dynamo --- chapter/7/langs-consistency.md | 61 +++++++++++++++++++++++++++++++++--------- 1 file changed, 48 insertions(+), 13 deletions(-) (limited to 'chapter') diff --git a/chapter/7/langs-consistency.md b/chapter/7/langs-consistency.md index 6eddfc5..3de0848 100644 --- a/chapter/7/langs-consistency.md +++ b/chapter/7/langs-consistency.md @@ -1,32 +1,67 @@ --- layout: page -title: "Languages Built For Consistency" +title: "Formal, Yet Relaxed: Models for Consistency" by: "James Larisch" --- -# Languages Built For Consistency +# Formal, Yet Relaxed: Models for Consistency ## What's the problem? - As processors become expensive and the limits of Moore's Law are pushed, programmers lately find themselves in situations where they need to connect multiple computers together using a network cable. Perhaps it's not even due to cost or performance constraints; perhaps your company has servers in New York and San Fransisco, and there is some global state that requires synchronization across the country. Problems requiring solutions of this nature can be described as "distributed systems" problems. Your data / processing power / entry points are distributed for some reason. In many ways, web developers deal with distributed systems problems every day: your client and your server are in two different geographical locations, and thus, some coordination is required. + As processors become expensive and the limits of Moore's Law are pushed, programmers find themselves in situations where they need to connect multiple computers together using a network cable. Perhaps it's not even due to cost or performance constraints; perhaps your company has servers in New York and San Fransisco, and there is some global state that requires synchronization across the country. Problems requiring solutions of this nature can be described as "distributed systems" problems. Your data / processing power / entry points are distributed for some reason. In many ways, web developers deal with distributed systems problems every day: your client and your server are in two different geographical locations, and thus, some coordination is required. - As Aviral discussed in the previous section, many computer scientists have done a lot of thinking about the nature of distributed systems problems. As such, we realize that it's impossible to completely emulate the behavior of a single computational machine using multiple machines. For example, the network simply is not reliable - and if we wait for it to be reliable, we sacrifice things like timeliness. After discussing the Consistency/Availability/Partition-tolerance theorem, Section 6 discussed how we can make drill down into the CAP pyramid and choose the properties of our systems. As stated, we can't perfectly emulate a single computer, but once we accept that fact... there are plenty of things we *can* do! + As Aviral discussed in the previous section, many computer scientists have done a lot of thinking about the nature of distributed systems problems. As such, we realize that it's impossible to completely emulate the behavior of a single computational machine using multiple machines. For example, the network is simply not as reliable as, say, memory - and waiting for responses can result in a lack of timeliness for the application's client. After discussing the Consistency/Availability/Partition-tolerance theorem, Section 6 discussed how we can make drill down into the CAP pyramid and choose the properties of our systems. As stated, we can't perfectly emulate a single computer using multiple machines, but once we accept that fact and learn to work with it... there are plenty of things we *can* do! ## The Shopping Cart Let's bring all these theorem talk back to reality. Let's say you're working at a new e-commerce startup, and you'd like to revolutionize the electronic shopping cart. You'd like to give the customer the ability to do the following: - * Log in to the site and add a candle to the cart while traveling Beijing. - * Take a HyperLoop train (3 hours) from Beijing to Los Angeles. - * Log back into the site, remove the candle from their cart, and add a skateboard to their cart. - * Take another HyperLoop train from Los Angeles to Paris (5 hours). - * Log back into the site, add another skateboard, and checkout. + 1. Log in to the site and add a candle to the cart while traveling in Beijing. + 1. Take a HyperLoop (3 hours) from Beijing to Los Angeles. + 1. Log back in, remove the candle from the cart, and add a skateboard. + 1. Take another HyperLoop train from Los Angeles to Paris (5 hours). + 1. Log back into the site, add another skateboard, and checkout. Let's assume you have a server in every single country, and customers connect to the geographically closest server. - If you only had 1 user of your website, this wouldn't be too hard. You could constantly send out messages to all of your servers and personally make sure the state of the customer's shopping cart is consistent across every single server. But what happens when you have millions of customers and thus millions of shopping carts? That would be impossible to keep track of personally. Luckily, you're a programmer - this can be automated! You simply need to make sure that all of your computers stay i-sync, so if the customer checks her cart in Beijing, then in Paris, she sees the same thing. + How can we ensure that the client sees the same cart at every point in her trip? - But as Section 6 already explained, this is not so trivial. Messages between your servers in Beijing and Paris could get dropped, corrupted, reordered, duplicated, or delayed. Since you have no guarantees about when you'll be able to synchronize state between two servers, it's possible that the customer could see two different cart-states depending on which server she asks. + If you only had one user of your website, this wouldn't be too hard. You could manually, constantly modify and check on all of your servers and personally make sure the state of the customer's shopping cart is consistent across every single server. But what happens when you have millions of customers and thus millions of shopping carts? That would be impossible to keep track of personally. Luckily, you're a programmer - this can be automated! You simply need to make sure that all of your computers stay in-sync, so if the customer checks her cart in Beijing, then in Paris, she sees the same thing. - If you're confident that the servers' state will eventually converge, you could present the user with an error message until the states have converged. That way, you know the user is looking at consistent state. [I may be overlapping too much with Aviral's section here. will wait until I see his draft before continuing. + But as Section 6 already explained, this is not so trivial. Messages between your servers in Beijing and Paris could get dropped, corrupted, reordered, duplicated, or delayed. Servers can crash. Sharks can cut the network cables between countries. Since you have no guarantees about when you'll be able to synchronize state between two servers, it's possible that the customer could see two different cart-states depending on which country she's in (which server she asks). - Mention Amazon's Dynamo + shopping cart. + It's possible to implement "consensus" protocols that provide coordination between your machines. When failure happens, such as a network shark-attack, the protocol detects a lack of consistency and becomes *unavailable*. For some applications, this is appropriate. For a shopping cart, this seems like overkill. If our shopping cart distributed systems experienced a failure, it means users would not be able to add or remove things from the cart. They also couldn't check out. This means our startup would lose money! Perhaps it's not so important that our clients' shopping carts be completely synchronized across the entire world at all times. After all, how often are people going to be doing such wanderlust shopping? + + This is an important moment. By thinking about our specific problem, we've realized a compromise we're willing to make: our users always need to be able to add things, remove things, and checkout. In other words, our service needs to be *available*. Servers don't necessarily need to agree all the time. We'd like them to, but the system shouldn't shut down if they don't. We'll find a way to deal with it. + + Turns out there's a company out there called Amazon.com - and they've been having a similar problem. Amazon sells things on their website too, and users can add and remove things from their cart. Amazon has lots of servers spread out across the world. They also have quite a few customers. They need to ensure their customers' carts are robust: if/when servers fail or lose communication with one another, a "best-effort" should be made to display the customer's cart. Amazon acknowledges that failure, latency, or HyperLoop-traveling users can cause inconsistent cart data, depending on which server you ask. How does Amazon resolve these issues? + +## Dynamo + Amazon built DynamoDB, which is basically a big distributed hash table. In other words, it's a hashmap spread across multiple computers. A user's cart would be stored as a value under the user's username as the key. When a user adds a new item to her cart, the cart data is replicated across a multiple machines within the network. If the client changes locations and performs another write or a few machines fail and later recover, it's possible for different machines to have different opinions about the state of a given user's cart. + + Dynamo has a rather unique way of dealing with these types of conflicts. Since Dynamo always wants to be available for both writes and reads (add/removes, viewing/checkouts, resp) it must have a way of combining inconsistent data. Dynamo chooses to perform this resolution at read time. When a client performs a `get()` on the user's cart, Dynamo will take the multiple conflicting carts...aaaaaand... push it all up to the application! Huh? I thought Dynamo resolves this for the programmer!? Actually, Dynamo is a generic key-value store. It detects inconsistencies in the data - but once it does, it simply tells the application (in this case the application is the shopping cart code) that there are some conflicts. The application (shopping cart, in this case) is free to resolve these inconsistencies as it pleases. + + How should Amazon's shopping cart procede with resolution? It may be fed two cart states like so: + + ``` + James's Cart V1 | James's Cart V2 + ----------------------------------- + Red Candle | Red Candle + Blue Skateboard | Green Umbrella + ``` + + Amazon doesn't want to accidently *remove* anything from your cart, so it errs on the side of inclusion. If given this particular conflict, you would see: + + ``` + James's Cart + ------------ + Red Candle + Blue Skateboard + Green Umbrella + ``` + + It's important to understand that Amazon has multiple machines storing the contents of your cart. These machines are asynchronously communicating in order to tell each other about updates they've received. Conflicts like this can happen when you try to read before the nodes have had time to gossip about your cart. More likely, however, is the situation in which one of the machines holding your cart goes offline and missing some updates. When it comes back online, you try to read, and this resolution process must occur. + + + + + Unfortunately Amazon has a leg up on our startup. Their programmers have figured out a way to add multiple instances of a single item into the cart. Users on our website can only add one "Red Candle"" to their shopping cart. [This is due to a fundamental limitation in the type of CRDT I chose to exemplify. It's quite possible to have a fully functional cart. Take a look at LWW-Sets.] ### Example -- cgit v1.2.3 From 367377b63bcd32848d0d44d7a3dd85fe429f8143 Mon Sep 17 00:00:00 2001 From: James Larisch Date: Fri, 9 Dec 2016 21:03:21 -0500 Subject: Examples --- chapter/7/langs-consistency.md | 91 +++++++++++++++++++++++++++++++++++++----- 1 file changed, 81 insertions(+), 10 deletions(-) (limited to 'chapter') diff --git a/chapter/7/langs-consistency.md b/chapter/7/langs-consistency.md index 3de0848..4584fd2 100644 --- a/chapter/7/langs-consistency.md +++ b/chapter/7/langs-consistency.md @@ -26,7 +26,7 @@ by: "James Larisch" But as Section 6 already explained, this is not so trivial. Messages between your servers in Beijing and Paris could get dropped, corrupted, reordered, duplicated, or delayed. Servers can crash. Sharks can cut the network cables between countries. Since you have no guarantees about when you'll be able to synchronize state between two servers, it's possible that the customer could see two different cart-states depending on which country she's in (which server she asks). - It's possible to implement "consensus" protocols that provide coordination between your machines. When failure happens, such as a network shark-attack, the protocol detects a lack of consistency and becomes *unavailable*. For some applications, this is appropriate. For a shopping cart, this seems like overkill. If our shopping cart distributed systems experienced a failure, it means users would not be able to add or remove things from the cart. They also couldn't check out. This means our startup would lose money! Perhaps it's not so important that our clients' shopping carts be completely synchronized across the entire world at all times. After all, how often are people going to be doing such wanderlust shopping? + It's possible to implement "consensus" protocols such as Paxos and 3-Phase-Commit that provide coordination between your machines. When failure happens, such as a network shark-attack, the protocol detects a lack of consistency and becomes *unavailable*. For some applications, this is appropriate. For a shopping cart, this seems like overkill. If our shopping cart distributed systems experienced a failure, it means users would not be able to add or remove things from the cart. They also couldn't check out. This means our startup would lose money! Perhaps it's not so important that our clients' shopping carts be completely synchronized across the entire world at all times. After all, how often are people going to be doing such wanderlust shopping? This is an important moment. By thinking about our specific problem, we've realized a compromise we're willing to make: our users always need to be able to add things, remove things, and checkout. In other words, our service needs to be *available*. Servers don't necessarily need to agree all the time. We'd like them to, but the system shouldn't shut down if they don't. We'll find a way to deal with it. @@ -58,10 +58,21 @@ by: "James Larisch" It's important to understand that Amazon has multiple machines storing the contents of your cart. These machines are asynchronously communicating in order to tell each other about updates they've received. Conflicts like this can happen when you try to read before the nodes have had time to gossip about your cart. More likely, however, is the situation in which one of the machines holding your cart goes offline and missing some updates. When it comes back online, you try to read, and this resolution process must occur. +### Good & Bad + What do we love about Dynamo? It's a highly available key-value store. It replicates data well, and according to the paper, has an insanely high uptime and low latency. We love that it's *eventually consistent*. Nodes are constantly gossiping, so given enough time (and assuming failures are resolved), nodes' states will eventually converge. However, this property is *weak*. It's weak because when failures+conflicts occur, and [and they will occur](https://www.youtube.com/watch?v=JG2ESDGwHHY), it's up to the application developer to figure out how to handle it. In the case of the shopping cart, it's relatively trivial. But as a programmer, every time you'd like to use DynamoDB you need to consider your resolution strategy. The database doesn't provide a general solution. + Instead of constructing an all-purpose database and forcing the burden of resolution on programmers, what if we constructed general-purpose data structures that required no manual resolution? These data structures would resolve conflicts inherently, themselves, and depending on your application you could choose which data structure works best for you. + Let's try this transfiguration on the shopping cart. Let's strip it down: how does Amazon handle resolution, really? It treats shopping cart versions as sets of items. In order to perform resolution, Amazon unions the two sets. - Unfortunately Amazon has a leg up on our startup. Their programmers have figured out a way to add multiple instances of a single item into the cart. Users on our website can only add one "Red Candle"" to their shopping cart. [This is due to a fundamental limitation in the type of CRDT I chose to exemplify. It's quite possible to have a fully functional cart. Take a look at LWW-Sets.] + ``` + { Red Candle, Blue Skateboard } U { Red Candle, Green Umbrella } == { Red Candle, Blue Skateboard, Green Umbrella } + ``` + + Cool. Using this knowledge, let's try to construct our own shopping cart that automatically resolves conflicts. + + + (Unfortunately Amazon has a leg up on our startup. Their programmers have figured out a way to add multiple instances of a single item into the cart. Users on our website can only add one "Red Candle"" to their shopping cart. This is due to a fundamental limitation in the type of CRDT I chose to exemplify. It's quite possible to have a fully functional cart. Take a look at LWW-Sets.) ### Example @@ -90,9 +101,11 @@ by: "James Larisch" } run() { - var clientAddition = Interface.receiveInput(); // contrived - this.addItem(clientAddition); - var receivedState = mySocket.nonBlockingRead(); // contrived + var clientAddition = Interface.nonBlockingReceiveInput(); // invented + if (clientAddition !== undefined) { + this.addItem(clientAddition); + } + var receivedState = mySocket.nonBlockingRead(); // invented if (receivedState !== undefined) { this.receiveState(receivedState); } @@ -104,26 +117,84 @@ by: "James Larisch" // theoretical usage - var socket = new UDPSocket(); // contrived + var socket = new UDPSocket(); // invented var cart = new Cart(peerSockets, socket); // peerSockets is an array of UDP sockets cart.run(); + cart.items // the cart's items ``` Here is an (almost) fully functional shopping cart program. You can imagine this code running across multiple nodes scattered over the world. The meat of the program lies in the `run()` method. Let's walk through that: 1. Program receives an addition to the cart from the user. - 2. Program adds that item to the current local state. + 2. Program adds that item to the current local state if it exists. 3. Program checks its UDP socket for any messages. 4. If it received one, it's means another instance of this program has sent us its state. What is state in this case? Simply a set of cart items. Let's handle this set of items by unioning it with our current set. 5. Synchronize our current state by sending our state to every peer that we know about. 6. Sleep for 10 seconds. 7. Repeat! - Hopefully it's clear that if a client adds an item to her cart in Beijing and then 10 seconds later checks her cart in Paris, she should see the same thing. Well, not exactly - remember, the network is unreliable, and Beijing's `synchronize` messages might have been dropped. But no worries! Beijing is `synchronizing` again in another 10 seconds. + W - This is the *Strong Eventual Consistency* concept that Aviral introduced in Section 6. It's *eventual* because given a long enough timeline the clients' states will sync up: they are constantly trying to synchronize. [mention you can't remove things trivially, this is actually a CRDT, union is a monotonic operation] + Hopefully it's clear that if a client adds an item to her cart in Beijing and then 10 seconds later checks her cart in Paris, she should see the same thing. Well, not exactly - remember, the network is unreliable, and Beijing's `synchronize` messages might have been dropped. But no worries! Beijing is `synchronizing` again in another 10 seconds. This should remind you of Dynamo's gossiping: nodes are constantly attempting to converge. + + Both systems are eventually consistent - the difference here is our Javascript shopping cart displays *strong* eventual consistency. It's strong because it requires no specialized resolution. When a node transmits its state to another node, there's absolutely no question about how to integrate that state into the current one. There's no conflict. ### The Intern - Unfortunately Jerry, the intern, has found your code. He'd like to make a few changes. He messes it up somehow. I'm not entirely sure how yet. + Unfortunately Jerry, the intern, has found your code. He'd like to add `remove` functionality to the cart. So he makes the following changes: + + ```javascript + class Cart { + constructor(peers, socket) { + this.mySocket = socket; + this.peers = peers; + this.items = new Set(); + } + + addItem(item) { + this.items.add(item); + } + + synchronize() { + peers.forEach(function(peer) { + peer.send(items); + }); + } + + receiveState(items) { + // JERRY WAS HERE + this.items = this.items.intersection(items); + // END JERRY WAS HERE + } + + run() { + var clientAddition = Interface.nonBlockingReceiveInput(); // invented + if (clientAddition !== undefined) { + this.addItem(clientAddition); + } + // JERRY WAS HERE + var clientDeletion = Interface.nonBlockingReceiveInput(): + if (clientDeletion !== undefined) { + this.items.delete(clientDeletion); + } + // END JERRY WAS HERE + var receivedState = mySocket.nonBlockingRead(); // invented + if (receivedState !== undefined) { + this.receiveState(receivedState); + } + synchronize(); + sleep(10); + run(); + } + } + + // theoretical usage + + var socket = new UDPSocket(); // invented + var cart = new Cart(peerSockets, socket); // peerSockets is an array of UDP sockets + cart.run(); + cart.items // the cart's items + ``` + + Uh-oh. Can you spot the problem? Let's break it down. In the original code, the current node's cart items were *unioned* with the communicating node's cart. Since there was no deletion, ### Guarantees The original Javascript we wrote down exhibits the property from Section 6 known as *monotonicity*. The union operation ensures that a given node's state is always "greater than or equal to" the states of the other nodes. However, how can we be *sure* that this property is maintained throughout the development of this program? As we've seen, there's nothing stopping an intern from coming along, making a mindless change, and destroying this wonderful property. Ideally, we want to make it impossible (or at least very difficult) to write programs that violate this property. Or, at the very least, we want to make it very easy to write programs that maintain these types of properties. -- cgit v1.2.3 From 58eb648a4e803c5e015d765ce5914899f1f374b7 Mon Sep 17 00:00:00 2001 From: James Larisch Date: Fri, 9 Dec 2016 23:46:53 -0500 Subject: Lacking programming language specifics --- chapter/7/langs-consistency.md | 322 +++++++++++++++++++++++------------------ 1 file changed, 184 insertions(+), 138 deletions(-) (limited to 'chapter') diff --git a/chapter/7/langs-consistency.md b/chapter/7/langs-consistency.md index 4584fd2..a77110f 100644 --- a/chapter/7/langs-consistency.md +++ b/chapter/7/langs-consistency.md @@ -18,206 +18,252 @@ by: "James Larisch" 1. Take another HyperLoop train from Los Angeles to Paris (5 hours). 1. Log back into the site, add another skateboard, and checkout. - Let's assume you have a server in every single country, and customers connect to the geographically closest server. +Let's assume you have a server in every single country, and customers connect to the geographically closest server. - How can we ensure that the client sees the same cart at every point in her trip? +How can we ensure that the client sees the same cart at every point in her trip? - If you only had one user of your website, this wouldn't be too hard. You could manually, constantly modify and check on all of your servers and personally make sure the state of the customer's shopping cart is consistent across every single server. But what happens when you have millions of customers and thus millions of shopping carts? That would be impossible to keep track of personally. Luckily, you're a programmer - this can be automated! You simply need to make sure that all of your computers stay in-sync, so if the customer checks her cart in Beijing, then in Paris, she sees the same thing. +If you only had one user of your website, this wouldn't be too hard. You could manually, constantly modify and check on all of your servers and personally make sure the state of the customer's shopping cart is consistent across every single server. But what happens when you have millions of customers and thus millions of shopping carts? That would be impossible to keep track of personally. Luckily, you're a programmer - this can be automated! You simply need to make sure that all of your computers stay in-sync, so if the customer checks her cart in Beijing, then in Paris, she sees the same thing. - But as Section 6 already explained, this is not so trivial. Messages between your servers in Beijing and Paris could get dropped, corrupted, reordered, duplicated, or delayed. Servers can crash. Sharks can cut the network cables between countries. Since you have no guarantees about when you'll be able to synchronize state between two servers, it's possible that the customer could see two different cart-states depending on which country she's in (which server she asks). +But as Section 6 already explained, this is not so trivial. Messages between your servers in Beijing and Paris could get dropped, corrupted, reordered, duplicated, or delayed. Servers can crash. Sharks can cut the network cables between countries. Since you have no guarantees about when you'll be able to synchronize state between two servers, it's possible that the customer could see two different cart-states depending on which country she's in (which server she asks). - It's possible to implement "consensus" protocols such as Paxos and 3-Phase-Commit that provide coordination between your machines. When failure happens, such as a network shark-attack, the protocol detects a lack of consistency and becomes *unavailable*. For some applications, this is appropriate. For a shopping cart, this seems like overkill. If our shopping cart distributed systems experienced a failure, it means users would not be able to add or remove things from the cart. They also couldn't check out. This means our startup would lose money! Perhaps it's not so important that our clients' shopping carts be completely synchronized across the entire world at all times. After all, how often are people going to be doing such wanderlust shopping? +It's possible to implement "consensus" protocols such as Paxos and 3-Phase-Commit that provide coordination between your machines. When failure happens, such as a network shark-attack, the protocol detects a lack of consistency and becomes *unavailable*. For some applications, this is appropriate. For a shopping cart, this seems like overkill. If our shopping cart distributed systems experienced a failure, it means users would not be able to add or remove things from the cart. They also couldn't check out. This means our startup would lose money! Perhaps it's not so important that our clients' shopping carts be completely synchronized across the entire world at all times. After all, how often are people going to be doing such wanderlust shopping? - This is an important moment. By thinking about our specific problem, we've realized a compromise we're willing to make: our users always need to be able to add things, remove things, and checkout. In other words, our service needs to be *available*. Servers don't necessarily need to agree all the time. We'd like them to, but the system shouldn't shut down if they don't. We'll find a way to deal with it. +This is an important moment. By thinking about our specific problem, we've realized a compromise we're willing to make: our users always need to be able to add things, remove things, and checkout. In other words, our service needs to be *available*. Servers don't necessarily need to agree all the time. We'd like them to, but the system shouldn't shut down if they don't. We'll find a way to deal with it. - Turns out there's a company out there called Amazon.com - and they've been having a similar problem. Amazon sells things on their website too, and users can add and remove things from their cart. Amazon has lots of servers spread out across the world. They also have quite a few customers. They need to ensure their customers' carts are robust: if/when servers fail or lose communication with one another, a "best-effort" should be made to display the customer's cart. Amazon acknowledges that failure, latency, or HyperLoop-traveling users can cause inconsistent cart data, depending on which server you ask. How does Amazon resolve these issues? +Turns out there's a company out there called Amazon.com - and they've been having a similar problem. Amazon sells things on their website too, and users can add and remove things from their cart. Amazon has lots of servers spread out across the world. They also have quite a few customers. They need to ensure their customers' carts are robust: if/when servers fail or lose communication with one another, a "best-effort" should be made to display the customer's cart. Amazon acknowledges that failure, latency, or HyperLoop-traveling users can cause inconsistent cart data, depending on which server you ask. How does Amazon resolve these issues? ## Dynamo - Amazon built DynamoDB, which is basically a big distributed hash table. In other words, it's a hashmap spread across multiple computers. A user's cart would be stored as a value under the user's username as the key. When a user adds a new item to her cart, the cart data is replicated across a multiple machines within the network. If the client changes locations and performs another write or a few machines fail and later recover, it's possible for different machines to have different opinions about the state of a given user's cart. +Amazon built DynamoDB, which is basically a big distributed hash table. In other words, it's a hashmap spread across multiple computers. A user's cart would be stored as a value under the user's username as the key. When a user adds a new item to her cart, the cart data is replicated across a multiple machines within the network. If the client changes locations and performs another write or a few machines fail and later recover, it's possible for different machines to have different opinions about the state of a given user's cart. - Dynamo has a rather unique way of dealing with these types of conflicts. Since Dynamo always wants to be available for both writes and reads (add/removes, viewing/checkouts, resp) it must have a way of combining inconsistent data. Dynamo chooses to perform this resolution at read time. When a client performs a `get()` on the user's cart, Dynamo will take the multiple conflicting carts...aaaaaand... push it all up to the application! Huh? I thought Dynamo resolves this for the programmer!? Actually, Dynamo is a generic key-value store. It detects inconsistencies in the data - but once it does, it simply tells the application (in this case the application is the shopping cart code) that there are some conflicts. The application (shopping cart, in this case) is free to resolve these inconsistencies as it pleases. +Dynamo has a rather unique way of dealing with these types of conflicts. Since Dynamo always wants to be available for both writes and reads (add/removes, viewing/checkouts, resp) it must have a way of combining inconsistent data. Dynamo chooses to perform this resolution at read time. When a client performs a `get()` on the user's cart, Dynamo will take the multiple conflicting carts...aaaaaand... push it all up to the application! Huh? I thought Dynamo resolves this for the programmer!? Actually, Dynamo is a generic key-value store. It detects inconsistencies in the data - but once it does, it simply tells the application (in this case the application is the shopping cart code) that there are some conflicts. The application (shopping cart, in this case) is free to resolve these inconsistencies as it pleases. - How should Amazon's shopping cart procede with resolution? It may be fed two cart states like so: +How should Amazon's shopping cart procede with resolution? It may be fed two cart states like so: - ``` - James's Cart V1 | James's Cart V2 - ----------------------------------- - Red Candle | Red Candle - Blue Skateboard | Green Umbrella - ``` +``` +James's Cart V1 | James's Cart V2 +----------------------------------- +Red Candle | Red Candle +Blue Skateboard | Green Umbrella +``` - Amazon doesn't want to accidently *remove* anything from your cart, so it errs on the side of inclusion. If given this particular conflict, you would see: +Amazon doesn't want to accidently *remove* anything from your cart, so it errs on the side of inclusion. If given this particular conflict, you would see: - ``` - James's Cart - ------------ - Red Candle - Blue Skateboard - Green Umbrella - ``` +``` +James's Cart +------------ +Red Candle +Blue Skateboard +Green Umbrella +``` - It's important to understand that Amazon has multiple machines storing the contents of your cart. These machines are asynchronously communicating in order to tell each other about updates they've received. Conflicts like this can happen when you try to read before the nodes have had time to gossip about your cart. More likely, however, is the situation in which one of the machines holding your cart goes offline and missing some updates. When it comes back online, you try to read, and this resolution process must occur. +It's important to understand that Amazon has multiple machines storing the contents of your cart. These machines are asynchronously communicating in order to tell each other about updates they've received. Conflicts like this can happen when you try to read before the nodes have had time to gossip about your cart. More likely, however, is the situation in which one of the machines holding your cart goes offline and missing some updates. When it comes back online, you try to read, and this resolution process must occur. ### Good & Bad - What do we love about Dynamo? It's a highly available key-value store. It replicates data well, and according to the paper, has an insanely high uptime and low latency. We love that it's *eventually consistent*. Nodes are constantly gossiping, so given enough time (and assuming failures are resolved), nodes' states will eventually converge. However, this property is *weak*. It's weak because when failures+conflicts occur, and [and they will occur](https://www.youtube.com/watch?v=JG2ESDGwHHY), it's up to the application developer to figure out how to handle it. In the case of the shopping cart, it's relatively trivial. But as a programmer, every time you'd like to use DynamoDB you need to consider your resolution strategy. The database doesn't provide a general solution. +What do we love about Dynamo? It's a highly available key-value store. It replicates data well, and according to the paper, has an insanely high uptime and low latency. We love that it's *eventually consistent*. Nodes are constantly gossiping, so given enough time (and assuming failures are resolved), nodes' states will eventually converge. However, this property is *weak*. It's weak because when failures+conflicts occur, and [and they will occur](https://www.youtube.com/watch?v=JG2ESDGwHHY), it's up to the application developer to figure out how to handle it. In the case of the shopping cart, it's relatively trivial. But as a programmer, every time you'd like to use DynamoDB you need to consider your resolution strategy. The database doesn't provide a general solution. - Instead of constructing an all-purpose database and forcing the burden of resolution on programmers, what if we constructed general-purpose data structures that required no manual resolution? These data structures would resolve conflicts inherently, themselves, and depending on your application you could choose which data structure works best for you. +Instead of constructing an all-purpose database and forcing the burden of resolution on programmers, what if we constructed general-purpose data structures that required no manual resolution? These data structures would resolve conflicts inherently, themselves, and depending on your application you could choose which data structure works best for you. - Let's try this transfiguration on the shopping cart. Let's strip it down: how does Amazon handle resolution, really? It treats shopping cart versions as sets of items. In order to perform resolution, Amazon unions the two sets. +Let's try this transfiguration on the shopping cart. Let's strip it down: how does Amazon handle resolution, really? It treats shopping cart versions as sets of items. In order to perform resolution, Amazon unions the two sets. - ``` - { Red Candle, Blue Skateboard } U { Red Candle, Green Umbrella } == { Red Candle, Blue Skateboard, Green Umbrella } - ``` +``` +{ Red Candle, Blue Skateboard } U { Red Candle, Green Umbrella } == { Red Candle, Blue Skateboard, Green Umbrella } +``` - Cool. Using this knowledge, let's try to construct our own shopping cart that automatically resolves conflicts. +Cool. Using this knowledge, let's try to construct our own shopping cart that automatically resolves conflicts. - (Unfortunately Amazon has a leg up on our startup. Their programmers have figured out a way to add multiple instances of a single item into the cart. Users on our website can only add one "Red Candle"" to their shopping cart. This is due to a fundamental limitation in the type of CRDT I chose to exemplify. It's quite possible to have a fully functional cart. Take a look at LWW-Sets.) +(Unfortunately Amazon has a leg up on our startup. Their programmers have figured out a way to add multiple instances of a single item into the cart. Users on our website can only add one "Red Candle"" to their shopping cart. This is due to a fundamental limitation in the type of CRDT I chose to exemplify. It's quite possible to have a fully functional cart. Take a look at LWW-Sets.) ### Example - Let's take a look at the following Javascript. For simplicity's sake, let's pretend users can only add things to their shopping cart. +Let's take a look at the following Javascript. For simplicity's sake, let's pretend users can only add things to their shopping cart. - ```javascript - class Cart { - constructor(peers, socket) { - this.mySocket = socket; - this.peers = peers; - this.items = new Set(); - } +```javascript +class Cart { + constructor(peers, socket) { + this.mySocket = socket; + this.peers = peers; + this.items = new Set(); + } - addItem(item) { - this.items.add(item); - } + addItem(item) { + this.items.add(item); + } - synchronize() { - peers.forEach(function(peer) { - peer.send(items); - }); - } + synchronize() { + peers.forEach(function(peer) { + peer.send(items); + }); + } - receiveState(items) { - this.items = this.items.union(items); - } + receiveState(items) { + this.items = this.items.union(items); + } - run() { - var clientAddition = Interface.nonBlockingReceiveInput(); // invented - if (clientAddition !== undefined) { - this.addItem(clientAddition); - } - var receivedState = mySocket.nonBlockingRead(); // invented - if (receivedState !== undefined) { - this.receiveState(receivedState); - } - synchronize(); - sleep(10); - run(); + run() { + var clientAddition = Interface.nonBlockingReceiveInput(); // invented + if (clientAddition !== undefined) { + this.addItem(clientAddition); + } + var receivedState = mySocket.nonBlockingRead(); // invented + if (receivedState !== undefined) { + this.receiveState(receivedState); } + synchronize(); + sleep(10); + run(); } +} - // theoretical usage +// theoretical usage - var socket = new UDPSocket(); // invented - var cart = new Cart(peerSockets, socket); // peerSockets is an array of UDP sockets - cart.run(); - cart.items // the cart's items - ``` +var socket = new UDPSocket(); // invented +var cart = new Cart(peerSockets, socket); // peerSockets is an array of UDP sockets +cart.run(); +cart.items // the cart's items +``` - Here is an (almost) fully functional shopping cart program. You can imagine this code running across multiple nodes scattered over the world. The meat of the program lies in the `run()` method. Let's walk through that: - 1. Program receives an addition to the cart from the user. - 2. Program adds that item to the current local state if it exists. - 3. Program checks its UDP socket for any messages. - 4. If it received one, it's means another instance of this program has sent us its state. What is state in this case? Simply a set of cart items. Let's handle this set of items by unioning it with our current set. - 5. Synchronize our current state by sending our state to every peer that we know about. - 6. Sleep for 10 seconds. - 7. Repeat! +Here is an (almost) fully functional shopping cart program. You can imagine this code running across multiple nodes scattered over the world. The meat of the program lies in the `run()` method. Let's walk through that: +1. Program receives an addition to the cart from the user. +2. Program adds that item to the current local state if it exists. +3. Program checks its UDP socket for any messages. +4. If it received one, it's means another instance of this program has sent us its state. What is state in this case? Simply a set of cart items. Let's handle this set of items by unioning it with our current set. +5. Synchronize our current state by sending our state to every peer that we know about. +6. Sleep for 10 seconds. +7. Repeat! - W +Hopefully it's clear that if a client adds an item to her cart in Beijing and then 10 seconds later checks her cart in Paris, she should see the same thing. Well, not exactly - remember, the network is unreliable, and Beijing's `synchronize` messages might have been dropped. But no worries! Beijing is `synchronizing` again in another 10 seconds. This should remind you of Dynamo's gossiping: nodes are constantly attempting to converge. - Hopefully it's clear that if a client adds an item to her cart in Beijing and then 10 seconds later checks her cart in Paris, she should see the same thing. Well, not exactly - remember, the network is unreliable, and Beijing's `synchronize` messages might have been dropped. But no worries! Beijing is `synchronizing` again in another 10 seconds. This should remind you of Dynamo's gossiping: nodes are constantly attempting to converge. - - Both systems are eventually consistent - the difference here is our Javascript shopping cart displays *strong* eventual consistency. It's strong because it requires no specialized resolution. When a node transmits its state to another node, there's absolutely no question about how to integrate that state into the current one. There's no conflict. +Both systems are eventually consistent - the difference here is our Javascript shopping cart displays *strong* eventual consistency. It's strong because it requires no specialized resolution. When a node transmits its state to another node, there's absolutely no question about how to integrate that state into the current one. There's no conflict. ### The Intern - Unfortunately Jerry, the intern, has found your code. He'd like to add `remove` functionality to the cart. So he makes the following changes: - - ```javascript - class Cart { - constructor(peers, socket) { - this.mySocket = socket; - this.peers = peers; - this.items = new Set(); - } +Unfortunately Jerry, the intern, has found your code. He'd like to add `remove` functionality to the cart. So he makes the following changes: + +```javascript +class Cart { + constructor(peers, socket) { + this.mySocket = socket; + this.peers = peers; + this.items = new Set(); + } - addItem(item) { - this.items.add(item); - } + addItem(item) { + this.items.add(item); + } - synchronize() { - peers.forEach(function(peer) { - peer.send(items); - }); - } + synchronize() { + peers.forEach(function(peer) { + peer.send(items); + }); + } - receiveState(items) { - // JERRY WAS HERE - this.items = this.items.intersection(items); - // END JERRY WAS HERE - } + receiveState(items) { + // JERRY WAS HERE + this.items = this.items.intersection(items); + // END JERRY WAS HERE + } - run() { - var clientAddition = Interface.nonBlockingReceiveInput(); // invented - if (clientAddition !== undefined) { - this.addItem(clientAddition); - } - // JERRY WAS HERE - var clientDeletion = Interface.nonBlockingReceiveInput(): - if (clientDeletion !== undefined) { - this.items.delete(clientDeletion); - } - // END JERRY WAS HERE - var receivedState = mySocket.nonBlockingRead(); // invented - if (receivedState !== undefined) { - this.receiveState(receivedState); - } - synchronize(); - sleep(10); - run(); + run() { + var clientAddition = Interface.nonBlockingReceiveInput(); // invented + if (clientAddition !== undefined) { + this.addItem(clientAddition); } + // JERRY WAS HERE + var clientDeletion = Interface.nonBlockingReceiveInput(): + if (clientDeletion !== undefined) { + this.items.delete(clientDeletion); + } + // END JERRY WAS HERE + var receivedState = mySocket.nonBlockingRead(); // invented + if (receivedState !== undefined) { + this.receiveState(receivedState); + } + synchronize(); + sleep(10); + run(); } +} + +// theoretical usage + +var socket = new UDPSocket(); // invented +var cart = new Cart(peerSockets, socket); // peerSockets is an array of UDP sockets +cart.run(); +cart.items // the cart's items +``` + +Uh-oh. Can you spot the problem? Let's break it down. In the original code, the current node's cart items were *unioned* with the communicating node's cart. Since there was no deletion, carts could only ever expand. Here was Jerry's plan: + +``` +> I want to delete things. If you delete something from node 1, and intersect it's state from node 2, the item will be deleted from node 2 as well. + +Node 1: { A, B } +Node 2: { A, B } + +delete(Node2, A) + +Node 1: { A, B } +Node 2: { B } - // theoretical usage +Node1 = Node1.intersect(Node2) +Node1: { B } +``` - var socket = new UDPSocket(); // invented - var cart = new Cart(peerSockets, socket); // peerSockets is an array of UDP sockets - cart.run(); - cart.items // the cart's items - ``` +The reasoning is sound. However, there's a huge issue here. We've flipped the `union` operation on its head! Now, carts can *never* expand! They can only either stay the same size or shrink. So although Jerry's contrived example works, it's impossible to ever reach the beginning states of Node 1 and Node 2 unless those two nodes receive *the same writes*. Let's take it from the top: - Uh-oh. Can you spot the problem? Let's break it down. In the original code, the current node's cart items were *unioned* with the communicating node's cart. Since there was no deletion, +``` +Node 1: { } +Node 2: { } + +add(Node1, A) +add(Node2, B) + +Node 1: { A } +Node 2: { B } + +Node1_temp = Node1.intersect(Node2) +Node2_temp = Node2.intersect(Node1) +Node1 = Node1_temp +Node2 = Node2_temp + +Node 1: { } +Node 2: { } +``` + +This is pretty nasty. Jerry has come along and with a few lines of code he's obliterated our nice strong eventually consistent code. Surely there's a better way. ### Guarantees - The original Javascript we wrote down exhibits the property from Section 6 known as *monotonicity*. The union operation ensures that a given node's state is always "greater than or equal to" the states of the other nodes. However, how can we be *sure* that this property is maintained throughout the development of this program? As we've seen, there's nothing stopping an intern from coming along, making a mindless change, and destroying this wonderful property. Ideally, we want to make it impossible (or at least very difficult) to write programs that violate this property. Or, at the very least, we want to make it very easy to write programs that maintain these types of properties. +The original Javascript we wrote down exhibits the property from Section 6 known as *monotonicity*. The union operation ensures that a given node's state is always "greater than or equal to" the states of the other nodes. However, how can we be *sure* that this property is maintained throughout the development of this program? As we've seen, there's nothing stopping an intern from coming along, making a mindless change, and destroying this wonderful property. Ideally, we want to make it impossible (or at least very difficult) to write programs that violate this property. Or, at the very least, we want to make it very easy to write programs that maintain these types of properties. - But where should these guarantees live? In the above Javascript example, the guarantees aren't guarantees at all, really. There's no restriction on what the programmer is allowed to do - the programmer has simply constructed a program that mirrors guarantees that she has modeled in her brain. In order to maintain properties such as *monotonicity*, she must constantly check the model in her brain against the code. We haven't really helped the programmer out that much - she has a lot of thinking to do. +But where should these guarantees live? In the above Javascript example, the guarantees aren't guarantees at all, really. There's no restriction on what the programmer is allowed to do - the programmer has simply constructed a program that mirrors guarantees that she has modeled in her brain. In order to maintain properties such as *monotonicity*, she must constantly check the model in her brain against the code. We haven't really helped the programmer out that much - she has a lot of thinking to do. - At the disk hardward level, there are certain mechanisms in place to ensure that data does not become corrupted when multiple things attempt to write bits to the same physical location. This is considered a type of IO-consistency. It doesn't help much with our shopping cart, but it's certainly necessary. These important guarantees facilitate the higher level abstractions by ensuring low-level safety. It would be unreasonable to expect our disks to enforce monotonicity, for example, since this would restrict usage of disks to monotonic programs only (more on this later!). But on the other hand, as we've seen, pushing the consistency to the application/programmer level is also unreasonable. Our tools should work for us. +Databases such as PostgreSQL have issues like this as well, though they handle them quite differently, masters may need to ensure that write have occurred on every slave before the database becomes available for reading. A database system like this has pushed consistency concerns to the IO-level, completely out of the users control. They are enforced on system reads and system writes. This approach gives programmers no flexibility: as demonstrated with our shopping cart example, there's no need for these type of restrictions; we can tolerate inconsistency in order to maintain availability. - Why not push the consistency guarantees in between? Is there any reason why you as the programmer couldn't program using tools that facilitate these types of monotonic programs? If you're familiar with formal systems -- why not construct a formal system (programming language / library) in which every theorem (program) is formally guarunteed to be monotonic? If it's *impossible* to express a non-monotonic program, the programmer needn't worry about maintaining a direct mapping between their code and their mental model. +Why not push the consistency guarantees in between the IO-level and the application-level? Is there any reason why you as the programmer couldn't program using tools that facilitate these types of monotonic programs? If you're familiar with formal systems -- why not construct a formal system (programming language / library) in which every theorem (program) is formally guarunteed to be monotonic? If it's *impossible* to express a non-monotonic program, the programmer needn't worry about maintaining a direct mapping between their code and their mental model. - Wouldn't it be great if tools like this existed? +Wouldn't it be great if tools like this existed? ### Bloom - The dudes/dudettes at Berkeley seem to think so too. +[ Introduce Bloom ] #### Restriction & Danger - [Bloom restricts you, it's different, and it's dangerous] +[Bloom restricts you, it's different, and it's dangerous] ### Lasp - [Library not language, embeddable, not dangerous] - Instead of trying to do it all (and accepting danger), it tries to be embeddable (and truly restrictive.) +[ Introduce Lasp ] +Instead of trying to do it all (and accepting danger), it tries to be embeddable (and truly restrictive.) + +### Utilization + +Lasp is an Erlang library, and for good reason. Remember the initial discussion and reasoning for models such as Bloom and Lasp: we have a specific type of application that doesn't require tight consistency constraints. The constraints that do exist have been formalized, and we can be quite sure that by using a DSL like Lasp, we'll be safe from interns like Jerry. But Lasp can't do everything. More generally, eventual consistency doesn't solve every problem. + +PostgreSQL enforce very specific and restrictive IO-level consistency, and this was too much for our needs. But it's certainly not too much for *all* needs. There certainly are applications (take banking, for example) in which consistency is extremely important. You certainly are not allowed to double spend your money depending on how fast you can travel to a different server, so eventual consistency is not enough! All servers must coordinate. + +There's a key principle here, however: distributed programming models that attempt to accomdate everything end up doing nothing well; models that accept compromises and formalize certain properties end up being extremely useful for a subset of domains. +Most programming languages are "general-use". This works for single machine programming. As the world moves toward distributed programming, programmers must adopt models / languages / libraries that are built for their domain. It forces serious thought on the part of the programmer: what *exactly* am I trying to achieve, and what am I willing to sacrifice? +We've known for quite a while that when we're talking about multiple machines, we can't have it all. Our tools must now reflect this mantra. Our sanity and the safety of our programs depends on it. ## References -- cgit v1.2.3 From 1b7f186b0ce9dd0014e021331f70dc22bb5798ff Mon Sep 17 00:00:00 2001 From: James Larisch Date: Fri, 9 Dec 2016 23:53:49 -0500 Subject: formatting --- chapter/7/langs-consistency.md | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) (limited to 'chapter') diff --git a/chapter/7/langs-consistency.md b/chapter/7/langs-consistency.md index a77110f..b8f013f 100644 --- a/chapter/7/langs-consistency.md +++ b/chapter/7/langs-consistency.md @@ -124,13 +124,13 @@ cart.items // the cart's items ``` Here is an (almost) fully functional shopping cart program. You can imagine this code running across multiple nodes scattered over the world. The meat of the program lies in the `run()` method. Let's walk through that: -1. Program receives an addition to the cart from the user. -2. Program adds that item to the current local state if it exists. -3. Program checks its UDP socket for any messages. -4. If it received one, it's means another instance of this program has sent us its state. What is state in this case? Simply a set of cart items. Let's handle this set of items by unioning it with our current set. -5. Synchronize our current state by sending our state to every peer that we know about. -6. Sleep for 10 seconds. -7. Repeat! + 1. Program receives an addition to the cart from the user. + 2. Program adds that item to the current local state if it exists. + 3. Program checks its UDP socket for any messages. + 4. If it received one, it's means another instance of this program has sent us its state. What is state in this case? Simply a set of cart items. Let's handle this set of items by unioning it with our current set. + 5. Synchronize our current state by sending our state to every peer that we know about. + 6. Sleep for 10 seconds. + 7. Repeat! Hopefully it's clear that if a client adds an item to her cart in Beijing and then 10 seconds later checks her cart in Paris, she should see the same thing. Well, not exactly - remember, the network is unreliable, and Beijing's `synchronize` messages might have been dropped. But no worries! Beijing is `synchronizing` again in another 10 seconds. This should remind you of Dynamo's gossiping: nodes are constantly attempting to converge. -- cgit v1.2.3 From c97cb3b91165525b1cb0c3273ad1edc59f9f2bd9 Mon Sep 17 00:00:00 2001 From: James Larisch Date: Thu, 15 Dec 2016 23:08:03 -0500 Subject: Small fixes --- chapter/7/langs-consistency.md | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'chapter') diff --git a/chapter/7/langs-consistency.md b/chapter/7/langs-consistency.md index b8f013f..78162bc 100644 --- a/chapter/7/langs-consistency.md +++ b/chapter/7/langs-consistency.md @@ -6,7 +6,7 @@ by: "James Larisch" # Formal, Yet Relaxed: Models for Consistency ## What's the problem? - As processors become expensive and the limits of Moore's Law are pushed, programmers find themselves in situations where they need to connect multiple computers together using a network cable. Perhaps it's not even due to cost or performance constraints; perhaps your company has servers in New York and San Fransisco, and there is some global state that requires synchronization across the country. Problems requiring solutions of this nature can be described as "distributed systems" problems. Your data / processing power / entry points are distributed for some reason. In many ways, web developers deal with distributed systems problems every day: your client and your server are in two different geographical locations, and thus, some coordination is required. + In many ways, web developers deal with distributed systems problems every day: your client and your server are in two different geographical locations, and thus, some coordination between computers is required. As Aviral discussed in the previous section, many computer scientists have done a lot of thinking about the nature of distributed systems problems. As such, we realize that it's impossible to completely emulate the behavior of a single computational machine using multiple machines. For example, the network is simply not as reliable as, say, memory - and waiting for responses can result in a lack of timeliness for the application's client. After discussing the Consistency/Availability/Partition-tolerance theorem, Section 6 discussed how we can make drill down into the CAP pyramid and choose the properties of our systems. As stated, we can't perfectly emulate a single computer using multiple machines, but once we accept that fact and learn to work with it... there are plenty of things we *can* do! @@ -35,7 +35,7 @@ Turns out there's a company out there called Amazon.com - and they've been havin ## Dynamo Amazon built DynamoDB, which is basically a big distributed hash table. In other words, it's a hashmap spread across multiple computers. A user's cart would be stored as a value under the user's username as the key. When a user adds a new item to her cart, the cart data is replicated across a multiple machines within the network. If the client changes locations and performs another write or a few machines fail and later recover, it's possible for different machines to have different opinions about the state of a given user's cart. -Dynamo has a rather unique way of dealing with these types of conflicts. Since Dynamo always wants to be available for both writes and reads (add/removes, viewing/checkouts, resp) it must have a way of combining inconsistent data. Dynamo chooses to perform this resolution at read time. When a client performs a `get()` on the user's cart, Dynamo will take the multiple conflicting carts...aaaaaand... push it all up to the application! Huh? I thought Dynamo resolves this for the programmer!? Actually, Dynamo is a generic key-value store. It detects inconsistencies in the data - but once it does, it simply tells the application (in this case the application is the shopping cart code) that there are some conflicts. The application (shopping cart, in this case) is free to resolve these inconsistencies as it pleases. +Dynamo has a rather unique way of dealing with these types of conflicts. Since Dynamo always wants to be available for both writes and reads (add/removes, viewing/checkouts, resp) it must have a way of combining inconsistent data. Dynamo chooses to perform this resolution at read time. When a client performs a `get()` on the user's cart, Dynamo will take the multiple conflicting carts and push it all up to the application! Huh? I thought Dynamo resolves this for the programmer!? Actually, Dynamo is a generic key-value store. It detects inconsistencies in the data - but once it does, it simply tells the application (in this case the application is the shopping cart code) that there are some conflicts. The application (shopping cart, in this case) is free to resolve these inconsistencies as it pleases. How should Amazon's shopping cart procede with resolution? It may be fed two cart states like so: @@ -59,7 +59,7 @@ Green Umbrella It's important to understand that Amazon has multiple machines storing the contents of your cart. These machines are asynchronously communicating in order to tell each other about updates they've received. Conflicts like this can happen when you try to read before the nodes have had time to gossip about your cart. More likely, however, is the situation in which one of the machines holding your cart goes offline and missing some updates. When it comes back online, you try to read, and this resolution process must occur. ### Good & Bad -What do we love about Dynamo? It's a highly available key-value store. It replicates data well, and according to the paper, has an insanely high uptime and low latency. We love that it's *eventually consistent*. Nodes are constantly gossiping, so given enough time (and assuming failures are resolved), nodes' states will eventually converge. However, this property is *weak*. It's weak because when failures+conflicts occur, and [and they will occur](https://www.youtube.com/watch?v=JG2ESDGwHHY), it's up to the application developer to figure out how to handle it. In the case of the shopping cart, it's relatively trivial. But as a programmer, every time you'd like to use DynamoDB you need to consider your resolution strategy. The database doesn't provide a general solution. +What do we love about Dynamo? It's a highly available key-value store. It replicates data well, and according to the paper, has high uptime and low latency. We love that it's *eventually consistent*. Nodes are constantly gossiping, so given enough time (and assuming failures are resolved), nodes' states will eventually converge. However, this property is *weak*. It's weak because when failures+conflicts occur, and [and they will occur](https://www.youtube.com/watch?v=JG2ESDGwHHY), it's up to the application developer to figure out how to handle it. In the case of the shopping cart, it's relatively trivial. But as a programmer, every time you'd like to use DynamoDB you need to consider your resolution strategy. The database doesn't provide a general solution. Instead of constructing an all-purpose database and forcing the burden of resolution on programmers, what if we constructed general-purpose data structures that required no manual resolution? These data structures would resolve conflicts inherently, themselves, and depending on your application you could choose which data structure works best for you. -- cgit v1.2.3 From b194e06bb58c6a840fd080466bb62b14cf64e201 Mon Sep 17 00:00:00 2001 From: James Larisch Date: Fri, 16 Dec 2016 15:46:17 -0500 Subject: Bloom, first pass --- chapter/7/langs-consistency.md | 295 ++++++++++++++++++++++++++++++++++++++++- 1 file changed, 292 insertions(+), 3 deletions(-) (limited to 'chapter') diff --git a/chapter/7/langs-consistency.md b/chapter/7/langs-consistency.md index 78162bc..cd0a7e5 100644 --- a/chapter/7/langs-consistency.md +++ b/chapter/7/langs-consistency.md @@ -244,10 +244,299 @@ Why not push the consistency guarantees in between the IO-level and the applicat Wouldn't it be great if tools like this existed? ### Bloom -[ Introduce Bloom ] +Before talking about such tools, I'd like you to forget almost everything you know about programming for a second (unless of course you've never programmed in a Von Neumann-based language in which you sequentially update pieces of memory; which, by the way, you have). -#### Restriction & Danger -[Bloom restricts you, it's different, and it's dangerous] +Imagine the following scenario: you are "programming" a node in a cluster of computers. All of the other computers work as expected. When you receive a message (all messages will include an integer), your task is to save the message, increment the integer, and resend the message back to its originator. You must also send messages you've received from `stdin`. Unfortunately, the programming environment isn't like anything you've encountered before. +You have access to five buffers: +* Messages you have received in the last 5 seconds +* Inputs you've received from `stdin` in the last 5 seconds +* An outgoing messages buffer: flushed & sent every 5 seconds +* A bucket of saved messages: *never* flushed + +However, you only have access to these buffers *every 5 seconds*. If messages are formatted as such: `(SOURCE, INTEGER, T)`, your buffers might look like when `t = 0`. (`t` is the number of seconds elapsed) + +``` + +RECV-BUFFER: [(A, 1, 0), (B, 2, 0)] +RSTDIN-INPUTS: [(A, 5, 0), (C, 10, 0)] +SEND-BUFFER: [] +SAVED: [(D, -1, 0), (E, -100, 0)] +``` + +If you don't write any code to manipulate these buffers, when `t = 5`, your buffers might look like: + +``` + +RECV-BUFFER: [(C, 10, 5)] +STDIN-INPUTS: [(X, 1, 5)] +SEND-BUFFER: [] +SAVED: [(D, -1, 0), (E, -100, 0)] +``` + +You can see that from `t = 0` to `t = 5`, you received one message from `C` and someone typed a message to `X` via `stdin`. + +Remember our goals? +* Save received messages from the network +* Send out messages received from `stdin` +* For all received network messages, increment the integer and resend it back to the originator + +In Javascript, perhaps you code up something like this: + +```javascript +onFiveSecondInterval(function() { + recvBuffer.forEach(function(msg) { + savedBuffer.push(msg); // save message + let newMsg = msg.clone() + newMsg.integer++; // increment recv'd message + sendBuffer.push(newMsg); // send it out + }); + + stdinInputBuffer.forEach(function(msg) { + sendBuffer.push(msg); // send stdin message + }); +}); +``` + +or Ruby: + +```ruby +on_five_second_interval do + recv_buffer.each do |msg| + saved_buffer << msg + new_msg = msg.clone + new_msg.integer += 1 + send_buffer << new_msg + end + + stdin_input_buffer.each do |msg| + send_buffer << msg + end +end +``` + +We have expressed this model using an event-driven programming style: the main event is `t % 5 = 0`: when the buffers populate & flush. + +Notice we perform a few "copies". We read something from one buffer and place it into another one, perhaps after applying some modification. Perhaps we place a message from a given buffer into two buffers (`recv_buffer` to `saved_buffer` & `send_buffer`). + +This situation screams for a more functional approach: +```ruby +on_five_second_interval do + saved_buffer += recv_buffer # add everything in recv_buffer to saved_buffer + + send_buffer += recv_buffer.map do |msg| # map over the recv_buffer, increment integers, add to send_buffer + new_msg = msg.clone + new_msg.integer += 1 + new_msg # this block returns new_msg + end + + send_buffer += stdin_input_buffer # add stdin messages to the send buffer +end +``` + +After this block/callback is called, the system automatically flushes & routes messages as described above. + +Bloom, a research language developed at UC Berkeley, has a similar programming model to the one described above. Execution is broken up into a series of "timesteps". In the above example, one "timestemp" would be the execution of one `on_five_second_interval` function. Bloom, like the theoretical system above, automatically flushes and populates the buffers before and after each timestep. In the above example, 5 seconds was an arbitrary amount of time. In Bloom, timesteps (rounds of evaluation) are logical tools - they may happen every second, 10 seconds, etc. Logically, it shouldn't affect how your program executes. In reality, Bud's timesteps correspond to evaluation iterations. Your code is evaluated, executed, and the process repeats. + +So what does a Bloom program look like? Bloom's prototypal implementation is called Bud and is implemented in Ruby. There are two main parts to a Bloom program: +1. User defined buffers: rather than the four buffers I gave you above, Bloom users can define their own buffers. There are different types of buffers depending on the behavior you desire: + * `channel`: Above, `recv_buffer` and `send_buffer` would be considered channels. They facilitate sending network messages to and from other nodes. Like the messages above, messages sent into these channels contain a "location-specifier", which tells Bloom where the message should be sent. If you wanted to send a message to `A`, you could push the message `(@A, 10)` into your send buffer (in Ruby, `["@A", 10]`). The `@` denotes the location-specifier. + * `table`: Above, `saved_buffer` would be considered a table. The contents of tables persist across timesteps. +2. Code to be executed at each timestep. A Bloom (Bud) program can be seen as the inside of the block passed to `on_five_second_interval`. In fact, it looks very similar, as we'll see. + +For the purposes of this chapter, let's assume `stdin_input_buffer` is a special kind of channel in which are sent in via `stdin`. Let's also assume this channel exists in all Bloom programs. + +Let's take a look at an example Bud program. + +First, let's declare our state. + +```ruby +module Incrementer + def state + channel :network_channel ['@dst', 'src', 'integer'] + table :saved_buffer ['dst', 'src', 'integer'] + # implied channel :stdin_input_buffer ['@dst', 'src', 'integer'] + end +end +``` + +The first line of `state` means: declare a channel called `network_channel` in which messages are 3-tuples. The first field of the message is called `dst`, the second `src`, and the third is called `integer`. `@` is our location-specifier, so if a program wants to send a message to a node at a given identifier, they will place it in the first `dst` field. + +The second line means: declare a table (persists) called `saved_buffer` in which messages follow the same format as `network_channel`. There's no location specifier since this collection is not network-connected. + +You can think of the Ruby array after the channel name as the "schema" of that collection. + +Notice how we only have one network channel for both receiving and sending. Before, we had two buffers, one for sending and one for receiving. When we place items *into* `network_channel`, Bud will automatically send messages to the appropriate `@dst`. + +Next, let's write our code. This code will be executed at every timestamp. In fact, you can think of a Bud program as the code inside of a timestamp callback. Let's model the raw Ruby code we saw above. + +```ruby +module Incrementer + def state + channel :network_channel ['@dst', 'src', 'integer'] + table :saved_buffer ['dst', 'src', 'integer'] + # implied channel :stdin_input_buffer ['@dst', 'src', 'integer'] + end + + declare + def increment_messages + network_channel <~ network_channel.map { |x| [x.src, x.dst, x.integer + 1] } + end + + declare + def save_messages + saved_buffer <= network_channel + end + + declare + def send_messages + network_channel <~ stdin_input_buffer + end +end +``` + +Don't panic. Remember - the output of this program is identical to our Ruby callback program from earlier. Let's walk through it step by step. +```ruby +declare +def increment_messages + network_channel <~ network_channel.map { |x| [x.src, x.dst, x.integer] } +end +``` +Here, we take messages we've received from the network channel and send them back into the network channel. The `<~` operator says "copy all of the elements in the right-hand-side and eventually send them off onto the network in the channel on the left-hand-side". So, we map over the contents of network channel *in the current timestep*: switching the `src` and `dst` fields, and incrementing the integer. This mapped collection is passed back into the network channel. Bud will ensure those messages sent off at some point. + +``` +declare +def save_messages + saved_buffer <= network_channel +end +``` +In `save_messages`, we use the `<=` operator. `<=` says "copy all of the elements in the right-hand-side and add them to the table on the left-hand-side." It's important to note that this movement occurs *within the current timestep*. This means if `saved_buffer` is referenced elsewhere in the code, it will include the contents of `network_channel`. If we had used the `<+` operator instead, the contents of `network_channel` would show up in `saved_buffer` in the *next* timestep. The latter is useful if you'd like to operate on the current contents of `saved_buffer` in the current timestep but want to specify how `saved_buffer` should be updated for the next timestep. + +Remember, all of this code is executed in each timestep - the separation of code into separate methods is merely for readability. + +``` +declare +def send_messages + network_channel <~ stdin_input_buffer +end +``` + +`send_messages` operates very much like `increment_messages`, except it reads the contents of `stdin_input_buffer` and places them into the network channel to be sent off at an indeterminite time. + +#### Details + +Examine Bloom's "style". Compare it to your (probably) standard way of programming. Compare it to the Javascript & Ruby examples within this strange "timestep" model. Bloom has a more "declarative" style: what does this mean? Look at our Javascript: + +```javascript +onFiveSecondInterval(function() { + recvBuffer.forEach(function(msg) { + savedBuffer.push(msg); // save message + let newMsg = msg.clone() + newMsg.integer++; // increment recv'd message + sendBuffer.push(newMsg); // send it out + }); + + stdinInputBuffer.forEach(function(msg) { + sendBuffer.push(msg); // send stdin message + }); +}); +``` + +"Every five seconds, loop over the received messages. For each one, do this, then that, then that." We are telling the computer each step we'd like it to perform. In Bud, however, we describe the state of tables and channels at either the current or next timestep using operators and other tables and channels. We describe what we'd like our collections to include and look like, rather than what to do. You declare what you'd like the state of the world to be at the current instant and at following instants. + +#### Isn't this chapter about consistency? + +It's time to implement our shopping cart in Bloom. We are going to introduce one more collection: a `periodic`. For example, `periodic :timer 10` instantiates a new periodic collection. This collection is "not empty" every 10 seconds. Alone, it's not all that useful. However, when `join`'d with another table, it can be used to perform actions every `x` seconds. + +```ruby +module ShoppingCart + include MulticastProtocol + + def state + table :cart ['item'] + channel :recv_channel ['@src', 'dst', 'item'] + # implied channel :stdin_input_buffer ['item'] + periodic :timer 10 + end + + declare + def add_items + cart <= stdin_input_buffer + end + + declare + def send_items + send_mcast <= join([cart, timer]).map { |item, timer| item } + end + + declare + def receive_items + cart <+ recv_channel.map { |x| x.item } + end +end +``` + +`send_mcast` is a special type of channel we receive from the `MulticastProtocol` mixin. It sends all items in the right-hand-side to every known peer. +* `add_items`: receive items from stdin, add them to the cart +* `send_items`: join our cart with the 10-second timer. Since the timer only "appears" every 10 seconds, this `join` will produce a result every 10 seconds. When it does, send all cart items to all peers via `send_mcast`. +* `receive_items`: when we receive a message from a peer, add the item to our cart. + +Functionally, this code is equivalent to our working Javascript shopping cart implementation. A few important things to note: +* In our Javascript example, we broadcasted our entire cart to all peers. When a peer received a message, they unioned their current cart with the received one. Here, each node broadcasts each element in the cart. When a node receives an item, it adds it to the current cart. Since tables are represented as sets, repeated or unordered additions do not matter. You can think of `{A, B, C}.add(D)` as equivalent to `{A, B, C}.union({D})`. +* You cannot add items twice. Since tables are represented as sets and we simply add items to our set, an item can only ever exist once. This was true of our Javascript example as well. +* You still cannot remove items! + +Bloom has leveraged the montononic, add-only set and constructed a declarative programming model based around these sets. When you treat everything as sets (not unlike SQL) and you introduce the notion of "timestemps", you can express programs as descriptions of state rather than an order of operations. Besides being a rather unique model, Bloom presents an accessible and (perhaps...) safe model for programming eventually consistent programs. + +#### Sets only? +Bloom's programming model is built around the set. As Aviral discussed in the previous chapter, however, sets are not the only monotonic data structures. Other CRDTs are incredibly useful for programming eventually consistent distributed programs. + +Recall that a *bounded join semilattice* (CRDT) can be represented as a 3-tuple: `(S, U, ⊥)`. `S` is the set of all elements within the semilattice. `U` is the `least-upper bound` operation. `⊥` is the "least" element within the set. For example, for add-only sets, `S = the set of all sets`, `U = union` and `⊥ = {}`. Elements of these semilattices, when `U` is applied, can only "stay the same or get larger". Sets can only stay the same size or get larger - they can never rollback. For some element `e` in `S`, `e U ⊥` must equal `e`. +For a semilattice we'll call `integerMax`, `S = the set of all integers`, `U = max(x, y)`, and `⊥ = -Infinity`. + +These semilattices (and many more!) can be used to program other types of distributed, eventually consistent programs. Although sets are powerful, there might be more expressive ways to describe your program. It's not difficult to imagine using `integerMax` to keep a global counter across multiple machines. + +Unfortunately, Bloom does not provide support for other CRDTs. In fact, you cannot define your own datatypes at all. You are bound by the collections described. + +BloomL, an addendum to the Bloom language, provides support for these types of data structures. Specifically, BloomL does two things: +* Adds a number of built-in lattices such as `lmax` (`integerMax`), `lmin`, etc. +* Adds an "interface" for lattices: the user can define lattices that "implement" this interface. + +This interface, if in an OO language like Java, would look something like: + +```java +interface Lattice { + static Lattice leastElement(); + Lattice merge(Lattice a, Lattice b); +} +``` + +[I am purposely leaving out morphisms & monotones for the sake of simplicity.] + +This provides the user with much more freedom in terms of the types of Bloom programs she can write. + +#### Review + +Bloom aims to provide a new model for writing distributed programs. And since bloom only allows for monotonic data structures with monotonicity-preserving operations, we're safe from Jerry the intern, right? + +Wrong. Unfortunately, I left out an operator from Bloom's set of collection operators. `<-` removes all elements in the right-hand-size from the table in the left-hand-side. As we've seen from Jerry's work on our original Javascript shopping cart implementation, naively attempting to remove elements from a distributed set is not a safe operation. Rollbacks can potentially destroy the properties we worked so hard to achieve. So what gives? Why would the Bloom developers add this operation? + +Despite putting so much emphasis on consistency via logical monotonicity, the Bloom programmers recognize that your program might need *some* coordination. + +In our example, we don't require coordination. We accept the fact that a user may ask a given node for the current state of her shopping cart and may not receive the most up-to-date response. There's no need for coordination, because we've used our domain knowledge to accept a compromise. + +For our shopping cart examples: when a client asks a given node what's in her cart, that node will respond with the information it's received so far. We know this information won't be *incorrect*, but this data could be *stale*. That client might be missing information. + +The Bloom team calls these points in your program *points of order*. They are points in your program where coordination may be required. In fact, the Bloom developers provide analysis tools for identifying points of order within your program. There's no reason why you couldn't implement a non-monotonic shopping cart in which all nodes must synchronize before giving a response to the user. The Bloom analysis tool would tell you where the points of order lie in your program and you would need to add coordination. + +So what does Bloom really give us? First off, it demonstrates an unusual and possibly more expressive way to program distributed systems. Consistency-wise, it uses sets under the hood for its collections. As long as you shy away from `<-` operator, you can be confident that your collections will only monotonically grow. Since the order of packets is not guaranteed, structuring these eventually consistent applications is reasonably easy within Bloom. BloomL also gives us the power to define our own monotonic data structures by "implementing" the lattice interface. + +However, Bloom makes it easy to program non-monotonic distributed programs as well. Applications may require coordination and the `<-` operator in particular can cause serious harm to our desired formal properties. Luckily, Bloom attempts to let the programmer know exactly when coordination may be required within their programs. Whenever an operation may return a stale or non-up-to-date value, Bloom's analysis tools let the programmer know. + +Another thing to consider: BloomL's user-defined lattices are just that - user-defined. It's up to the programmer to ensure that the data structures that implement the lattice interface are actually valid lattice structures. If not, Bloom can't help you. + +Currently Bloom exists as a Ruby prototype: Bud. Hypothetically speaking, there's nothing stopping the programmer from writing normal, sequentially evaluated Ruby code within Bud. This can also cause harm to our formal properties. + +All in all, Bloom provides programmers with a new model for writing distributed programs. If the user desires monotonic data structures and operations, it's relatively easy to use and reason about. Rather than blindly destroying the properties of your system, you will know exactly when you introduce a possible point of order into your program. It's up to you to decide whether or not you need to introduce coordination. ### Lasp [ Introduce Lasp ] -- cgit v1.2.3 From b8d19388111b4dacecf4694a8db36f0721f26eb0 Mon Sep 17 00:00:00 2001 From: James Larisch Date: Fri, 16 Dec 2016 17:06:03 -0500 Subject: Begin lasp, add citations --- chapter/7/langs-consistency.md | 22 +++++++++++++++------- 1 file changed, 15 insertions(+), 7 deletions(-) (limited to 'chapter') diff --git a/chapter/7/langs-consistency.md b/chapter/7/langs-consistency.md index cd0a7e5..0b10c56 100644 --- a/chapter/7/langs-consistency.md +++ b/chapter/7/langs-consistency.md @@ -33,7 +33,7 @@ This is an important moment. By thinking about our specific problem, we've reali Turns out there's a company out there called Amazon.com - and they've been having a similar problem. Amazon sells things on their website too, and users can add and remove things from their cart. Amazon has lots of servers spread out across the world. They also have quite a few customers. They need to ensure their customers' carts are robust: if/when servers fail or lose communication with one another, a "best-effort" should be made to display the customer's cart. Amazon acknowledges that failure, latency, or HyperLoop-traveling users can cause inconsistent cart data, depending on which server you ask. How does Amazon resolve these issues? ## Dynamo -Amazon built DynamoDB, which is basically a big distributed hash table. In other words, it's a hashmap spread across multiple computers. A user's cart would be stored as a value under the user's username as the key. When a user adds a new item to her cart, the cart data is replicated across a multiple machines within the network. If the client changes locations and performs another write or a few machines fail and later recover, it's possible for different machines to have different opinions about the state of a given user's cart. +Amazon built DynamoDB {% cite Dynamo --file langs-consistency %}, which is basically a big distributed hash table. In other words, it's a hashmap spread across multiple computers. A user's cart would be stored as a value under the user's username as the key. When a user adds a new item to her cart, the cart data is replicated across a multiple machines within the network. If the client changes locations and performs another write or a few machines fail and later recover, it's possible for different machines to have different opinions about the state of a given user's cart. Dynamo has a rather unique way of dealing with these types of conflicts. Since Dynamo always wants to be available for both writes and reads (add/removes, viewing/checkouts, resp) it must have a way of combining inconsistent data. Dynamo chooses to perform this resolution at read time. When a client performs a `get()` on the user's cart, Dynamo will take the multiple conflicting carts and push it all up to the application! Huh? I thought Dynamo resolves this for the programmer!? Actually, Dynamo is a generic key-value store. It detects inconsistencies in the data - but once it does, it simply tells the application (in this case the application is the shopping cart code) that there are some conflicts. The application (shopping cart, in this case) is free to resolve these inconsistencies as it pleases. @@ -239,7 +239,7 @@ But where should these guarantees live? In the above Javascript example, the gua Databases such as PostgreSQL have issues like this as well, though they handle them quite differently, masters may need to ensure that write have occurred on every slave before the database becomes available for reading. A database system like this has pushed consistency concerns to the IO-level, completely out of the users control. They are enforced on system reads and system writes. This approach gives programmers no flexibility: as demonstrated with our shopping cart example, there's no need for these type of restrictions; we can tolerate inconsistency in order to maintain availability. -Why not push the consistency guarantees in between the IO-level and the application-level? Is there any reason why you as the programmer couldn't program using tools that facilitate these types of monotonic programs? If you're familiar with formal systems -- why not construct a formal system (programming language / library) in which every theorem (program) is formally guarunteed to be monotonic? If it's *impossible* to express a non-monotonic program, the programmer needn't worry about maintaining a direct mapping between their code and their mental model. +Why not push the consistency guarantees in between the IO-level and the application-level? {% cite ConsistencyWithoutBorders --file langs-consistency %} { Is there any reason why you as the programmer couldn't program using tools that facilitate these types of monotonic programs? If you're familiar with formal systems -- why not construct a formal system (programming language / library) in which every theorem (program) is formally guarunteed to be monotonic? If it's *impossible* to express a non-monotonic program, the programmer needn't worry about maintaining a direct mapping between their code and their mental model. Wouldn't it be great if tools like this existed? @@ -335,7 +335,7 @@ end After this block/callback is called, the system automatically flushes & routes messages as described above. -Bloom, a research language developed at UC Berkeley, has a similar programming model to the one described above. Execution is broken up into a series of "timesteps". In the above example, one "timestemp" would be the execution of one `on_five_second_interval` function. Bloom, like the theoretical system above, automatically flushes and populates the buffers before and after each timestep. In the above example, 5 seconds was an arbitrary amount of time. In Bloom, timesteps (rounds of evaluation) are logical tools - they may happen every second, 10 seconds, etc. Logically, it shouldn't affect how your program executes. In reality, Bud's timesteps correspond to evaluation iterations. Your code is evaluated, executed, and the process repeats. +Bloom {% cite Bloom --file langs-consistency %}, a research language developed at UC Berkeley, has a similar programming model to the one described above. Execution is broken up into a series of "timesteps". In the above example, one "timestemp" would be the execution of one `on_five_second_interval` function. Bloom, like the theoretical system above, automatically flushes and populates the buffers before and after each timestep. In the above example, 5 seconds was an arbitrary amount of time. In Bloom, timesteps (rounds of evaluation) are logical tools - they may happen every second, 10 seconds, etc. Logically, it shouldn't affect how your program executes. In reality, Bud's timesteps correspond to evaluation iterations. Your code is evaluated, executed, and the process repeats. So what does a Bloom program look like? Bloom's prototypal implementation is called Bud and is implemented in Ruby. There are two main parts to a Bloom program: 1. User defined buffers: rather than the four buffers I gave you above, Bloom users can define their own buffers. There are different types of buffers depending on the behavior you desire: @@ -497,7 +497,7 @@ These semilattices (and many more!) can be used to program other types of distri Unfortunately, Bloom does not provide support for other CRDTs. In fact, you cannot define your own datatypes at all. You are bound by the collections described. -BloomL, an addendum to the Bloom language, provides support for these types of data structures. Specifically, BloomL does two things: +BloomL{% cite BloomL --file langs-consistency %}, an addendum to the Bloom language, provides support for these types of data structures. Specifically, BloomL does two things: * Adds a number of built-in lattices such as `lmax` (`integerMax`), `lmin`, etc. * Adds an "interface" for lattices: the user can define lattices that "implement" this interface. @@ -539,8 +539,16 @@ Currently Bloom exists as a Ruby prototype: Bud. Hypothetically speaking, there' All in all, Bloom provides programmers with a new model for writing distributed programs. If the user desires monotonic data structures and operations, it's relatively easy to use and reason about. Rather than blindly destroying the properties of your system, you will know exactly when you introduce a possible point of order into your program. It's up to you to decide whether or not you need to introduce coordination. ### Lasp -[ Introduce Lasp ] -Instead of trying to do it all (and accepting danger), it tries to be embeddable (and truly restrictive.) +Lasp {% cite Lasp --file langs-consistency %}is an Erlang library which aims to facilitate this type of "disorderly" programming. + +Lasp provides access to myriad of CRDTs. It does not allows user-defined CRDTs (lattices), but the programmer can have confidence that the CRDTs obey the lattice formal requirements. + +A Simple Lasp Program is defined as either a: +* Single CRDT instance +* A "Lasp process" with *m* inputs, all Simple Lasp Programs, and one output CRDT instance + +For those of you unfamiliar with Erlang: a *process* can be thought of as an independent piece of code executing asynchronously. Processes can receive messages and send messages to other processes. Process can also subscribe (I think) to other processes' messages. + ### Utilization @@ -548,7 +556,7 @@ Lasp is an Erlang library, and for good reason. Remember the initial discussion PostgreSQL enforce very specific and restrictive IO-level consistency, and this was too much for our needs. But it's certainly not too much for *all* needs. There certainly are applications (take banking, for example) in which consistency is extremely important. You certainly are not allowed to double spend your money depending on how fast you can travel to a different server, so eventual consistency is not enough! All servers must coordinate. -There's a key principle here, however: distributed programming models that attempt to accomdate everything end up doing nothing well; models that accept compromises and formalize certain properties end up being extremely useful for a subset of domains. +There's a key principle here, however: distributed programming models that attempt to accomodate everything end up doing nothing well; models that accept compromises and formalize certain properties end up being extremely useful for a subset of domains. Most programming languages are "general-use". This works for single machine programming. As the world moves toward distributed programming, programmers must adopt models / languages / libraries that are built for their domain. It forces serious thought on the part of the programmer: what *exactly* am I trying to achieve, and what am I willing to sacrifice? -- cgit v1.2.3 From 79f787876a4e71b54e2d6724b58f6c056c8d2512 Mon Sep 17 00:00:00 2001 From: James Larisch Date: Sat, 17 Dec 2016 15:56:23 -0500 Subject: Fixes, fix up conclusion --- chapter/7/langs-consistency.md | 86 ++++++++++++++++++++++++++---------------- 1 file changed, 54 insertions(+), 32 deletions(-) (limited to 'chapter') diff --git a/chapter/7/langs-consistency.md b/chapter/7/langs-consistency.md index 0b10c56..edaee53 100644 --- a/chapter/7/langs-consistency.md +++ b/chapter/7/langs-consistency.md @@ -8,7 +8,7 @@ by: "James Larisch" ## What's the problem? In many ways, web developers deal with distributed systems problems every day: your client and your server are in two different geographical locations, and thus, some coordination between computers is required. - As Aviral discussed in the previous section, many computer scientists have done a lot of thinking about the nature of distributed systems problems. As such, we realize that it's impossible to completely emulate the behavior of a single computational machine using multiple machines. For example, the network is simply not as reliable as, say, memory - and waiting for responses can result in a lack of timeliness for the application's client. After discussing the Consistency/Availability/Partition-tolerance theorem, Section 6 discussed how we can make drill down into the CAP pyramid and choose the properties of our systems. As stated, we can't perfectly emulate a single computer using multiple machines, but once we accept that fact and learn to work with it... there are plenty of things we *can* do! + As Aviral discussed in the previous section, many computer scientists have done a lot of thinking about the nature of distributed systems problems. As such, we realize that it's impossible to completely emulate the behavior of a single computational machine using multiple machines. For example, the network is simply not as reliable as, say, memory - and waiting for responses can result in untimeliness for the application's userbase. After discussing the Consistency/Availability/Partition-tolerance theorem, Section 6 discussed how we can make drill down into the CAP pyramid and choose the necessary and unnecessary properties of our systems. As stated, we can't perfectly emulate a single computer using multiple machines, but once we accept that fact and learn to work with it, there are plenty of things we *can* do! ## The Shopping Cart Let's bring all these theorem talk back to reality. Let's say you're working at a new e-commerce startup, and you'd like to revolutionize the electronic shopping cart. You'd like to give the customer the ability to do the following: @@ -24,18 +24,18 @@ How can we ensure that the client sees the same cart at every point in her trip? If you only had one user of your website, this wouldn't be too hard. You could manually, constantly modify and check on all of your servers and personally make sure the state of the customer's shopping cart is consistent across every single server. But what happens when you have millions of customers and thus millions of shopping carts? That would be impossible to keep track of personally. Luckily, you're a programmer - this can be automated! You simply need to make sure that all of your computers stay in-sync, so if the customer checks her cart in Beijing, then in Paris, she sees the same thing. -But as Section 6 already explained, this is not so trivial. Messages between your servers in Beijing and Paris could get dropped, corrupted, reordered, duplicated, or delayed. Servers can crash. Sharks can cut the network cables between countries. Since you have no guarantees about when you'll be able to synchronize state between two servers, it's possible that the customer could see two different cart-states depending on which country she's in (which server she asks). +But as Section 6 has already explained, this is not so trivial. Messages between your servers in Beijing and Paris could be dropped, corrupted, reordered, duplicated, or delayed. Servers can crash. Sharks can cut the network cables between countries. Since you have no guarantees about when you'll be able to synchronize state between two servers, it's possible that the customer could see two different cart-states depending on which country she's in (which server she asks). -It's possible to implement "consensus" protocols such as Paxos and 3-Phase-Commit that provide coordination between your machines. When failure happens, such as a network shark-attack, the protocol detects a lack of consistency and becomes *unavailable*. For some applications, this is appropriate. For a shopping cart, this seems like overkill. If our shopping cart distributed systems experienced a failure, it means users would not be able to add or remove things from the cart. They also couldn't check out. This means our startup would lose money! Perhaps it's not so important that our clients' shopping carts be completely synchronized across the entire world at all times. After all, how often are people going to be doing such wanderlust shopping? +It's possible to implement "consensus" protocols such as Paxos and 3-Phase-Commit that provide coordination between your machines. When failure happens, such as a network shark-attack, the protocol detects a lack of consistency and becomes *unavailable* - at least until it is consistent once more. For applications in which inconsistent state is dangerous, this is appropriate. For a shopping cart, this seems like overkill. If our shopping cart system experienced a failure and became unavailable, users would not be able to add or remove things from the cart. They also couldn't check out. This means our startup would lose money! Perhaps it's not so important that our clients' shopping carts be completely synchronized across the entire world at all times. After all, how often are people going to be doing such wanderlust shopping? -This is an important moment. By thinking about our specific problem, we've realized a compromise we're willing to make: our users always need to be able to add things, remove things, and checkout. In other words, our service needs to be *available*. Servers don't necessarily need to agree all the time. We'd like them to, but the system shouldn't shut down if they don't. We'll find a way to deal with it. +This is an important moment. By thinking about our specific problem, we've realized a compromise we're willing to make: our users always need to be able to add things, remove things, and checkout. In other words, our service needs to be as *available* as possible. Servers don't necessarily need to agree all the time. We'd like them to, but the system shouldn't shut down if they don't. We'll find a way to deal with it. Turns out there's a company out there called Amazon.com - and they've been having a similar problem. Amazon sells things on their website too, and users can add and remove things from their cart. Amazon has lots of servers spread out across the world. They also have quite a few customers. They need to ensure their customers' carts are robust: if/when servers fail or lose communication with one another, a "best-effort" should be made to display the customer's cart. Amazon acknowledges that failure, latency, or HyperLoop-traveling users can cause inconsistent cart data, depending on which server you ask. How does Amazon resolve these issues? ## Dynamo -Amazon built DynamoDB {% cite Dynamo --file langs-consistency %}, which is basically a big distributed hash table. In other words, it's a hashmap spread across multiple computers. A user's cart would be stored as a value under the user's username as the key. When a user adds a new item to her cart, the cart data is replicated across a multiple machines within the network. If the client changes locations and performs another write or a few machines fail and later recover, it's possible for different machines to have different opinions about the state of a given user's cart. +Amazon built DynamoDB {% cite Dynamo --file langs-consistency %}, which is basically a big distributed hash table. In other words, it's a hashmap spread across multiple computers. A user's cart would be stored as a value under the user's username as the key. (`{'james': {'candle', 'skateboard'}}`) When a user adds a new item to her cart, the cart data is replicated across a multiple machines within the network. If the client changes locations then performs another write, or if a few machines fail and later recover, it's possible for different machines to have different opinions about the state of a given user's cart. -Dynamo has a rather unique way of dealing with these types of conflicts. Since Dynamo always wants to be available for both writes and reads (add/removes, viewing/checkouts, resp) it must have a way of combining inconsistent data. Dynamo chooses to perform this resolution at read time. When a client performs a `get()` on the user's cart, Dynamo will take the multiple conflicting carts and push it all up to the application! Huh? I thought Dynamo resolves this for the programmer!? Actually, Dynamo is a generic key-value store. It detects inconsistencies in the data - but once it does, it simply tells the application (in this case the application is the shopping cart code) that there are some conflicts. The application (shopping cart, in this case) is free to resolve these inconsistencies as it pleases. +Dynamo has a rather unique way of dealing with these types of conflicts. Since Dynamo always wants to be available for both writes and reads (add/removes, viewing/checkouts, resp) it must have a way of combining inconsistent data. Dynamo chooses to perform this resolution at read time. When a client performs a `get()` on the user's cart, Dynamo will take the multiple conflicting carts and push them up to the application! Huh? I thought Dynamo resolves this for the programmer!? Actually, Dynamo is a generic key-value store. It detects inconsistencies in the data - but once it does, it simply tells the application (in this case the application is the shopping cart code) that there are some conflicts. The application (shopping cart, in this case) is free to resolve these inconsistencies as it pleases. How should Amazon's shopping cart procede with resolution? It may be fed two cart states like so: @@ -59,9 +59,9 @@ Green Umbrella It's important to understand that Amazon has multiple machines storing the contents of your cart. These machines are asynchronously communicating in order to tell each other about updates they've received. Conflicts like this can happen when you try to read before the nodes have had time to gossip about your cart. More likely, however, is the situation in which one of the machines holding your cart goes offline and missing some updates. When it comes back online, you try to read, and this resolution process must occur. ### Good & Bad -What do we love about Dynamo? It's a highly available key-value store. It replicates data well, and according to the paper, has high uptime and low latency. We love that it's *eventually consistent*. Nodes are constantly gossiping, so given enough time (and assuming failures are resolved), nodes' states will eventually converge. However, this property is *weak*. It's weak because when failures+conflicts occur, and [and they will occur](https://www.youtube.com/watch?v=JG2ESDGwHHY), it's up to the application developer to figure out how to handle it. In the case of the shopping cart, it's relatively trivial. But as a programmer, every time you'd like to use DynamoDB you need to consider your resolution strategy. The database doesn't provide a general solution. +What do we love about Dynamo? It's a highly available key-value store. It replicates data well, and according to the paper, has high uptime and low latency. We love that it's *eventually consistent*. Nodes are constantly gossiping, so given enough time (and assuming failures are resolved), nodes' states will eventually converge. However, this property is *weak*. It's weak because when failures & conflicts occur, and [and they will occur](https://www.youtube.com/watch?v=JG2ESDGwHHY), it's up to the application developer to figure out how to handle it. Given a conflict, there isn't a one-size-fits-all solution for resolving them. In the case of the shopping cart, it's relatively trivial. But as a programmer, every time you use DynamoDB for a different purpose you need to consider your resolution strategy. The database doesn't provide a general solution. -Instead of constructing an all-purpose database and forcing the burden of resolution on programmers, what if we constructed general-purpose data structures that required no manual resolution? These data structures would resolve conflicts inherently, themselves, and depending on your application you could choose which data structure works best for you. +Instead of constructing an all-purpose database and forcing the burden of resolution on programmers, what if we constructed multi-purpose (read: multi, not *all*) data structures that required no manual resolution? These data structures would resolve conflicts inherently, themselves, and depending on your application you could choose which data structure works best for you. Let's try this transfiguration on the shopping cart. Let's strip it down: how does Amazon handle resolution, really? It treats shopping cart versions as sets of items. In order to perform resolution, Amazon unions the two sets. @@ -71,7 +71,6 @@ Let's try this transfiguration on the shopping cart. Let's strip it down: how do Cool. Using this knowledge, let's try to construct our own shopping cart that automatically resolves conflicts. - (Unfortunately Amazon has a leg up on our startup. Their programmers have figured out a way to add multiple instances of a single item into the cart. Users on our website can only add one "Red Candle"" to their shopping cart. This is due to a fundamental limitation in the type of CRDT I chose to exemplify. It's quite possible to have a fully functional cart. Take a look at LWW-Sets.) ### Example @@ -233,20 +232,20 @@ Node 2: { } This is pretty nasty. Jerry has come along and with a few lines of code he's obliterated our nice strong eventually consistent code. Surely there's a better way. ### Guarantees -The original Javascript we wrote down exhibits the property from Section 6 known as *monotonicity*. The union operation ensures that a given node's state is always "greater than or equal to" the states of the other nodes. However, how can we be *sure* that this property is maintained throughout the development of this program? As we've seen, there's nothing stopping an intern from coming along, making a mindless change, and destroying this wonderful property. Ideally, we want to make it impossible (or at least very difficult) to write programs that violate this property. Or, at the very least, we want to make it very easy to write programs that maintain these types of properties. +The original Javascript we wrote down exhibits the property from Section 6 known as logical *monotonicity*. The union operation ensures that a given node's state is always "greater than or equal to" the states of the other nodes. However, how can we be *sure* that this property is maintained throughout the development of this program? As we've seen, there's nothing stopping an intern from coming along, making a mindless change, and destroying this wonderful property. Ideally, we want to make it impossible (or at least very difficult) to write programs that violate this property. Or, at the very least, we want to make it very easy to write programs that maintain these types of properties. But where should these guarantees live? In the above Javascript example, the guarantees aren't guarantees at all, really. There's no restriction on what the programmer is allowed to do - the programmer has simply constructed a program that mirrors guarantees that she has modeled in her brain. In order to maintain properties such as *monotonicity*, she must constantly check the model in her brain against the code. We haven't really helped the programmer out that much - she has a lot of thinking to do. -Databases such as PostgreSQL have issues like this as well, though they handle them quite differently, masters may need to ensure that write have occurred on every slave before the database becomes available for reading. A database system like this has pushed consistency concerns to the IO-level, completely out of the users control. They are enforced on system reads and system writes. This approach gives programmers no flexibility: as demonstrated with our shopping cart example, there's no need for these type of restrictions; we can tolerate inconsistency in order to maintain availability. +Databases such as PostgreSQL have issues like this as well, though they handle them quite differently, masters may need to ensure that writes have occurred on every slave before the database becomes available for reading. A database system like this has pushed consistency concerns to the IO-level, completely out of the users control. They are enforced on system reads and system writes. This approach gives programmers no flexibility: as demonstrated with our shopping cart example, there's no need for these type of restrictions; we can tolerate inconsistency in order to maintain availability. -Why not push the consistency guarantees in between the IO-level and the application-level? {% cite ConsistencyWithoutBorders --file langs-consistency %} { Is there any reason why you as the programmer couldn't program using tools that facilitate these types of monotonic programs? If you're familiar with formal systems -- why not construct a formal system (programming language / library) in which every theorem (program) is formally guarunteed to be monotonic? If it's *impossible* to express a non-monotonic program, the programmer needn't worry about maintaining a direct mapping between their code and their mental model. +Why not push the consistency guarantees in between the IO-level and the application-level? {% cite ConsistencyWithoutBorders --file langs-consistency %} Is there any reason why you as the programmer couldn't program using tools that facilitate these types of monotonic programs? If you're familiar with formal systems -- why not construct a formal system (programming language / library) in which every theorem (program) is formally guaranteed to be monotonic? If it's *impossible* to express a non-monotonic program, the programmer needn't worry about maintaining a direct mapping between their code and his or her mental model. Wouldn't it be great if tools like this existed? ### Bloom Before talking about such tools, I'd like you to forget almost everything you know about programming for a second (unless of course you've never programmed in a Von Neumann-based language in which you sequentially update pieces of memory; which, by the way, you have). -Imagine the following scenario: you are "programming" a node in a cluster of computers. All of the other computers work as expected. When you receive a message (all messages will include an integer), your task is to save the message, increment the integer, and resend the message back to its originator. You must also send messages you've received from `stdin`. Unfortunately, the programming environment isn't like anything you've encountered before. +Imagine the following scenario: you are "programming" a node in a cluster of computers. All of the other computers work as expected. When you receive a message (all messages will include an integer), your task is to save the message, increment the integer, and resend the message back to its originator. You must also send messages you've received from `stdin`. Unfortunately, the programming environment is a little strange. You have access to five buffers: * Messages you have received in the last 5 seconds * Inputs you've received from `stdin` in the last 5 seconds @@ -288,6 +287,7 @@ onFiveSecondInterval(function() { savedBuffer.push(msg); // save message let newMsg = msg.clone() newMsg.integer++; // increment recv'd message + newMsg.flipSourceDestination() sendBuffer.push(newMsg); // send it out }); @@ -305,6 +305,7 @@ on_five_second_interval do saved_buffer << msg new_msg = msg.clone new_msg.integer += 1 + new_msg.flip_source_destination send_buffer << new_msg end @@ -314,7 +315,7 @@ on_five_second_interval do end ``` -We have expressed this model using an event-driven programming style: the main event is `t % 5 = 0`: when the buffers populate & flush. +We have expressed this model using an event-driven programming style: the callbacks are triggered when `t % 5 = 0`: when the buffers populate & flush. Notice we perform a few "copies". We read something from one buffer and place it into another one, perhaps after applying some modification. Perhaps we place a message from a given buffer into two buffers (`recv_buffer` to `saved_buffer` & `send_buffer`). @@ -326,7 +327,8 @@ on_five_second_interval do send_buffer += recv_buffer.map do |msg| # map over the recv_buffer, increment integers, add to send_buffer new_msg = msg.clone new_msg.integer += 1 - new_msg # this block returns new_msg + new_msg.flip_source_destination # send to originator + new_msg # this block returns new_msg end send_buffer += stdin_input_buffer # add stdin messages to the send buffer @@ -335,12 +337,12 @@ end After this block/callback is called, the system automatically flushes & routes messages as described above. -Bloom {% cite Bloom --file langs-consistency %}, a research language developed at UC Berkeley, has a similar programming model to the one described above. Execution is broken up into a series of "timesteps". In the above example, one "timestemp" would be the execution of one `on_five_second_interval` function. Bloom, like the theoretical system above, automatically flushes and populates the buffers before and after each timestep. In the above example, 5 seconds was an arbitrary amount of time. In Bloom, timesteps (rounds of evaluation) are logical tools - they may happen every second, 10 seconds, etc. Logically, it shouldn't affect how your program executes. In reality, Bud's timesteps correspond to evaluation iterations. Your code is evaluated, executed, and the process repeats. +Bloom {% cite Bloom --file langs-consistency %}, a research language developed at UC Berkeley, has a similar programming model to the one described above. Execution is broken up into a series of "timesteps". In the above example, one "timestemp" would be the execution of one `on_five_second_interval` function. Bloom, like the theoretical system above, automatically flushes and populates certain buffers before and after each timestep. In the above example, 5 seconds was an arbitrary amount of time. In Bloom, timesteps (rounds of evaluation) are logical tools - they may happen every second, 10 seconds, etc. Logically, it shouldn't affect how your program executes. In reality, Bud's timesteps correspond to evaluation iterations. Your code is evaluated, executed, and the process repeats. So what does a Bloom program look like? Bloom's prototypal implementation is called Bud and is implemented in Ruby. There are two main parts to a Bloom program: 1. User defined buffers: rather than the four buffers I gave you above, Bloom users can define their own buffers. There are different types of buffers depending on the behavior you desire: - * `channel`: Above, `recv_buffer` and `send_buffer` would be considered channels. They facilitate sending network messages to and from other nodes. Like the messages above, messages sent into these channels contain a "location-specifier", which tells Bloom where the message should be sent. If you wanted to send a message to `A`, you could push the message `(@A, 10)` into your send buffer (in Ruby, `["@A", 10]`). The `@` denotes the location-specifier. - * `table`: Above, `saved_buffer` would be considered a table. The contents of tables persist across timesteps. + * `channel`: Above, `recv_buffer` and `send_buffer` would be considered channels. They facilitate sending network messages to and from other nodes. Like the messages above, messages sent into these channels contain a "location-specifier", which tells Bloom where the message should be sent. If you wanted to send a message to `A`, you could push the message `(@A, 10)` into your send buffer (in Ruby, `["@A", 10]`). The `@` denotes the location-specifier. At the end of the timestep (or callback execution in the above example), these buffers are flushed. + * `table`: Above, `saved_buffer` would be considered a table. The contents of tables persist across timesteps, which means tables are never flushed. 2. Code to be executed at each timestep. A Bloom (Bud) program can be seen as the inside of the block passed to `on_five_second_interval`. In fact, it looks very similar, as we'll see. For the purposes of this chapter, let's assume `stdin_input_buffer` is a special kind of channel in which are sent in via `stdin`. Let's also assume this channel exists in all Bloom programs. @@ -359,7 +361,7 @@ module Incrementer end ``` -The first line of `state` means: declare a channel called `network_channel` in which messages are 3-tuples. The first field of the message is called `dst`, the second `src`, and the third is called `integer`. `@` is our location-specifier, so if a program wants to send a message to a node at a given identifier, they will place it in the first `dst` field. +The first line of `state` means: declare a channel called `network_channel` in which messages are 3-tuples. The first field of the message is called `dst`, the second `src`, and the third is called `integer`. `@` is our location-specifier, so if a program wants to send a message to a node at a given identifier, they will place it in the first `dst` field. For example, a message destined for `A` would look like `['A', 'me', 10]`. The `@` denotes the location-specifier within the collection's "schema". The second line means: declare a table (persists) called `saved_buffer` in which messages follow the same format as `network_channel`. There's no location specifier since this collection is not network-connected. @@ -401,7 +403,7 @@ def increment_messages network_channel <~ network_channel.map { |x| [x.src, x.dst, x.integer] } end ``` -Here, we take messages we've received from the network channel and send them back into the network channel. The `<~` operator says "copy all of the elements in the right-hand-side and eventually send them off onto the network in the channel on the left-hand-side". So, we map over the contents of network channel *in the current timestep*: switching the `src` and `dst` fields, and incrementing the integer. This mapped collection is passed back into the network channel. Bud will ensure those messages sent off at some point. +Here, we take messages we've received from the network channel and send them back into the network channel. The `<~` operator says "copy all of the elements in the right-hand-side and eventually send them off onto the network in the channel on the left-hand-side". So, we map over the contents of network channel *in the current timestep*: switching the `src` and `dst` fields, and incrementing the integer. This mapped collection is passed back into the network channel. Bud will ensure that those messages are sent off at some point. ``` declare @@ -411,7 +413,7 @@ end ``` In `save_messages`, we use the `<=` operator. `<=` says "copy all of the elements in the right-hand-side and add them to the table on the left-hand-side." It's important to note that this movement occurs *within the current timestep*. This means if `saved_buffer` is referenced elsewhere in the code, it will include the contents of `network_channel`. If we had used the `<+` operator instead, the contents of `network_channel` would show up in `saved_buffer` in the *next* timestep. The latter is useful if you'd like to operate on the current contents of `saved_buffer` in the current timestep but want to specify how `saved_buffer` should be updated for the next timestep. -Remember, all of this code is executed in each timestep - the separation of code into separate methods is merely for readability. +Remember, all of this code is executed in *each* timestep - the separation of code into separate methods is merely for readability. ``` declare @@ -424,7 +426,7 @@ end #### Details -Examine Bloom's "style". Compare it to your (probably) standard way of programming. Compare it to the Javascript & Ruby examples within this strange "timestep" model. Bloom has a more "declarative" style: what does this mean? Look at our Javascript: +Examine Bloom's "style". Compare it to your standard way of programming. Compare it to the Javascript & Ruby timestep/callback examples. Bloom has a more "declarative" style: what does this mean? Look at our Javascript: ```javascript onFiveSecondInterval(function() { @@ -432,6 +434,7 @@ onFiveSecondInterval(function() { savedBuffer.push(msg); // save message let newMsg = msg.clone() newMsg.integer++; // increment recv'd message + newMsg.flipSourceDestination(); sendBuffer.push(newMsg); // send it out }); @@ -441,11 +444,11 @@ onFiveSecondInterval(function() { }); ``` -"Every five seconds, loop over the received messages. For each one, do this, then that, then that." We are telling the computer each step we'd like it to perform. In Bud, however, we describe the state of tables and channels at either the current or next timestep using operators and other tables and channels. We describe what we'd like our collections to include and look like, rather than what to do. You declare what you'd like the state of the world to be at the current instant and at following instants. +"Every five seconds, loop over the received messages. For each message, do this, then that, then that." We are telling the computer each step we'd like it to perform. In Bud, however, we describe the state of tables and channels at either the current or next timestep using operators and other tables and channels. We describe what we'd like our collections to include and look like, rather than what to do. You declare what you'd like the state of the world to be at the current instant and at following instants. #### Isn't this chapter about consistency? -It's time to implement our shopping cart in Bloom. We are going to introduce one more collection: a `periodic`. For example, `periodic :timer 10` instantiates a new periodic collection. This collection is "not empty" every 10 seconds. Alone, it's not all that useful. However, when `join`'d with another table, it can be used to perform actions every `x` seconds. +It's time to implement our shopping cart in Bloom. We are going to introduce one more collection: a `periodic`. For example, `periodic :timer 10` instantiates a new periodic collection. This collection becomes "populated" every 10 seconds. Alone, it's not all that useful. However, when `join`'d with another table, it can be used to perform actions every `x` seconds. ```ruby module ShoppingCart @@ -480,7 +483,7 @@ end * `send_items`: join our cart with the 10-second timer. Since the timer only "appears" every 10 seconds, this `join` will produce a result every 10 seconds. When it does, send all cart items to all peers via `send_mcast`. * `receive_items`: when we receive a message from a peer, add the item to our cart. -Functionally, this code is equivalent to our working Javascript shopping cart implementation. A few important things to note: +Functionally, this code is equivalent to our working Javascript shopping cart implementation. However, there are a few important things to note: * In our Javascript example, we broadcasted our entire cart to all peers. When a peer received a message, they unioned their current cart with the received one. Here, each node broadcasts each element in the cart. When a node receives an item, it adds it to the current cart. Since tables are represented as sets, repeated or unordered additions do not matter. You can think of `{A, B, C}.add(D)` as equivalent to `{A, B, C}.union({D})`. * You cannot add items twice. Since tables are represented as sets and we simply add items to our set, an item can only ever exist once. This was true of our Javascript example as well. * You still cannot remove items! @@ -491,7 +494,7 @@ Bloom has leveraged the montononic, add-only set and constructed a declarative p Bloom's programming model is built around the set. As Aviral discussed in the previous chapter, however, sets are not the only monotonic data structures. Other CRDTs are incredibly useful for programming eventually consistent distributed programs. Recall that a *bounded join semilattice* (CRDT) can be represented as a 3-tuple: `(S, U, ⊥)`. `S` is the set of all elements within the semilattice. `U` is the `least-upper bound` operation. `⊥` is the "least" element within the set. For example, for add-only sets, `S = the set of all sets`, `U = union` and `⊥ = {}`. Elements of these semilattices, when `U` is applied, can only "stay the same or get larger". Sets can only stay the same size or get larger - they can never rollback. For some element `e` in `S`, `e U ⊥` must equal `e`. -For a semilattice we'll call `integerMax`, `S = the set of all integers`, `U = max(x, y)`, and `⊥ = -Infinity`. +For a semilattice we'll call `integerMax`, `S = the set of all integers`, `U = max(x, y)`, and `⊥ = -Infinity`. Hopefully you can see that elements of this lattice (integers) "merged" with other elements of this lattice never produce a result less than either of the merged elements. These semilattices (and many more!) can be used to program other types of distributed, eventually consistent programs. Although sets are powerful, there might be more expressive ways to describe your program. It's not difficult to imagine using `integerMax` to keep a global counter across multiple machines. @@ -510,7 +513,7 @@ interface Lattice { } ``` -[I am purposely leaving out morphisms & monotones for the sake of simplicity.] +Heather: [I am purposely leaving out morphisms & monotones for the sake of simplicity.] This provides the user with much more freedom in terms of the types of Bloom programs she can write. @@ -518,7 +521,7 @@ This provides the user with much more freedom in terms of the types of Bloom pro Bloom aims to provide a new model for writing distributed programs. And since bloom only allows for monotonic data structures with monotonicity-preserving operations, we're safe from Jerry the intern, right? -Wrong. Unfortunately, I left out an operator from Bloom's set of collection operators. `<-` removes all elements in the right-hand-size from the table in the left-hand-side. As we've seen from Jerry's work on our original Javascript shopping cart implementation, naively attempting to remove elements from a distributed set is not a safe operation. Rollbacks can potentially destroy the properties we worked so hard to achieve. So what gives? Why would the Bloom developers add this operation? +Wrong. Unfortunately, I left out an operator from Bloom's set of collection operators. `<-` removes all elements in the right-hand-size from the table in the left-hand-side. So Bloom's sets are *not* add-only. As we've seen from Jerry's work on our original Javascript shopping cart implementation, naively attempting to remove elements from a distributed set is not a safe operation. Rollbacks can potentially destroy the properties we worked so hard to achieve. So what gives? Why would the Bloom developers add this operation? Despite putting so much emphasis on consistency via logical monotonicity, the Bloom programmers recognize that your program might need *some* coordination. @@ -526,13 +529,13 @@ In our example, we don't require coordination. We accept the fact that a user ma For our shopping cart examples: when a client asks a given node what's in her cart, that node will respond with the information it's received so far. We know this information won't be *incorrect*, but this data could be *stale*. That client might be missing information. -The Bloom team calls these points in your program *points of order*. They are points in your program where coordination may be required. In fact, the Bloom developers provide analysis tools for identifying points of order within your program. There's no reason why you couldn't implement a non-monotonic shopping cart in which all nodes must synchronize before giving a response to the user. The Bloom analysis tool would tell you where the points of order lie in your program and you would need to add coordination. +The Bloom team calls points like the one above, the user asking to checkout the contents at the cart of a given node, *points of order*. These are points in your program where coordination may be required - depending on when and who you ask, you may receive a different response. In fact, the Bloom developers provide analysis tools for identifying points of order within your program. There's no reason why you couldn't implement a non-monotonic shopping cart in which all nodes must synchronize before giving a response to the user. The Bloom analysis tool would tell you where the points of order lie in your program, and you as the programmer could decide whether or not (and how!) to add coordination. So what does Bloom really give us? First off, it demonstrates an unusual and possibly more expressive way to program distributed systems. Consistency-wise, it uses sets under the hood for its collections. As long as you shy away from `<-` operator, you can be confident that your collections will only monotonically grow. Since the order of packets is not guaranteed, structuring these eventually consistent applications is reasonably easy within Bloom. BloomL also gives us the power to define our own monotonic data structures by "implementing" the lattice interface. However, Bloom makes it easy to program non-monotonic distributed programs as well. Applications may require coordination and the `<-` operator in particular can cause serious harm to our desired formal properties. Luckily, Bloom attempts to let the programmer know exactly when coordination may be required within their programs. Whenever an operation may return a stale or non-up-to-date value, Bloom's analysis tools let the programmer know. -Another thing to consider: BloomL's user-defined lattices are just that - user-defined. It's up to the programmer to ensure that the data structures that implement the lattice interface are actually valid lattice structures. If not, Bloom can't help you. +Another thing to consider: BloomL's user-defined lattices are just that - user-defined. It's up to the programmer to ensure that the data structures that implement the lattice interface are actually valid lattice structures. If your structures don't follow the rules, your program will behave in some seemingly strange ways. Currently Bloom exists as a Ruby prototype: Bud. Hypothetically speaking, there's nothing stopping the programmer from writing normal, sequentially evaluated Ruby code within Bud. This can also cause harm to our formal properties. @@ -552,9 +555,28 @@ For those of you unfamiliar with Erlang: a *process* can be thought of as an ind ### Utilization -Lasp is an Erlang library, and for good reason. Remember the initial discussion and reasoning for models such as Bloom and Lasp: we have a specific type of application that doesn't require tight consistency constraints. The constraints that do exist have been formalized, and we can be quite sure that by using a DSL like Lasp, we'll be safe from interns like Jerry. But Lasp can't do everything. More generally, eventual consistency doesn't solve every problem. +Compare Lasp and Bloom: + +Lasp +* An Erlang library, meant to be used in every-day Erlang programs. +* Built-in CRDTs. Does not allow user-defined CRDTs (for now). +* All data structures are CRDTs and all operations are logically monotonic. +* Thus, it's essentially impossible to construct a non-monotonic program *using only the Lasp library*. +* It is possible to use Lasp in a non-monotonic way with disrupting outer Erlang code. +* Follows well-known functional programming patterns and is compatible with optimal Erlang style. + +Bloom: +* Aims to be a full-featured language. Is not meant to be embeddable. +* Built-in set collections only. Allows user-defined CRDTs. +* Its sets are not add-only and thus not exclusively logically monotonic. User-defined lattices carry no formal proofs of their consistency gaurantees. +* It's possible to construct non-monotonic programs. Using the `<-` operator, for example. +* With the prototype, Bud, it's possible to use normal Ruby code to disrupt Bloom's properties. But this is more a result of the prototype implementation, not the design. +* Uses a unique programming model based on temporal logic. +* Contains an analysis tool that tells programmers which points in their code might require coordination, depending on the consistency concerns of the application. + +Remember the initial discussion and reasoning for models such as Bloom and Lasp: we have a specific type of application that doesn't require tight consistency constraints. The constraints that do exist have been formalized, and we can be quite sure that by using a DSL like Lasp, we'll be safe from interns like Jerry. But Lasp can't do everything. More generally, eventual consistency doesn't solve every problem. -PostgreSQL enforce very specific and restrictive IO-level consistency, and this was too much for our needs. But it's certainly not too much for *all* needs. There certainly are applications (take banking, for example) in which consistency is extremely important. You certainly are not allowed to double spend your money depending on how fast you can travel to a different server, so eventual consistency is not enough! All servers must coordinate. +PostgreSQL, for example, enforced very specific and restrictive IO-level consistency, and this was too much for our needs. But it's certainly not too much for *all* needs. There certainly are applications (take banking, for example) in which consistency is extremely important. You certainly are not allowed to double spend your money depending on how fast you can travel to a different server, so eventual consistency is not enough! All servers must coordinate. There's a key principle here, however: distributed programming models that attempt to accomodate everything end up doing nothing well; models that accept compromises and formalize certain properties end up being extremely useful for a subset of domains. -- cgit v1.2.3 From 98a6f1f836dd3be15d552fb7c0a1d05ee05d34d2 Mon Sep 17 00:00:00 2001 From: James Larisch Date: Sat, 17 Dec 2016 16:29:01 -0500 Subject: More conclusion fixes --- chapter/7/langs-consistency.md | 18 ++++++++++++++---- 1 file changed, 14 insertions(+), 4 deletions(-) (limited to 'chapter') diff --git a/chapter/7/langs-consistency.md b/chapter/7/langs-consistency.md index edaee53..af78294 100644 --- a/chapter/7/langs-consistency.md +++ b/chapter/7/langs-consistency.md @@ -574,15 +574,25 @@ Bloom: * Uses a unique programming model based on temporal logic. * Contains an analysis tool that tells programmers which points in their code might require coordination, depending on the consistency concerns of the application. -Remember the initial discussion and reasoning for models such as Bloom and Lasp: we have a specific type of application that doesn't require tight consistency constraints. The constraints that do exist have been formalized, and we can be quite sure that by using a DSL like Lasp, we'll be safe from interns like Jerry. But Lasp can't do everything. More generally, eventual consistency doesn't solve every problem. +Although they are fundamentally different in many ways, Lasp and Bloom accept a key reality: it's probably impossible to program using eventual consistency gaurantees only. It works for shopping carts, but there will always be situations where coordination between machines will need to occur. Lasp and Bloom's designs reflect the different approaches for dealing with this harsh truth. -PostgreSQL, for example, enforced very specific and restrictive IO-level consistency, and this was too much for our needs. But it's certainly not too much for *all* needs. There certainly are applications (take banking, for example) in which consistency is extremely important. You certainly are not allowed to double spend your money depending on how fast you can travel to a different server, so eventual consistency is not enough! All servers must coordinate. +Lasp, on one hand, plans to be an embeddable eventually-consistent library. If you're an Erlang developer and you recognized a situation in which you can accept eventual consistent properties, you can reach for the Lasp library. Within your existing code, you can add communication mechanisms using Lasp and be confident of the properties advertised by eventual consistent systems. No need to change your entire system or re-write code in a different language. Since Lasp does not allow the expression of non-monotonic programs, you express non-monotonicity *outside* of the Lasp sections in your code. -There's a key principle here, however: distributed programming models that attempt to accomodate everything end up doing nothing well; models that accept compromises and formalize certain properties end up being extremely useful for a subset of domains. +Bloom, on the other hand, aims to be an entirely new model for expressing distributed systems problems. By using CRDT-like sets for their collections, they can encourage a declarative way of programming without enforcing too much coordination. They even let the user define their own lattices with BloomL to further encourage this type of programming. But since there will always be times where coordination is necessary, Bloom allows for operations that may require coordination. They even allow the user to perform non-monotonic operations such as `<-`. Bloom, in a way, must do this. They must provide the user with mechanisms for coordination, since they aim to create a new model for expressing distributed systems programs. Lasp is embeddable, so it can perform one specific job. Bloom is not, so it must allow many types of programs. In order to ameliorate this, Bloom provides the programmer with anaylsis tools to help the programmer identify points in the code that may not be totally safe. The programmer can then decide to coordinate or ignore these "points of order". Most programming languages are "general-use". This works for single machine programming. As the world moves toward distributed programming, programmers must adopt models / languages / libraries that are built for their domain. It forces serious thought on the part of the programmer: what *exactly* am I trying to achieve, and what am I willing to sacrifice? -We've known for quite a while that when we're talking about multiple machines, we can't have it all. Our tools must now reflect this mantra. Our sanity and the safety of our programs depends on it. +Bloom could potentially facilitate distributed systems programming through a new, temporal model. The Bloom developers have designed a language for a specific purpose: distributed programming. The Lasp developers take this philosophy even further: let's design a library for a specific subset of distributed systems programming. Although one goes deeper than the other, the two languages share an idea: languages / models should be build for subsets of the computing domain. Distributed systems produce difficult problems. When we put our heads together and develop tools to facilitate distributed systems programming (Bloom) and always *eventually consistent* distributed systems programming, programming gets easier. Fewer bugs pop up, and it becomes easier to formally reason about the behavior of our programs. + +When a language or model tries to do everything well, it cannot provide formal guarantees or tools to facilitate certain problem solving. Since different domains have totally different needs and issues to deal with, general purpose programming languages simply try to provide the minimum required for a wide variety software problems. + +If we shift our mindset as software developers and begin to develop and look for tools to help us with specific problems and domains of problems, we can leverage computers much more than we do today. Our tools can provide relevant feedback and help us design our systems. They can even provide formal properties that we need not question. + +Critically, it requires a narrowing of our problem domain. It means inspecting our problem and asking what we need, and what's not so important? + +In this chapter, we examined ways in which tools can help us leverage eventually consistent distributed systems. But there's no reason why this philosophy couldn't be applied to other subsections of the CAP pyramid. In fact, there's no reason why this philosophy couldn't be applied to other areas of computing in general. Why are both video games and distributed systems programmed using the same language & models? + +Even if you don't encounter consistency issues in your day-to-day life, this idea applies to many areas of computing and tools in general. Hopefully you can begin to ask yourself and those around you: what tasks are we trying to accomplish, and how can our tools help us accomplish them? ## References -- cgit v1.2.3 From c2771b35ed511917ace99e149d0f5eef56a8c7e4 Mon Sep 17 00:00:00 2001 From: James Larisch Date: Sat, 17 Dec 2016 17:21:25 -0500 Subject: Add more Lasp --- chapter/7/langs-consistency.md | 29 +++++++++++++++++++++++++++++ 1 file changed, 29 insertions(+) (limited to 'chapter') diff --git a/chapter/7/langs-consistency.md b/chapter/7/langs-consistency.md index af78294..9838876 100644 --- a/chapter/7/langs-consistency.md +++ b/chapter/7/langs-consistency.md @@ -552,6 +552,35 @@ A Simple Lasp Program is defined as either a: For those of you unfamiliar with Erlang: a *process* can be thought of as an independent piece of code executing asynchronously. Processes can receive messages and send messages to other processes. Process can also subscribe (I think) to other processes' messages. +Programming in Erlang is unique in comparison to programming in Ruby or Javascript. Erlang processes are spun off for just about everything - and they are independent "nodes" of code acting independently while communicating with other processes. Naturally, distributed systems programming fits well here. Processes can be distributed within a single computer or distributed across a cluster of computers. So communication between processes may move over the network. + +Distribution of a data structure, then, means the transmission of a data structure across network-distributed processes. If a client asks for the state of the shopping cart in Beijing, the processes located on the computer in Beijing will respond. However, the processes in New York may disagree. Thus, our task is to distribute our data structures (CRDTs, right?) across distributed processes. + +So, what's a "Lasp process"? A Lasp process is a process that operates on lattice elements, or CRDTs. Three popular Lasp processes are `map`, `fold`, and `filter`. + +* `map`: If you're familiar with functional programming, these functions shouldn't appear too foreign. `map` spins off a never-ending process which applies a user-supplied `f` to all the replicas of a given CRDT this processes receives. +* `fold`: Spins off a process that continously folds input CRDT values into another CRDT value using a user-provided function. +* `filter`: Spins off a process that continously picks specific CRDT input values based on a user-provided filtering function. + +Drawing parallels to our mock-Bloom-Ruby-callback implementation, we remember that CRDT modifications and movements can be modeled using functional styles. In Bloom, we dealt with mapping values from "collections" to other "collections". These collections were backed by CRDT-like sets. + +Here, we are mapping "streams" of CRDT instances to other CRDT instances using the same functional programming methods. + +However, here, the stream manipulations occcur within unique processes distributed across a network of computers. These processes consume CRDTs and produce new ones based on functions provided by the user. + +There's one hiccup though: the user can't provide *any* function to these processes. Since our datatypes must obey certain properties, the functions that operate on our datas must preserve these properties. + +Recall that within a lattice, a partial order exists. One element is always `<=` another element. For example, with add-only sets, `{A} <= {A} <= {A, B} <= {A, B} <= {A, B, C}`. A *monotonic* function that operates over the domain of add-only sets must preserve this partial ordering. For example - if `{A} <= {A, B}` and `f` is a monotonic function that operates over add-only sets, `f({A}) <= f({A, B})`. + +This ensures the preservation of our consistency properties across our ever-interacting processes. + +#### A Library + +Remember that Lasp is an Erlang *library*. Within your existing Erlang program, you're free to drop in some interacting Lasp-processes. These processes will communicate using CRDTs and functions over CRDTs. As such, your Lasp sub-program is guaranteed to exhibit strong eventual consistency properties. + +However, the rest of your Erlang program is not. Since Lasp is embeddable, it has no control over the rest of your Erlang program. You must be sure to use Lasp in a safe way. But since it doesn't provide the programmer with the ability to perform non-monotonic operations within the Lasp-context, the programmer can have significant confidence in the eventual consistency of the Lasp portion of the program. + +Bloom provided a new model for distributed programming, where Lasp aims to provide existing distributed systems with a drop-in solution for adding eventually consistent parts to their systems. ### Utilization -- cgit v1.2.3 From bf4cd5b0534edfcdca171ccc0f3bc142cd50bf64 Mon Sep 17 00:00:00 2001 From: James Larisch Date: Sat, 17 Dec 2016 17:23:21 -0500 Subject: jerry the intern --- chapter/7/langs-consistency.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'chapter') diff --git a/chapter/7/langs-consistency.md b/chapter/7/langs-consistency.md index 9838876..50f3926 100644 --- a/chapter/7/langs-consistency.md +++ b/chapter/7/langs-consistency.md @@ -578,7 +578,7 @@ This ensures the preservation of our consistency properties across our ever-inte Remember that Lasp is an Erlang *library*. Within your existing Erlang program, you're free to drop in some interacting Lasp-processes. These processes will communicate using CRDTs and functions over CRDTs. As such, your Lasp sub-program is guaranteed to exhibit strong eventual consistency properties. -However, the rest of your Erlang program is not. Since Lasp is embeddable, it has no control over the rest of your Erlang program. You must be sure to use Lasp in a safe way. But since it doesn't provide the programmer with the ability to perform non-monotonic operations within the Lasp-context, the programmer can have significant confidence in the eventual consistency of the Lasp portion of the program. +However, the rest of your Erlang program is not. Since Lasp is embeddable, it has no control over the rest of your Erlang program. You must be sure to use Lasp in a safe way. But since it doesn't provide the programmer with the ability to perform non-monotonic operations within the Lasp-context, the programmer can have significant confidence in the eventual consistency of the Lasp portion of the program. We still aren't totally safe from Jerry the intern, since Jerry can modify our outer-Erlang to do some dangerous things. Bloom provided a new model for distributed programming, where Lasp aims to provide existing distributed systems with a drop-in solution for adding eventually consistent parts to their systems. -- cgit v1.2.3 From 7aa8cd97fc451f28dbdb9d95af808e27c598054f Mon Sep 17 00:00:00 2001 From: James Larisch Date: Sat, 17 Dec 2016 17:24:40 -0500 Subject: remove cool --- chapter/7/langs-consistency.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'chapter') diff --git a/chapter/7/langs-consistency.md b/chapter/7/langs-consistency.md index 50f3926..b19ba23 100644 --- a/chapter/7/langs-consistency.md +++ b/chapter/7/langs-consistency.md @@ -69,7 +69,7 @@ Let's try this transfiguration on the shopping cart. Let's strip it down: how do { Red Candle, Blue Skateboard } U { Red Candle, Green Umbrella } == { Red Candle, Blue Skateboard, Green Umbrella } ``` -Cool. Using this knowledge, let's try to construct our own shopping cart that automatically resolves conflicts. +Using this knowledge, let's try to construct our own shopping cart that automatically resolves conflicts. (Unfortunately Amazon has a leg up on our startup. Their programmers have figured out a way to add multiple instances of a single item into the cart. Users on our website can only add one "Red Candle"" to their shopping cart. This is due to a fundamental limitation in the type of CRDT I chose to exemplify. It's quite possible to have a fully functional cart. Take a look at LWW-Sets.) -- cgit v1.2.3