Turn: blog.csdn.net/cadem/artic…

Sequential consistency analysis

In 2017, MY team undertook the transformation of ZooKeeper’s remote live project. During this time I heard two different statements about consistency.

  • One theory is that ZooKeeper is the ultimate consistency, because because of multiple copies and the Zab protocol that guarantees most success, when one client process writes a new value, another client process is not guaranteed to read it immediately, but it is guaranteed to read it eventually.

  • Another argument is that ZooKeeper’s Zab protocol is similar to the Paxos protocol and provides strong consistency.

Whenever I hear these two statements, I want to correct them by saying, No, ZooKeeper is Sequential consistency.

But it’s too complicated to explain. It takes a long article. I have always wanted to write this article to explain this statement, but I have not done so. It has been a long time since the end of ele. me’s remote live project, so I finally squeezed some time to write it out and discuss it with everyone.

As you can see from the ZooKeeper documentation, it is explicitly stated that its consistency is Sequential consistency (see link at the end).

What is Sequential consistency?

Sequential Consistency was first proposed by Lamport in 1979. (See his paper How to Make a Multiprocessor Computer that correctly executes Multiprocess Programs.) Sequential consistency occurs when the following condition is met:

the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.

The English definition is obscure (Lomport is always strict but obscure, as is the Paxos protocol), and the first time I saw it I thought, “What the hell?” . How come I know every English word, but I just don’t know what he’s talking about. The first time I saw this sentence and I feel the same friend raise a hand.

I will translate this English definition into Chinese later in this article, but let’s first look at the title of this paper and a key word in its definition to illustrate the scope of sequential consistency. The title of the paper and this definition includes the word multiprocessor, which means multiple processors.

From this point of view, sequential consistency is a feature used to define multiple processors and programs that run on multiple processors. The title of Lomport’s paper translates as “How to Make a computer with multiple processors run multiprocess programs correctly”, meaning that if a multi-core processor has the properties of sequential consistency, the multi-core processor will run correctly. We will explain what this means by running correctly (the role of Sequential consistency, as discussed later in this article). From this title we can also see that Sequential consistency should be a concept in the domain of concurrent programming.

But we often talk about Sequential consistency in the realm of distributed systems, as this article focuses on the consistency of Zookeeper (which is obviously a distributed system). In fact, multiple programs running on a multicore processor, In fact, it is a Distributed System (Lomport explains this point in his book “Time, Clocks, and the Ordering of Events in a Distributed System”).

Therefore, although Sequential consistency was first proposed in concurrent programming, it can be applied to distributed systems, such as the distributed storage system discussed in this article, Zookeeper. Another important Linearizability, which was first proposed in concurrent programming, is now widely used in distributed systems.

Now let’s translate that obscure definition. Translating this definition made me feel like I was doing reading comprehension in school. I’m not going to translate it directly, because even if I translated it into Chinese, I don’t think many people would understand what it means. I still get the feeling that I know every word in Chinese, but I still don’t know what it is.

First, LET me explain some individual words. First, any execution, what does any execution mean? You have multiple programs running on a multi-core processor, so for example you have two programs,

The first program, called P1, has the following code: P1_write(x); P1_read(y); The second program, called P2, has the following code: P2_write(u); P2_read(v);Copy the code

Theoretically, how many execution possibilities are there for two programs running on two separate processor cores? I’ll give you a few examples.

1: P1 - write (x) -- -- -- -- -- -- -- -- read (y) -- -- -- -- -- -- -- -- P2 -- -- -- -- -- -- -- -- -- -- -- write (u) -- -- -- -- -- -- -- read (v) - 2 kinds: P1 -- -- -- -- -- -- -- -- -- - write (x) - read (y) -- -- -- -- -- -- -- -- P2 - write (u) -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- read (v) - 3 kinds:  P1---read(y)----------write(x)------ P2-----------write(u)---------read(v)-Copy the code

We have 24 possible sequences of execution, which are these 4 operations any combination of permutations, which is 4 factorial. = 24. Possibilities like the first and second are easy to understand. Why is there a possible implementation like the third one? That’s because even in the same program, given the levels of caching and coherence of processing, the order that actually works in memory, even if your program is write before read, can be read before write.

There is also an execution like the following, where two operations are executed simultaneously on two processors. P1 – write (x) – read (y) — — — — — — — — P2 – write (u) — — — — — — — — read (v) – if combined with a run at the same time this kind of situation, that there is more possibility. I’m not good at math, so I’m not going to do it anymore, because it doesn’t matter how many there are, what matters is that you know there are many possibilities. “Any execution” in this definition means any possible execution, but it also means all possible execution. Without translating the definition, let’s explain another word, sequential order. What does sequential order mean? Let’s take a look at the English dictionary. Sequential: continuous; One after another; There is an order. The order; Rules; Trade order

Sequential order– what the hell is this? Sequential means one after another, and in this context of a processor, sequential means that operations are executed one after another, sequentially, without overlap. Order means to make something orderly by following certain rules after certain adjustments. For example, the ordering of an algorithm is the ordering of an array. That is, the ordering of an array follows the order of the largest to the smallest or the order of the smallest to the largest. Sequential order, then, means that operations are arranged one after another in such a sequence, without overlap. Again, if we put the four operations in order, one after the other, we would get four! The number of possible orders, again, doesn’t matter how many.

