June 8, 2017 at 10:08How to pass a law or data processing in distributed systems in a clear language
- Transfer
If your work is not related to computer technology, you probably did not think long about how the data is stored on computers or in the cloud. I'm not talking about the physical mechanisms of hard drives or memory chips, but about something at the same time more complex and more understandable than you think.
If you have a piece of data that many people want to read and immediately edit, for example, a common text file, bank account or the world in a multiplayer game, how to reach a general agreement with what is in the document and make sure that no one overwrites someone else’s work? This is a consensus problem in distributed systems , and in order to deal with this, I will have to talk about the sheep, dictators and fictional islands of ancient Greece.
“What other islands?” You ask?
It turns out that the original scientific article on one of the most important methods used to solve this problem was written in the form of a lengthy discussion of how the fictitious parliament of the ancient Greek island of Paxos (Paxos) in part managed to pass laws, despite the fact that no one of the parliamentarians it was impossible to reliably say when he would appear in parliament. This is a great metaphor for how a group of people can agree on what to write to a file, provided that part of the group may not be available for some indefinite time. The original article is one of the funniest serious science articles ever published and one of the best explanations for the complex algorithm I have ever seen.
The reason this metaphor works so well is that in both cases with files and laws we have some data that many people want to change, many people want to read, but no one wants to spend all on this process your time. Simultaneous reading of a book with a set of laws is limited by the number of people who can see the book at a time, just as reading a file can be limited by the speed at which data can be received from disk. Simultaneous recording requires everyone to agree not to overwrite each other's decision, but without lengthy debate to make it. Besides the fact that each person in the world will take turns using a book, how can we solve this problem?
Instead of talking about file systems and database operations, let's move on to the islands of the fake Aegean where coincidences with reality are random and residents are obsessed with issuing decrees and laws. We just need to make sure everyone can read the law when they need it. There is a way through several winding stories, and by the time we finish, you will be aware of the problem of distributed consensus, in the form in which IT professionals face it. Except for the sheep.
By the way, there will be many islands, and their names are completely invented, except for the one that was the cause of this story, but more on that later.
We begin our story with the simplest case on the island of Pseudemoxos. Here lives one hermit who writes laws and decrees for his own use. At first he used a very simple and understandable method: a notebook and a pencil. He could add laws, change laws and reorganize laws as he wanted, just erasing and writing down new ones wherever he wanted (in fact, this is how the disks on our computers worked until the end of the 90s).
This method seemed to work quite well, except for paper that was too frayed when erased. However, the hermit realized the terrible flaw of such a decision, when one day a box of dubious burritos was thrown ashore. Making changes to the law - erasing the text and starting to write something, the hermit experienced what we politely call "an emergency at work." When the somewhat shabby hermit returned to his code, he discovered that he not only forgot what he was going to write, but now the empty space in the middle of the book is not filled with either old or new law, and the scribbles written in haste cannot be read!
A metaphor describes what happens to a computer or program when it crashes - the data on the disk can be hopelessly distorted. The more serious failures of the hermit can be compared with events such as damage to the block of magnetic heads, which can damage not only written words, but also leave a rather unpleasant and constant mark on the entire page.
These issues are resolved using logging. The scheme is to not erase anything, just like people keep accounting books or a laboratory observation diary. Now our hermit is holding a stack of papers, and when he wants to make changes to the laws, he adds a new entry to his journal:
June 4, 10:32 - Add to food safety laws: it is forbidden to consume burritos that have been at sea for an indefinite period of time.
Each edit, whether it is an insert, change or delete, is written at the end of the log with a pen. The hermit is protected from an emergency because he never erases records. In the worst case, there is an incomplete, corrupted log entry or traces of an unsuccessful write attempt that can simply be ignored. The journal has the added benefit of recording all changes. To see how the law looked a year ago, our hermit can simply read the magazine and stop at that date.
One obvious drawback of the magazine is that it is harder to read than a notebook. To find out about the current version of the food safety law, you need to start from the very beginning of the magazine and read to the end, tracking all the changes. As the volume of the magazine increases over time, the process becomes more and more burdensome.
To simplify things, our hermit keeps a stack of empty directories. Whenever a magazine becomes too voluminous, it takes time to make a set of laws: it reads the magazine from beginning to end, formulating the whole law in an up-to-date state, and then writes this state into a collection of laws. On the cover of the code of laws, he writes: "This is the state of the law on [such and such a date]." Further use of the law requires only that he read the code of laws and the journal of changes made after the date of collection of the law. Logs older than this date can be saved if sometimes a change history is required before the set, or simply thrown away.
If our hermit is too busy developing new legislation and cannot regularly make a set of laws, you can call a clerk (that is, a second computer program running in parallel with the first) to help him. The scribe will read the magazine until some agreed time, write a code of laws and inform the hermit that he has finished so that he can start using the new collection. There is no need to tell the scribe anything in order to carry out his work, so the hermit can continue his work in silence.
This method has even more advantages. Our hermit has become widely known for his wisdom (for example, his lessons on refusing Mexican cuisines delivered by sea), many people may want to read his laws. As long as these readers are satisfied with the code of laws from a specific date, they can make their own copies and read them freely without the need to disturb the sage. Only a person who needs the latest version of laws should contact him directly.
(The use of magazines in personal computers began in the late 1990s and became widespread in the mid-2000s. Your computer probably uses journaling now.)
Near the island of Psevdomoxos is the larger island of Fotas. This island is not very populated, but there are enough people for all residents to agree that they need a consolidated system of laws to manage their lives. Nevertheless, the residents of Fotassica are known for their irreconcilable independence: they do not allow any other resident or group to rule them, and therefore decided that any resident of Fotas would have the power to pass the law. To do this, simply write the law on a piece of paper with the date, time and your name and send a messenger with him to the Fotas Library, where the clerk will add it to law journals.
(This means that many people try to save changes to a single file at the same time, without first making consensus on what will be in the file.)
To see some cases when something may go wrong, we start the story with Agniya, who lives on one of the coasts of the island and is very concerned about the purity of ritual sacrifices. She introduces the law:
June 1, noon - Law 32.1.2 on the sale of sheep is amended as follows: Under pain of death, it is forbidden to sell or acquire sheep whose coat is not completely white. Signed, Agnia.
On the other side of the island, Bazil, who has several black sheep with whom he has difficulty selling, writes his law:
June 1, noon - Law 32.1.2 on the sale of sheep changes as follows: No one can refuse to buy or sell sheep due to the color of the coat. Signed, Basil.
A little later, the clerk discovers two new laws with the same time stamp. What should he do? When Bazil comes to the city to sell the black sheep to Galatea, and she refuses to buy non-white sheep, they will go to read the code of laws. Which version of the law should they use? And what will happen when the clerk tries to collect the following code of laws? (If two people tried to simultaneously write different data to the same part of the same file, the result can be absolutely any.)
To illustrate a more delicate problem, imagine that Agnia wants to perform the read-modify-write operations of the law - she looks at the current law, decides to make changes, and then writes it down. But while she does this, Basil introduces a contradiction into the law. For example, at 10:00 Agnia reads the law
Section 32.1.3. Any person selling a goat must pay a tax equal to one coin to the general fund of the library.
She ponders and writes the following message at 10:02:
June 1, 10:02 - In Law 32.1.3 you need to change “equal to one coin” to “equal to two coins”. Signed, Agnia.
Unfortunately, at 10:01, Bazil, who hates goat taxes, writes:
June 1, 10:01 - Law 32.1.3 is replaced by "Mid-February - National Olive Day." So there you go. Signed, Basil.
Our scribe, trying to reconcile the laws and put them in order, will be very confused: when he gets to the message from Agniya, the law 32.1.3 already sets the National Olive Day and nowhere is mentioned “equal to one coin”. What should he do? Imagine that Basil replaces “pay to the general fund of the library” with “pay Basil!”.
Similar situations happen when several authors compete when editing the same code of laws. There are many solutions, each of which has its pros and cons. These solutions can be divided into two main types of models. One type is “ultimately consistent” or “eventual consistency,” where several rules governing recording allow everyone to record simultaneously without talking to each other. This model ensures that in the absence of new updates for some time all copies of the data (replicas) will become consistent. The costs of this approach are that no one can know the exact state of the law at the moment, everyone can only know what it was recently. Another model is “strict consistency,” in which all kinds of recording are possible,
Both types of models are useful. Sometimes you have information for which the norm is to be a little outdated. For example, when the residents of Fotas make their annual photo album. They exchange photos with each other and there is no need to have the latest photos, so a simpler “consistency in the end” would be good. On the other hand, “strict coherence” will be more useful for these laws, despite its costs. (This is also true for computers. For example, the images that you upload to Google are stored in the system with “consistency in the long run”, while the access control lists that determine the viewing rights are stored using strict agreement)
Back to Fotas Island .
We could easily solve the first of our problems - conflicting laws with the same time stamp, simply adding a rule for tie-break so that no marks could be the same. For example, we could add the author’s name to the label in alphabetical order, so that in the case of a race, changes from Agnia will always be made before Basil. (Or, if the names match, we can assign a unique number to each resident). After the timestamps no longer match, there is no confusion. Galatea comes into the city, and the law of Basil is the only one.
If such mutual rewriting is a problem, it can be avoided by first agreeing on who can write something. For example, in one week Agnia can only edit even laws, while Bazil is odd, and vice versa next week. (In computers, the file space is often divided so that two authors never try to write the same file at all, and even more so at the same time. For example, each newly uploaded photo can be automatically assigned a unique name.)
To solve the second problem, we destroy the possibility of its existence: we change the rules of journalization in order to prohibit amendments, allowing only a complete replacement, addition or removal. This means that no wording in the journal can depend on the current state of the law for its interpretation. Agnia would have to write her law in the form
of June 1, 10:02 - Law 32.1.3 is replaced by "Any person selling a goat must pay a tax equal to two coins to the Senate." Agnia.
Since her record had a later timestamp, her version of the law easily defeats the version of Basil.
Such a system of writing laws has the advantages of speed and simplicity: everyone can write a law at any time, without consulting with anyone else. However, using laws is becoming an amazingly difficult task. If you want to know the current tax rate for the sale of goats, you go to the library and ask to read Law 32.1.3. Arriving at 10:05, you will read the code of laws and the journal of changes. The law says: “Any person selling a goat must pay a tax equal to one coin to the Senate.”
You see, Agnia changed the law at 10:02, but her messenger has not arrived yet! To make the situation a little easier, messengers can register in the library: whenever a messenger arrives from each resident, after delivering a message, they write a note on the board indicating that all messages from the photo messenger were delivered at such and such a time. Then the visitor can look at the board and see that the last message from Agnia was at 9 in the morning, and from Vasily at 7 in the evening. Now you at least know that the laws that you are reading are accurate from 7 o'clock the previous evening - the earliest time shown on the board, and all changes written before this time should have arrived. (This time is called the "low-water mark")
Of course, if a particular citizen is not very conflicting, updates from him may be rare, and everyone will ask a question: “Has the change just not yet reached the library or are there simply no?” To avoid this problem, every photo resident should send a messenger to the library regularly and regardless of whether they have any updates or not, so that the board remains relevant.
The inhabitants of Fotas are creative people, so they quickly realized that this constant stream of messengers could simplify their lives otherwise. Instead of making tedious trips to the library, they can simply keep their own copy of the code of laws and the change journal. Now their messenger every time comes back with all the latest changes in the journal, as well as with a copy of the dates that were on the board. They update their copies and may refer to them.
However, as the population of Fotas increased, the movement of messengers running to the library became a problem. For scribes copying magazines and vaults, the task of simply passing the law on changing the goat tax began to be solved terribly slowly. Fortunately, the photo community realized that they had already solved their problem:having their own copies of the law, they no longer need one central library!
Instead, several branch libraries were opened. Messengers can deliver and receive updates at the nearest branches, while other messengers will travel between each pair of branch libraries to transmit copies of all updates. As a result, a "tree-like map" was built: a structure connecting each branch with each other and each inhabitant with a branch. Updates are delivered only along the routes shown on the map, but since each citizen or branch is associated with another citizen or library, in the end, all changes made by any resident will be available to everyone on Fotas. Everyone will ultimately have the same journal in their hands, and the codes of laws will eventually be agreed upon !
This approach has many advantages. For example, when you have to move along a dangerous and toll road, which is the only path from the center of the island to its eastern mountains, only one messenger needs to go this way. It will deliver updates from West to East and vice versa, and a branch branch at the opposite ends of the road will distribute information to the rest of the island.
(At this stage, it can be noted that there is no longer any significant difference between the individual residents and branches of the library. Everyone has a copy and as long as they continue to send messengers along the appropriate routes, everyone can change the law simply by writing it in his own journal and disseminating information through the system)
This method is very effective, but has three noticeable disadvantages.
At first,no one can know with certainty about the current state of the law. Unlike the hermit on Pseudo-Moxos, who wrote in his own journal, the resident of Fotas no longer has the guarantee that after making changes, anyone reading this law in the future will see this change. Only someone who reads this in the distant future will see this change. (This is called a lack of consistency without a “read-after-write check”)
Second, it is not possible to perform read-modify-write. If two photographic residents try to change the same law, the consequences will be unpredictable. In order to get around this problem, the photo fellow must find some way to ensure that he is the only person trying to change this law and that he has read the latest version of the law before making the changes.
Thirdly, this method is vulnerable to network failures: imagine that the road leading to the remote home of one of the residents is cut off by the collapse of a rock. No updates can be received by him from the outside world, and no one can assume that they have all updates of any time, later than his last message. Also, no one can assume that since then he has not transmitted anything. The rest suggest that the resident does not know about the rock and continues to write in his own journal, waiting for a messenger who will never come. Thus, the whole system stops, no one pushes the “low-water mark” forward, no one can create a new code of laws, because the only way is lost!
In computer practice, such problems are real and serious. Whenever one node (a computer or, possibly, a data center) shuts down, engineers need to immediately assess the situation and determine whether the node can be restored and reconnected. If this is not the case, other servers will not be able to form a set, and their logs will continue to grow, which will cause problems for readers. In this case, an isolated writer will become more and more unsynchronized. If the problem cannot be fixed quickly, isolated nodes are often completely disconnected; other methods are used to route people who want to connect to them - often much slower external networks. However, the remaining nodes continue to wait. If it becomes clear that the problem will not be solved quickly, then there is only one possibility: completely remove the missing nodes from the network, telling the other nodes to pretend that those nodes no longer exist and there will be no updates from them. Nodes develop, but any records that an isolated node performs will be lost forever, unless they are copied and transferred to the main network in other ways.
So, what we saw above is a reasonable solution for violently independent islanders like Fotans who want to be able to write quickly and are not quite interested in being able to read the latest version of something. But what happens in situations where this is simply unacceptable? Laws are actually a good example - if you committed a crime at 10:00, it matters a lot whether the law against it was passed at 9:00 or 11:00. Important knowledge of the law in the present tense.
Problems became much more when Fotas began to develop a legal business. You see, Fotas is surrounded by many much smaller islands, each of which has its own industry and, therefore, needs its own code of laws. Being small islands, they do not have the resources to maintain a scribe and messenger system like in Fotas. They could never train their scribes and messengers to work as fast and efficiently. Therefore, these small islands continued to use the simplest solution for many years: each island had its own hermit with a magazine in the pseudo-Emoxosian style, and everyone who wanted to read or amend the law simply lined up for communication with the hermit. The method is slow and ineffective, especially if the hermit became ill or was washed away by a tidal wave. But without resources like on Fotas,
Fotaschan, sensing the opportunity, offered their codes of law as a service to their neighbors (LaaS). The client islands could read and write their decrees as part of the Fotas code of laws; each island received its own chapter in which no one else could write.
At first, the neighbors were delighted: they no longer had to line up to talk with the hermit. The process has become much faster, even taking into account the time to travel to Fotas. (In fact, the Fotassane worked to reduce travel time by creating embassies on different islands that became part of the network). It was also much more reliable. When the tsunami destroyed several islands and severely damaged Fotas, each photo resident had copies of the entire code of laws and the system was easily restored. Because Fotas was close to so many islands, the islands began to use the Fotas system as a reliable way to forward messages.
But the two problems we talked about earlier became more apparent. For example, on Parafoitas Island (one of the client islands), the Andros wine company used the Fotas vault to track their orders. Once Andros received an order for 100 amphora of wine for the wedding of a local politician and made an entry in the order book. The next day, one of his remote employees checked the order book, but the messenger could not deliver the record by this time, being blocked in another port due to a storm. The employee did not know about the order, and the wine was not ready before the wedding day!
Things were no better on Siranos Island. In an attempt to solve the problem of read-modify-write, only one person could change the law at a time, they appointed Bavkida responsible for the laws with even numbers on Monday, and Galen for the rest. On Tuesday - vice versa, and so on. However, Galen was very impatient and changed the even laws exactly at midnight on Tuesday, as soon as the opportunity appeared. Unfortunately, Bavkida changed the same law at 11:58 last night and her changes had not yet been delivered to Galen. Galen enacted the law and inadvertently rewritten the work of Bavkida.
Some of the neighboring islands were quite satisfied. For example, Epifoitas used Fotas's repository to archive local poetry. As soon as the poem was archived, it never changed, but new verses were re-read and added. For them, the Fotas system was both reliable and inexpensive. But overall there were enough islands for which the flaws of the Fotas system became clear.
So now we have arrived on the island of Paxos. This is the real name of the island in the Aegean with a parliamentary system invented by Leslie Lamport. He led me to all these metaphors, and the method he described is universally known as the “Paxos algorithm.” (All other island names in this article were the author’s own invention) The
good news about this algorithm is that it is no more complicated than what we discussed earlier, and Lamport's article describes the problem in the same style. Here is the article in The Part-Time Parliament . The bad news is that I could not come up with any explanation shorter than Lamport's explanation. That would make this long story insanely long. Good thing I can give you a brief description of the idea!
The residents of Paxos were interested in tracking changes in their laws and wanted every citizen to be able to know the current law of the country. They also wanted to have consistency in reading-modifying-writing, because otherwise conflicting laws could have been adopted. This type of consistency is often called strict consistency, while systems with weaker consistency, as in Fotas, are called consistency in the long run.
Paxos had its own problems: their laws were passed only by their parliament, which met in the same building, and therefore they did not have to worry about parliamentarians suddenly becoming inaccessible due to a landslide or a tidal wave. However, it was a parliament of free access: lawmakers were inclined to come and go at their discretion, sometimes inaccessible for a long time, but not because of a natural disaster, but because of a good amphora of wine. The poor acoustics in the hall made oratory impossible, and the legislators communicated with each other through messengers, as did the Fascists. Therefore, despite superficial disagreements, the parliament of free visits on Paxos created the same logistical difficulties as the more dispersed parliament of Fotas.
The basic idea of Paxos is simple: in order to amend the laws, you need to assemble the majority of parliamentarians who must do the same. If someone tries to make conflicting changes at this moment, trying to collect his own majority, he will be guaranteed at least one person who knows about the changes you have proposed, and he will help stop this by saying: “Wait! We are already voting for something else! ”Similarly, when you want to read the laws, you will ask most parliamentarians about the latest version of the law. Again, if any changes were made, at least one of them should have been involved. Tracking what kind of voting is currently taking place is based on data from each member of parliament, who has her own journal and notebook,
The Lamport method provides several important guarantees: it allows you to read the law immediately after writing, because after reaching a state of consensus regarding the law, it is guaranteed that with every future attempt to read the law, anyone will see this consensus; It makes it possible to read-modify-write, because after the process of making changes to the law begins, if successful, no other records will be made during this period. It also satisfies the “condition of progress”, since “if the majority of the parliamentarians were in the Chamber and no one entered and did not exit for a sufficiently long period of time, then the change proposed by the legislator in the House would be accepted, and the adopted change would appear in the book of every legislator in the House. ”
However, this is achieved at a certain price. The adoption of the law, that is, the entry in the system, requires the formation of consensus among most members. If some of the participants are far from the initiator of the change, then this is potentially a very slow process. You can no longer make changes to the law by simply writing them in your own journal. Reading the law also becomes slow, as this process now involves questioning the quorum of parliament.
Therefore, in practice, Paxos offers two methods of reading: “Read-latest”, which polls the quorum, and “read-recent,” which simply checks your own logbook. There is no guarantee of consistency in Paxos in the read-recent method, but it is fast. In practice, many systems require guarantees of strict consistency only at certain points in time. (For example, Agnia and Bazil may wish to receive the latest information about the law when they are arguing about the sale of sheep, but on a normal day, when one of them goes to the market, he will be content with reading his own magazine).
This means that the Paxos method always has non-zero costs due to its low speed, which quickly grows as the number of people involved increases.
One of the interesting properties of these systems is that they can be combined. For example, in both Fotas and Paxos systems, each legislator had their own copies of change logs and a notebook. The only differences are with what guarantees of strict consistency you can make entries in them.
Imagine a network of islands, each of which is small, but very distant from the others, like islands in the Pacific Ocean. (Or in computer terms, imagine a network of data centers, each located inside a building, but they are scattered around the world). Ensuring strict consistency between repositories using Paxos at such distances would be terribly impractical since a quorum would be required for each read or write. This will require several trips between the islands. However, each island can maintain its own agreed repository, and then a separate inter-island organization can process its own laws by any means, simply replacing individual notebooks with separate island repositories. Customer limited to one island
This opportunity led to the revision of their own system on Siranos. Remember that this island tried to achieve strict coherence by dividing the law so that Bavkid could write laws with an even number on Monday and Galen on Tuesday. Although this simple system caused problems, it revealed an important truth. If someone is interested in goat sale laws on Monday, he will probably still be interested in this on Tuesday, as changes in interest are relatively rare. We also learned that many strictly consistent methods are very slow, but this is the norm if you have to use them in rare cases.
This led the people of Siranos to ask themselves if they could elect a dictator on any issue that would be responsible for all laws related to this issue. While everyone can easily find a dictator on a particular topic, and the dictator himself is not overloaded with requests, this provides a simpler form of strict consistency. Anyone who would like to change or read the current laws on this issue will communicate with the dictator. If someone just wants to get an idea of the law, he can read his own copy of the code of laws, copied as in the Fotas system.
The basic principle is simple. Let's say Bavkida wants to know the law on the sale of sheep. Bavkida asks in the central register of dictators: “Who is the sheep dictator today?” Having learned that Philemon is a thematic dictator, Bavkida understands where to go. If the registry says that no dictator has been appointed, then she simply proposes a law for this registry: "Bavkida will be a sheep dictator." If this law is adopted, Bavkida will be a dictator and can act completely independently on this issue. If the law has not passed approval, then another law was under approval, so she repeats her request.
As you might have guessed, the central registry of dictators is nothing more than another strictly agreed repository. For very small groups, a single hermit may be a workflow, but for reasons of scale and reliability, it is usually best to use the Paxos method to create a central registry of dictators. At the same time, inter-island Paxos can be very slow, but you need to access it only in rare cases when you want to recognize the dictator (or become one).
This method has some great advantages. If only one person is interested in a specific issue (it happens if the question is narrow enough), then this person can become a dictator and have no business with neighbors at all. If many people are interested in a specific topic, then these people will have to stand in line to talk with one dictator, but he can immediately give them an answer, without waiting for the information to be transferred from somewhere else.
However, there are several problems. The first is the death of a dictator. Bavkida has been a dictator on the sheep issue for many years, but once she had a heart attack. No one knew about this, and so everyone who worked on the sheep ended up in line at her door. Waiting for it to appear, the entire industry stopped for several days. Finally, the door broke. Upon discovering her death, the inhabitants of Siranos passed a law abolishing her dictatorship. After that, they formalized the decision, setting the term of office. Instead of “Bavkida will be a sheep dictator” became “Bavkida will be a sheep dictator until Thursday noon.” If she is still alive and interested in sheep, then on Thursday morning she can propose a new law for voting that will extend her reign.
The second problem is the overload of dictators. It is one thing to be a dictator of sheep on a small Aegean island, it is quite another to be him in New Zealand, where the sheep outnumber people in the proportion of 7: 1. The lines in front of the dictator’s door would be huge!
Fortunately, this system does not require that there be only one dictator. The dictator must provide a strictly consistent presentation on his subject, as well as transmit updates to all other magazines using a reliable method. Therefore, in New Zealand they did not elect one dictator for the sheep. A group of interested farmers formed the New Zealand Sheep Dictator Society. As a relatively small group of relatively reliable people, they can maintain a common code of laws using Paxos (or any other system) with reasonable ease and speed. If they realize that they are becoming overwhelmed, they call new members to the organization to serve the needs of all customers.
They can constantly improve their methods. When the Society is small, they can use one magazine. They can share work topics among themselves, and if someone is temporarily unavailable, consider his question on a one-time basis using Paxos. Ultimately, as the Society grows, they can introduce a structure to determine, say, a junior dictator for shearing sheep in Otago. The nice thing about this is that their customers do not need to understand and know how they store information inside the company. As long as the Company provides a guarantee that anyone coming to them will receive a strictly agreed idea of the sheep’s law, the methods of the Company may be changed at their request.
The classic version of this ruler election protocol is called Chubby, and you can learn more about it atlink .
Author’s illustration, Yonatan Zunger, Distinguished Engineer on Privacy at Google
If you read up to this point, you have just learned some of the most complex topics in distributed computing. Almost every problem in computing based on data centers comes down to these problems: how is it that many computers that are remote from each other, connected through unreliable channels, prone to unpredictable changes, nevertheless consistently store information?
In practice, there are four methods that are commonly used:
* Unified data storages (Hermit of Pseudo-Moxos), in which one computer stores its own copy, everyone should use it in turn. The system is vulnerable to a single catastrophe, strictly coordinated, terribly simple, and all other systems are built on its basis.
* Coordinated ultimately replication (Fotas system), in which each participant has their own (strictly coordinated) storage, everyone reads their own copy, exchanging updates between all nodes and then considering them. Such a system has the advantages of speed and simplicity, as well as reliability in many types of disasters, but does not have guarantees of strict consistency in which all future readers will learn about the change as soon as you write it down. This system is very useful in cases where such a guarantee is not required, for example, the distribution of copies of images (or other voluminous data) that will never change after they are recorded and do not require constant updating.
* Quorum solution (Paxos system, unlike other examples, it is actually called “Paxos”). Reading and writing involves receiving confirmations from most participants. This ensures strict consistency and reliability, but turns out to be a very slow method, especially when distributing the system over a large area.
* Election of a dictator (Ciranos system) - an expensive, strictly agreed repository is used to determine the dictator who is responsible for some time for any question. The responsible party then uses its own, smaller, strictly agreed repository to use and amend the law on this matter.
The best thing about these systems is that, from the client’s point of view, they differ not in the methods, but in the guarantees they provide. Now I will leave you. We wandered through a chain of funny stories about fictional islands, but what you learned is not a children's version of computer science. This is the reality that IT professionals face every day. Therefore, I hope that even if you yourself are not an IT specialist and do not plan to become one, you now have a better understanding of how computer computing is organized in our time.
If you have a piece of data that many people want to read and immediately edit, for example, a common text file, bank account or the world in a multiplayer game, how to reach a general agreement with what is in the document and make sure that no one overwrites someone else’s work? This is a consensus problem in distributed systems , and in order to deal with this, I will have to talk about the sheep, dictators and fictional islands of ancient Greece.
“What other islands?” You ask?
It turns out that the original scientific article on one of the most important methods used to solve this problem was written in the form of a lengthy discussion of how the fictitious parliament of the ancient Greek island of Paxos (Paxos) in part managed to pass laws, despite the fact that no one of the parliamentarians it was impossible to reliably say when he would appear in parliament. This is a great metaphor for how a group of people can agree on what to write to a file, provided that part of the group may not be available for some indefinite time. The original article is one of the funniest serious science articles ever published and one of the best explanations for the complex algorithm I have ever seen.
The reason this metaphor works so well is that in both cases with files and laws we have some data that many people want to change, many people want to read, but no one wants to spend all on this process your time. Simultaneous reading of a book with a set of laws is limited by the number of people who can see the book at a time, just as reading a file can be limited by the speed at which data can be received from disk. Simultaneous recording requires everyone to agree not to overwrite each other's decision, but without lengthy debate to make it. Besides the fact that each person in the world will take turns using a book, how can we solve this problem?
Instead of talking about file systems and database operations, let's move on to the islands of the fake Aegean where coincidences with reality are random and residents are obsessed with issuing decrees and laws. We just need to make sure everyone can read the law when they need it. There is a way through several winding stories, and by the time we finish, you will be aware of the problem of distributed consensus, in the form in which IT professionals face it. Except for the sheep.
By the way, there will be many islands, and their names are completely invented, except for the one that was the cause of this story, but more on that later.
Hermit crabs and mexican food
We begin our story with the simplest case on the island of Pseudemoxos. Here lives one hermit who writes laws and decrees for his own use. At first he used a very simple and understandable method: a notebook and a pencil. He could add laws, change laws and reorganize laws as he wanted, just erasing and writing down new ones wherever he wanted (in fact, this is how the disks on our computers worked until the end of the 90s).
This method seemed to work quite well, except for paper that was too frayed when erased. However, the hermit realized the terrible flaw of such a decision, when one day a box of dubious burritos was thrown ashore. Making changes to the law - erasing the text and starting to write something, the hermit experienced what we politely call "an emergency at work." When the somewhat shabby hermit returned to his code, he discovered that he not only forgot what he was going to write, but now the empty space in the middle of the book is not filled with either old or new law, and the scribbles written in haste cannot be read!
A metaphor describes what happens to a computer or program when it crashes - the data on the disk can be hopelessly distorted. The more serious failures of the hermit can be compared with events such as damage to the block of magnetic heads, which can damage not only written words, but also leave a rather unpleasant and constant mark on the entire page.
These issues are resolved using logging. The scheme is to not erase anything, just like people keep accounting books or a laboratory observation diary. Now our hermit is holding a stack of papers, and when he wants to make changes to the laws, he adds a new entry to his journal:
June 4, 10:32 - Add to food safety laws: it is forbidden to consume burritos that have been at sea for an indefinite period of time.
Each edit, whether it is an insert, change or delete, is written at the end of the log with a pen. The hermit is protected from an emergency because he never erases records. In the worst case, there is an incomplete, corrupted log entry or traces of an unsuccessful write attempt that can simply be ignored. The journal has the added benefit of recording all changes. To see how the law looked a year ago, our hermit can simply read the magazine and stop at that date.
One obvious drawback of the magazine is that it is harder to read than a notebook. To find out about the current version of the food safety law, you need to start from the very beginning of the magazine and read to the end, tracking all the changes. As the volume of the magazine increases over time, the process becomes more and more burdensome.
To simplify things, our hermit keeps a stack of empty directories. Whenever a magazine becomes too voluminous, it takes time to make a set of laws: it reads the magazine from beginning to end, formulating the whole law in an up-to-date state, and then writes this state into a collection of laws. On the cover of the code of laws, he writes: "This is the state of the law on [such and such a date]." Further use of the law requires only that he read the code of laws and the journal of changes made after the date of collection of the law. Logs older than this date can be saved if sometimes a change history is required before the set, or simply thrown away.
If our hermit is too busy developing new legislation and cannot regularly make a set of laws, you can call a clerk (that is, a second computer program running in parallel with the first) to help him. The scribe will read the magazine until some agreed time, write a code of laws and inform the hermit that he has finished so that he can start using the new collection. There is no need to tell the scribe anything in order to carry out his work, so the hermit can continue his work in silence.
This method has even more advantages. Our hermit has become widely known for his wisdom (for example, his lessons on refusing Mexican cuisines delivered by sea), many people may want to read his laws. As long as these readers are satisfied with the code of laws from a specific date, they can make their own copies and read them freely without the need to disturb the sage. Only a person who needs the latest version of laws should contact him directly.
(The use of magazines in personal computers began in the late 1990s and became widespread in the mid-2000s. Your computer probably uses journaling now.)
Chaos on the island of Fotas
Near the island of Psevdomoxos is the larger island of Fotas. This island is not very populated, but there are enough people for all residents to agree that they need a consolidated system of laws to manage their lives. Nevertheless, the residents of Fotassica are known for their irreconcilable independence: they do not allow any other resident or group to rule them, and therefore decided that any resident of Fotas would have the power to pass the law. To do this, simply write the law on a piece of paper with the date, time and your name and send a messenger with him to the Fotas Library, where the clerk will add it to law journals.
(This means that many people try to save changes to a single file at the same time, without first making consensus on what will be in the file.)
To see some cases when something may go wrong, we start the story with Agniya, who lives on one of the coasts of the island and is very concerned about the purity of ritual sacrifices. She introduces the law:
June 1, noon - Law 32.1.2 on the sale of sheep is amended as follows: Under pain of death, it is forbidden to sell or acquire sheep whose coat is not completely white. Signed, Agnia.
On the other side of the island, Bazil, who has several black sheep with whom he has difficulty selling, writes his law:
June 1, noon - Law 32.1.2 on the sale of sheep changes as follows: No one can refuse to buy or sell sheep due to the color of the coat. Signed, Basil.
A little later, the clerk discovers two new laws with the same time stamp. What should he do? When Bazil comes to the city to sell the black sheep to Galatea, and she refuses to buy non-white sheep, they will go to read the code of laws. Which version of the law should they use? And what will happen when the clerk tries to collect the following code of laws? (If two people tried to simultaneously write different data to the same part of the same file, the result can be absolutely any.)
To illustrate a more delicate problem, imagine that Agnia wants to perform the read-modify-write operations of the law - she looks at the current law, decides to make changes, and then writes it down. But while she does this, Basil introduces a contradiction into the law. For example, at 10:00 Agnia reads the law
Section 32.1.3. Any person selling a goat must pay a tax equal to one coin to the general fund of the library.
She ponders and writes the following message at 10:02:
June 1, 10:02 - In Law 32.1.3 you need to change “equal to one coin” to “equal to two coins”. Signed, Agnia.
Unfortunately, at 10:01, Bazil, who hates goat taxes, writes:
June 1, 10:01 - Law 32.1.3 is replaced by "Mid-February - National Olive Day." So there you go. Signed, Basil.
Our scribe, trying to reconcile the laws and put them in order, will be very confused: when he gets to the message from Agniya, the law 32.1.3 already sets the National Olive Day and nowhere is mentioned “equal to one coin”. What should he do? Imagine that Basil replaces “pay to the general fund of the library” with “pay Basil!”.
Similar situations happen when several authors compete when editing the same code of laws. There are many solutions, each of which has its pros and cons. These solutions can be divided into two main types of models. One type is “ultimately consistent” or “eventual consistency,” where several rules governing recording allow everyone to record simultaneously without talking to each other. This model ensures that in the absence of new updates for some time all copies of the data (replicas) will become consistent. The costs of this approach are that no one can know the exact state of the law at the moment, everyone can only know what it was recently. Another model is “strict consistency,” in which all kinds of recording are possible,
Both types of models are useful. Sometimes you have information for which the norm is to be a little outdated. For example, when the residents of Fotas make their annual photo album. They exchange photos with each other and there is no need to have the latest photos, so a simpler “consistency in the end” would be good. On the other hand, “strict coherence” will be more useful for these laws, despite its costs. (This is also true for computers. For example, the images that you upload to Google are stored in the system with “consistency in the long run”, while the access control lists that determine the viewing rights are stored using strict agreement)
Back to Fotas Island .
In the end, everything makes sense
We could easily solve the first of our problems - conflicting laws with the same time stamp, simply adding a rule for tie-break so that no marks could be the same. For example, we could add the author’s name to the label in alphabetical order, so that in the case of a race, changes from Agnia will always be made before Basil. (Or, if the names match, we can assign a unique number to each resident). After the timestamps no longer match, there is no confusion. Galatea comes into the city, and the law of Basil is the only one.
If such mutual rewriting is a problem, it can be avoided by first agreeing on who can write something. For example, in one week Agnia can only edit even laws, while Bazil is odd, and vice versa next week. (In computers, the file space is often divided so that two authors never try to write the same file at all, and even more so at the same time. For example, each newly uploaded photo can be automatically assigned a unique name.)
To solve the second problem, we destroy the possibility of its existence: we change the rules of journalization in order to prohibit amendments, allowing only a complete replacement, addition or removal. This means that no wording in the journal can depend on the current state of the law for its interpretation. Agnia would have to write her law in the form
of June 1, 10:02 - Law 32.1.3 is replaced by "Any person selling a goat must pay a tax equal to two coins to the Senate." Agnia.
Since her record had a later timestamp, her version of the law easily defeats the version of Basil.
Such a system of writing laws has the advantages of speed and simplicity: everyone can write a law at any time, without consulting with anyone else. However, using laws is becoming an amazingly difficult task. If you want to know the current tax rate for the sale of goats, you go to the library and ask to read Law 32.1.3. Arriving at 10:05, you will read the code of laws and the journal of changes. The law says: “Any person selling a goat must pay a tax equal to one coin to the Senate.”
You see, Agnia changed the law at 10:02, but her messenger has not arrived yet! To make the situation a little easier, messengers can register in the library: whenever a messenger arrives from each resident, after delivering a message, they write a note on the board indicating that all messages from the photo messenger were delivered at such and such a time. Then the visitor can look at the board and see that the last message from Agnia was at 9 in the morning, and from Vasily at 7 in the evening. Now you at least know that the laws that you are reading are accurate from 7 o'clock the previous evening - the earliest time shown on the board, and all changes written before this time should have arrived. (This time is called the "low-water mark")
Of course, if a particular citizen is not very conflicting, updates from him may be rare, and everyone will ask a question: “Has the change just not yet reached the library or are there simply no?” To avoid this problem, every photo resident should send a messenger to the library regularly and regardless of whether they have any updates or not, so that the board remains relevant.
The inhabitants of Fotas are creative people, so they quickly realized that this constant stream of messengers could simplify their lives otherwise. Instead of making tedious trips to the library, they can simply keep their own copy of the code of laws and the change journal. Now their messenger every time comes back with all the latest changes in the journal, as well as with a copy of the dates that were on the board. They update their copies and may refer to them.
However, as the population of Fotas increased, the movement of messengers running to the library became a problem. For scribes copying magazines and vaults, the task of simply passing the law on changing the goat tax began to be solved terribly slowly. Fortunately, the photo community realized that they had already solved their problem:having their own copies of the law, they no longer need one central library!
Instead, several branch libraries were opened. Messengers can deliver and receive updates at the nearest branches, while other messengers will travel between each pair of branch libraries to transmit copies of all updates. As a result, a "tree-like map" was built: a structure connecting each branch with each other and each inhabitant with a branch. Updates are delivered only along the routes shown on the map, but since each citizen or branch is associated with another citizen or library, in the end, all changes made by any resident will be available to everyone on Fotas. Everyone will ultimately have the same journal in their hands, and the codes of laws will eventually be agreed upon !
This approach has many advantages. For example, when you have to move along a dangerous and toll road, which is the only path from the center of the island to its eastern mountains, only one messenger needs to go this way. It will deliver updates from West to East and vice versa, and a branch branch at the opposite ends of the road will distribute information to the rest of the island.
(At this stage, it can be noted that there is no longer any significant difference between the individual residents and branches of the library. Everyone has a copy and as long as they continue to send messengers along the appropriate routes, everyone can change the law simply by writing it in his own journal and disseminating information through the system)
This method is very effective, but has three noticeable disadvantages.
At first,no one can know with certainty about the current state of the law. Unlike the hermit on Pseudo-Moxos, who wrote in his own journal, the resident of Fotas no longer has the guarantee that after making changes, anyone reading this law in the future will see this change. Only someone who reads this in the distant future will see this change. (This is called a lack of consistency without a “read-after-write check”)
Second, it is not possible to perform read-modify-write. If two photographic residents try to change the same law, the consequences will be unpredictable. In order to get around this problem, the photo fellow must find some way to ensure that he is the only person trying to change this law and that he has read the latest version of the law before making the changes.
Thirdly, this method is vulnerable to network failures: imagine that the road leading to the remote home of one of the residents is cut off by the collapse of a rock. No updates can be received by him from the outside world, and no one can assume that they have all updates of any time, later than his last message. Also, no one can assume that since then he has not transmitted anything. The rest suggest that the resident does not know about the rock and continues to write in his own journal, waiting for a messenger who will never come. Thus, the whole system stops, no one pushes the “low-water mark” forward, no one can create a new code of laws, because the only way is lost!
In computer practice, such problems are real and serious. Whenever one node (a computer or, possibly, a data center) shuts down, engineers need to immediately assess the situation and determine whether the node can be restored and reconnected. If this is not the case, other servers will not be able to form a set, and their logs will continue to grow, which will cause problems for readers. In this case, an isolated writer will become more and more unsynchronized. If the problem cannot be fixed quickly, isolated nodes are often completely disconnected; other methods are used to route people who want to connect to them - often much slower external networks. However, the remaining nodes continue to wait. If it becomes clear that the problem will not be solved quickly, then there is only one possibility: completely remove the missing nodes from the network, telling the other nodes to pretend that those nodes no longer exist and there will be no updates from them. Nodes develop, but any records that an isolated node performs will be lost forever, unless they are copied and transferred to the main network in other ways.
Fotas customers and strict consistency
So, what we saw above is a reasonable solution for violently independent islanders like Fotans who want to be able to write quickly and are not quite interested in being able to read the latest version of something. But what happens in situations where this is simply unacceptable? Laws are actually a good example - if you committed a crime at 10:00, it matters a lot whether the law against it was passed at 9:00 or 11:00. Important knowledge of the law in the present tense.
Problems became much more when Fotas began to develop a legal business. You see, Fotas is surrounded by many much smaller islands, each of which has its own industry and, therefore, needs its own code of laws. Being small islands, they do not have the resources to maintain a scribe and messenger system like in Fotas. They could never train their scribes and messengers to work as fast and efficiently. Therefore, these small islands continued to use the simplest solution for many years: each island had its own hermit with a magazine in the pseudo-Emoxosian style, and everyone who wanted to read or amend the law simply lined up for communication with the hermit. The method is slow and ineffective, especially if the hermit became ill or was washed away by a tidal wave. But without resources like on Fotas,
Fotaschan, sensing the opportunity, offered their codes of law as a service to their neighbors (LaaS). The client islands could read and write their decrees as part of the Fotas code of laws; each island received its own chapter in which no one else could write.
At first, the neighbors were delighted: they no longer had to line up to talk with the hermit. The process has become much faster, even taking into account the time to travel to Fotas. (In fact, the Fotassane worked to reduce travel time by creating embassies on different islands that became part of the network). It was also much more reliable. When the tsunami destroyed several islands and severely damaged Fotas, each photo resident had copies of the entire code of laws and the system was easily restored. Because Fotas was close to so many islands, the islands began to use the Fotas system as a reliable way to forward messages.
But the two problems we talked about earlier became more apparent. For example, on Parafoitas Island (one of the client islands), the Andros wine company used the Fotas vault to track their orders. Once Andros received an order for 100 amphora of wine for the wedding of a local politician and made an entry in the order book. The next day, one of his remote employees checked the order book, but the messenger could not deliver the record by this time, being blocked in another port due to a storm. The employee did not know about the order, and the wine was not ready before the wedding day!
Things were no better on Siranos Island. In an attempt to solve the problem of read-modify-write, only one person could change the law at a time, they appointed Bavkida responsible for the laws with even numbers on Monday, and Galen for the rest. On Tuesday - vice versa, and so on. However, Galen was very impatient and changed the even laws exactly at midnight on Tuesday, as soon as the opportunity appeared. Unfortunately, Bavkida changed the same law at 11:58 last night and her changes had not yet been delivered to Galen. Galen enacted the law and inadvertently rewritten the work of Bavkida.
Some of the neighboring islands were quite satisfied. For example, Epifoitas used Fotas's repository to archive local poetry. As soon as the poem was archived, it never changed, but new verses were re-read and added. For them, the Fotas system was both reliable and inexpensive. But overall there were enough islands for which the flaws of the Fotas system became clear.
Paxos Parliament
So now we have arrived on the island of Paxos. This is the real name of the island in the Aegean with a parliamentary system invented by Leslie Lamport. He led me to all these metaphors, and the method he described is universally known as the “Paxos algorithm.” (All other island names in this article were the author’s own invention) The
good news about this algorithm is that it is no more complicated than what we discussed earlier, and Lamport's article describes the problem in the same style. Here is the article in The Part-Time Parliament . The bad news is that I could not come up with any explanation shorter than Lamport's explanation. That would make this long story insanely long. Good thing I can give you a brief description of the idea!
The residents of Paxos were interested in tracking changes in their laws and wanted every citizen to be able to know the current law of the country. They also wanted to have consistency in reading-modifying-writing, because otherwise conflicting laws could have been adopted. This type of consistency is often called strict consistency, while systems with weaker consistency, as in Fotas, are called consistency in the long run.
Paxos had its own problems: their laws were passed only by their parliament, which met in the same building, and therefore they did not have to worry about parliamentarians suddenly becoming inaccessible due to a landslide or a tidal wave. However, it was a parliament of free access: lawmakers were inclined to come and go at their discretion, sometimes inaccessible for a long time, but not because of a natural disaster, but because of a good amphora of wine. The poor acoustics in the hall made oratory impossible, and the legislators communicated with each other through messengers, as did the Fascists. Therefore, despite superficial disagreements, the parliament of free visits on Paxos created the same logistical difficulties as the more dispersed parliament of Fotas.
The basic idea of Paxos is simple: in order to amend the laws, you need to assemble the majority of parliamentarians who must do the same. If someone tries to make conflicting changes at this moment, trying to collect his own majority, he will be guaranteed at least one person who knows about the changes you have proposed, and he will help stop this by saying: “Wait! We are already voting for something else! ”Similarly, when you want to read the laws, you will ask most parliamentarians about the latest version of the law. Again, if any changes were made, at least one of them should have been involved. Tracking what kind of voting is currently taking place is based on data from each member of parliament, who has her own journal and notebook,
The Lamport method provides several important guarantees: it allows you to read the law immediately after writing, because after reaching a state of consensus regarding the law, it is guaranteed that with every future attempt to read the law, anyone will see this consensus; It makes it possible to read-modify-write, because after the process of making changes to the law begins, if successful, no other records will be made during this period. It also satisfies the “condition of progress”, since “if the majority of the parliamentarians were in the Chamber and no one entered and did not exit for a sufficiently long period of time, then the change proposed by the legislator in the House would be accepted, and the adopted change would appear in the book of every legislator in the House. ”
However, this is achieved at a certain price. The adoption of the law, that is, the entry in the system, requires the formation of consensus among most members. If some of the participants are far from the initiator of the change, then this is potentially a very slow process. You can no longer make changes to the law by simply writing them in your own journal. Reading the law also becomes slow, as this process now involves questioning the quorum of parliament.
Therefore, in practice, Paxos offers two methods of reading: “Read-latest”, which polls the quorum, and “read-recent,” which simply checks your own logbook. There is no guarantee of consistency in Paxos in the read-recent method, but it is fast. In practice, many systems require guarantees of strict consistency only at certain points in time. (For example, Agnia and Bazil may wish to receive the latest information about the law when they are arguing about the sale of sheep, but on a normal day, when one of them goes to the market, he will be content with reading his own magazine).
This means that the Paxos method always has non-zero costs due to its low speed, which quickly grows as the number of people involved increases.
Combined Systems and Dictatorial Elections: Back to Siranos
One of the interesting properties of these systems is that they can be combined. For example, in both Fotas and Paxos systems, each legislator had their own copies of change logs and a notebook. The only differences are with what guarantees of strict consistency you can make entries in them.
Imagine a network of islands, each of which is small, but very distant from the others, like islands in the Pacific Ocean. (Or in computer terms, imagine a network of data centers, each located inside a building, but they are scattered around the world). Ensuring strict consistency between repositories using Paxos at such distances would be terribly impractical since a quorum would be required for each read or write. This will require several trips between the islands. However, each island can maintain its own agreed repository, and then a separate inter-island organization can process its own laws by any means, simply replacing individual notebooks with separate island repositories. Customer limited to one island
This opportunity led to the revision of their own system on Siranos. Remember that this island tried to achieve strict coherence by dividing the law so that Bavkid could write laws with an even number on Monday and Galen on Tuesday. Although this simple system caused problems, it revealed an important truth. If someone is interested in goat sale laws on Monday, he will probably still be interested in this on Tuesday, as changes in interest are relatively rare. We also learned that many strictly consistent methods are very slow, but this is the norm if you have to use them in rare cases.
This led the people of Siranos to ask themselves if they could elect a dictator on any issue that would be responsible for all laws related to this issue. While everyone can easily find a dictator on a particular topic, and the dictator himself is not overloaded with requests, this provides a simpler form of strict consistency. Anyone who would like to change or read the current laws on this issue will communicate with the dictator. If someone just wants to get an idea of the law, he can read his own copy of the code of laws, copied as in the Fotas system.
The basic principle is simple. Let's say Bavkida wants to know the law on the sale of sheep. Bavkida asks in the central register of dictators: “Who is the sheep dictator today?” Having learned that Philemon is a thematic dictator, Bavkida understands where to go. If the registry says that no dictator has been appointed, then she simply proposes a law for this registry: "Bavkida will be a sheep dictator." If this law is adopted, Bavkida will be a dictator and can act completely independently on this issue. If the law has not passed approval, then another law was under approval, so she repeats her request.
As you might have guessed, the central registry of dictators is nothing more than another strictly agreed repository. For very small groups, a single hermit may be a workflow, but for reasons of scale and reliability, it is usually best to use the Paxos method to create a central registry of dictators. At the same time, inter-island Paxos can be very slow, but you need to access it only in rare cases when you want to recognize the dictator (or become one).
This method has some great advantages. If only one person is interested in a specific issue (it happens if the question is narrow enough), then this person can become a dictator and have no business with neighbors at all. If many people are interested in a specific topic, then these people will have to stand in line to talk with one dictator, but he can immediately give them an answer, without waiting for the information to be transferred from somewhere else.
However, there are several problems. The first is the death of a dictator. Bavkida has been a dictator on the sheep issue for many years, but once she had a heart attack. No one knew about this, and so everyone who worked on the sheep ended up in line at her door. Waiting for it to appear, the entire industry stopped for several days. Finally, the door broke. Upon discovering her death, the inhabitants of Siranos passed a law abolishing her dictatorship. After that, they formalized the decision, setting the term of office. Instead of “Bavkida will be a sheep dictator” became “Bavkida will be a sheep dictator until Thursday noon.” If she is still alive and interested in sheep, then on Thursday morning she can propose a new law for voting that will extend her reign.
The second problem is the overload of dictators. It is one thing to be a dictator of sheep on a small Aegean island, it is quite another to be him in New Zealand, where the sheep outnumber people in the proportion of 7: 1. The lines in front of the dictator’s door would be huge!
Fortunately, this system does not require that there be only one dictator. The dictator must provide a strictly consistent presentation on his subject, as well as transmit updates to all other magazines using a reliable method. Therefore, in New Zealand they did not elect one dictator for the sheep. A group of interested farmers formed the New Zealand Sheep Dictator Society. As a relatively small group of relatively reliable people, they can maintain a common code of laws using Paxos (or any other system) with reasonable ease and speed. If they realize that they are becoming overwhelmed, they call new members to the organization to serve the needs of all customers.
They can constantly improve their methods. When the Society is small, they can use one magazine. They can share work topics among themselves, and if someone is temporarily unavailable, consider his question on a one-time basis using Paxos. Ultimately, as the Society grows, they can introduce a structure to determine, say, a junior dictator for shearing sheep in Otago. The nice thing about this is that their customers do not need to understand and know how they store information inside the company. As long as the Company provides a guarantee that anyone coming to them will receive a strictly agreed idea of the sheep’s law, the methods of the Company may be changed at their request.
The classic version of this ruler election protocol is called Chubby, and you can learn more about it atlink .
Eventually
Author’s illustration, Yonatan Zunger, Distinguished Engineer on Privacy at Google
If you read up to this point, you have just learned some of the most complex topics in distributed computing. Almost every problem in computing based on data centers comes down to these problems: how is it that many computers that are remote from each other, connected through unreliable channels, prone to unpredictable changes, nevertheless consistently store information?
In practice, there are four methods that are commonly used:
* Unified data storages (Hermit of Pseudo-Moxos), in which one computer stores its own copy, everyone should use it in turn. The system is vulnerable to a single catastrophe, strictly coordinated, terribly simple, and all other systems are built on its basis.
* Coordinated ultimately replication (Fotas system), in which each participant has their own (strictly coordinated) storage, everyone reads their own copy, exchanging updates between all nodes and then considering them. Such a system has the advantages of speed and simplicity, as well as reliability in many types of disasters, but does not have guarantees of strict consistency in which all future readers will learn about the change as soon as you write it down. This system is very useful in cases where such a guarantee is not required, for example, the distribution of copies of images (or other voluminous data) that will never change after they are recorded and do not require constant updating.
* Quorum solution (Paxos system, unlike other examples, it is actually called “Paxos”). Reading and writing involves receiving confirmations from most participants. This ensures strict consistency and reliability, but turns out to be a very slow method, especially when distributing the system over a large area.
* Election of a dictator (Ciranos system) - an expensive, strictly agreed repository is used to determine the dictator who is responsible for some time for any question. The responsible party then uses its own, smaller, strictly agreed repository to use and amend the law on this matter.
The best thing about these systems is that, from the client’s point of view, they differ not in the methods, but in the guarantees they provide. Now I will leave you. We wandered through a chain of funny stories about fictional islands, but what you learned is not a children's version of computer science. This is the reality that IT professionals face every day. Therefore, I hope that even if you yourself are not an IT specialist and do not plan to become one, you now have a better understanding of how computer computing is organized in our time.