Such as:

P1_write(x); P1_read(y); P2_write(u); P2_read(v); P1_read(y); P1_write(x); P2_write(u); P2:read(v); P2_write(u); P2_read(v); P1_read(y); P1:write(x);Copy the code

I’m just going to list three of them here, and you can sort out the rest. Sequential order means that four operations are executed sequentially, one after the other, without overlap. Note that this is not a true execution. A true execution is any execution. This is a logical assumption, and that’s why the definition has an as if.

With all this groundwork, let’s begin translating the first sentence of the definition:

The effect of any one possible execution is the same as the effect of a sequence of all the operations on the processor.

Notice that some here means something, not some, because order is singular. What this means is that for a processor to satisfy this condition, it must be able to allow only those possible executions that satisfy this condition to exist, and none that do not.

From the first statement, we can see that for a multi-core processor to achieve sequential consistency, multiple programs running on multiple cores are “equivalent” to executing all operations sequentially on one core. If so, the power of multicore would essentially disappear. So neither in 1979, when Lomport wrote this paper, nor today, has any realistic multicore processor achieved sequential consistency.

So why does Lomport come up with such an unrealistic concept? (I’ll note that Lomport didn’t extend this to the realm of distributed systems when he wrote this paper, which is the realm of concurrent programming for multi-core processors.) We’ll get to that later.

Another point to note here is that I use the word effect in my translation, but actually the original English definition uses the word result. What’s the difference between the effect and the result? What do we mean by execution results? Whether it’s any real execution or some sort of sequenced hypothetical execution, the program produces a result, such as the result of print. In fact, the definition says the same thing.

If the definition uses effect, then the definition is only a qualitative definition, if the definition uses result, then the definition is a quantitative definition. Quantitative, that is, something that can be proved mathematically. From this we can see that the great god is different, any theory can be mathematically proved correct. We’ll talk about proof later in the article, but we’ll keep it in suspense. Here, a more accurate translation of our first definition is:

The result of any possible execution is the same as the result of a certain sequence in which all processor operations are executed.

The other thing to note here is that the same result means that if someone really wants to implement a sequential multi-core processor, they will have some room to optimize because they want the same result, rather than a purely sequential effect. But it is estimated that this optimization is also very limited.

Well, we have finally explained the first sentence, which is the most difficult one. Everyone can breathe a sigh of relief. The second sentence is very easy. Let’s explain one word first and then translate it completely. This word is the sequence that appears in the second sentence. Sequential order, as we have just explained, is an action that produces a result, the result of which produces a queue of operations. The sequence is the sequence of the operation.

Ok, the translation of the second sentence is:

And the operations of each individual processor appear in the operation queue in the order specified by the program.

That is, if you write (x) first; After the read (y); Then only operation queues that meet this order are eligible. So a lot of the possible executions that we just talked about are going to be a lot less, and I’m not going to count them, but again, it doesn’t matter how many there are, but they’re going to be a lot less. So what does the second sentence mean? This means that if a multicore processor achieves sequential consistency, then the multicore processor is essentially done with sequential consistency. I continue to wonder why caching, the most effective processor performance optimization, is missing.

Here we can put the two sentences together and have a complete look:

The result of any possible execution is the same as the result of a sequence in which all processor operations are executed, and each individual processor operation appears in the operation queue in the order specified by the program.

From this definition, we can see that the core of this concept is sequential order, which is why Lomport calls this model of consistency sequential consistency. It can be said that this is very aptly named. I don’t know if this kind of appropriateness is more understandable to native English speakers, but there should not be a “what the hell is the order of order” situation. If sequential seems apposite to you after reading this article, then I am clear. Let’s take a concrete example to illustrate.

execution A
    P0 writex=1-------------------------------
    P1 -------write x=2----------------------
    P2 -----------------read x==1--read x==2
    P3 -----------------read x==1--read x==2

    sequetial order: P0_write x=1,P3_read x==1,P4_read x==1,P1_write x=2,P3_read x==2,P4_read x==2

    execution B
    P0 write=1-------------------------------
    P1 -------write x=2----------------------
    P2 -----------------read x==2--read x==1
    P3 -----------------read x==2--read x==1

    sequetial order: P1_write x=2,P3_read x==2,P4_read x==2,P0_write x=1,P3_read x==1,P4_read x==1

    execution C
    P0 write=1-------------------------------
    P1 -------write x=2----------------------
    P2 -----------------read x==1--read x==2
    P3 -----------------read x==2--read x==1
Copy the code

Sequetial Order: You cannot find an order that meets both conditions in the definition. So if A multicore processor only allows execution A and B and not C, then the multicore processor is sequetial consistency. If it allows C, it’s not sequetial consistency.

So far we have covered all of what is sequetial consistency. However, careful friends may ask, what if your program is a multithreaded program? So let’s explain the last detail of the definition: program. A Program is a sequence of instructions that can be run directly on the processor. This is not a strict definition of Pogram, but I would like to point out that this Program is a concept that existed in ancient times when there was no operating system. In this definition, Prgram refers to the Program of that era. This Program does not have the concept of process, thread, these concepts after the operating system has the concept.

There is no operating system and no concept of memory space. Unlike programs, different programs have their own independent memory address space. In our case, memory is shared for different programs. In addition, it is important to note that Program can be used to describe all kinds of programs, whether you are an operating system kernel or an application.

We have just said that sequential consistency, although conceived in the domain of concurrent programming, is actually a concept for the distributed domain, especially distributed storage systems. The Distributed system: Principles and Paradigms by Andrew S.Tanenbaum by Maarten Van Steen, The author tweaks Lomport’s definition a bit to make it more relevant to the concept of the distributed realm, Let’s take a look at how the author changed it:

The result of any execution is the same as if the (read and write) operations by all processes on the data store were executed in some sequential order and the operations of-each individual process appear in this sequence in the order specified by its program.

The author changed the processor to Process and added the qualification on the data store, which is not available in Lomport and actually refers to memory by default. A Process is a Process. Zookeeper is an application process that accesses ZooKeeper. Program is not so low level concept, also based on the operating system application.

Ok, now IT’s time for me to reveal the two secrets I sold above. In Lomport’s paper, a small example is given as follows:

    process 1
        a := 1;
        if b = 0 then critical section:
                a := 0
            else.fi

    process 2
        b := 1;
        if a = 0 then critical section:
                b := 0
            else.fi
Copy the code

If a multicore processing satisfies the requirements for sequential consistency, then at most one program can enter the critical section, Lomport said. In his paper, Lomport does not explain why at most one program can enter the critical section. I leave the proof to the reader of the paper, just like the problem sets that we see in our textbooks, to the reader.

Lomport probably thought the proof was too simple to put pen to paper. At less than 2 A4 pages, the paper sequential Consistency is the shortest I have ever seen. This is Lomport’s style, and his Paxos paper is full of detail, all in one brush, leaving the reader with endless imagination. Assuming that we have now proved this to be true (although I have not proved it, the paper gives two references to prove it), what does this example show? You may notice that this example doesn’t use any locks, but it implements the critical section, which is a multithreaded synchronization mechanism. If multiple processors are sequential, then your concurrent programs are “naturally correct”.

But processor designers, for best performance, leave the task of making sure the program is correct to the programmer. Only some instructions such as fence and CAS are provided at the hardware level. Based on these instructions, the synchronization mechanism is implemented to ensure the correctness of the operating system and application programs. Programmers must be careful about using threads and synchronization mechanisms, or else unexpected problems can occur.

If you don’t debug a multithreading bug for 2 days in a row, you’re a god. Linearizability is the foundation of concurrency control. Linearizability is the basis of concurrency control. Linearizability is the foundation of concurrency control. The processor as a whole only achieves a much lower level of consistency than sequential consistency. So the implementation difficulty is greatly reduced.

While Lomport’s concept of sequential consistency has no practical relevance in the world of Concurrent programming, it does point us to programmer heaven. In programmer’s heaven, there are no programs, just programs. No more multithreaded programming, no more locks when you’re in an interview.

Sequential consistency is more practical in a distributed realm. Zookeeper achieves sequential consistency. Again, this should be provable, but I’m not aware of any papers from the ZooKeeper community proving this. If you understand the definition explained above, you can understand that ZooKeeper is sequential consistency. Welcome to join us in the discussion.

ZK consistency

In fact, The consistency of ZooKeeper is more complicated. ZooKeeper reads sequential consistency. Linearizability is used to write ZooKeeper. For linearizability, see my other article linear consistency is the foundation of concurrency control.

This statement is not written in the official ZooKeeper documentation, but is discussed in detail in the community mailing group. In addition, this view is also mentioned in this paper Modular Composition of Coordination Services about ZooKeeper (this paper is not the mainstream paper of ZooKeeper, However, the characteristics of ZooKeeper and the cross-room scheme of ZooKeeper have been comprehensively analyzed, and the remote multi-activity transformation of ZooKeeper of Ele. me has also referred to some points in this paper. ZooKeeper is an integrated read operation and a write operation that implements sequential consistency.

Through simple reasoning, we can conclude that the small example in Lomport’s paper is also true in ZooKeeper. We can implement distributed locking like this. However, the distributed implementation method officially recommended by ZooKeeper does not adopt this way to achieve the implementation. Instead, the Linearizability feature of ZooKeeper is used to achieve the distributed lock. See my article “ZooKeeper implementing Distributed Locking and Master selection”).

Why does ZK want sequential consistency?

The core function of ZooKeeper is to make coordination service, that is, to make distributed lock service. In a distributed environment, how can ZooKeeper be “naturally correct”? There is no other synchronization mechanism to ensure the correctness of ZooKeeper. Therefore, as long as ZK implements SC, it can guarantee the correctness and provide external lock service.

Reference documentation

  1. Zookeeper.apache.org/doc/r3.4.9/…
  2. Blog.csdn.net/cadem/artic…
  3. Comments.gmane.org/gmane.comp….
  4. Blog.csdn.net/cadem/artic…