A brief history of Consensus, 2PC and Transaction Commit.

Thu, 12 Aug 2010 15:37:00 GMT

Notes:
*. Time, Clocks and the Ordering of Events in a Distributed System" (1978)
1. The issue is that in a distributed system you cannot tell if event A happened before event B, unless A caused B in some way. Each observer can see events happen in a different order, except for events that cause each other, ie there is only a partial ordering of events in a distributed system.
    2. Lamport defines the "happens before" relationship and operator, and goes on to give an algorithm that provides a total ordering of events in a distributed system, so that each process sees events in the same order as every other process.
    3. Lamport also introduces the concept of a distributed state machine: start a set of deterministic state machines in the same state and then make sure they process the same messages in the same order.
    4. Each machine is now a replica of the others. The key problem is making each replica agree what is the next message to process: a consensus problem.
    5. However, the system is not fault tolerant; if one process fails that others have to wait for it to recover.

*. "Notes on Database Operating Systems" (1979).
    1. 2PC problem: Unfortunately 2PC would block if the TM (Transaction Manager) fails at the wrong time.

*. "NonBlocking Commit Protocols" (1981)
    1. 3PC problem: The problem was coming up with a nice 3PC algorithm, this would only take nearly 25 years!

*. "Impossibility of distributed consensus with one faulty process" (1985)
    1. this famous result is known as the "FLP" result
    2. By this time "consensus" was the name given to the problem of getting a bunch of processors to agree a value.
    3. The kernel of the problem is that you cannot tell the difference between a process that has stopped and one that is running very slowly, making dealing with faults in an asynchronous system almost impossible.
    4. a distributed algorithm has two properties: safety and liveness. 2PC is safe: no bad data is ever written to the databases, but its liveness properties aren't great: if the TM fails at the wrong point the system will block.
    5. The asynchronous case is more general than the synchronous case: an algorithm that works for an asynchronous system will also work for a synchronous system, but not vice versa.

*. "The Byzantine Generals Problem" (1982)
    1. In this form of the consensus problem the processes can lie, and they can actively try to deceive other processes.

*. "A Comparison of the Byzantine Agreement Problem and the Transaction Commit Problem." (1987) .
    1. At the time the best consensus algorithm was the Byzantine Generals, but this was too expensive to use for transactions.

*. "Uniform consensus is harder than consensus" (2000)
    1. With uniform consensus all processes must agree on a value, even the faulty ones - a transaction should only commit if all RMs are prepared to commit.

*. "The Part-Time Parliament" (submitted in 1990, published 1998)
    1. Paxos consensus algorithm

*. "How to Build a Highly Availability System using Consensus" (1996).
1. This paper provides a good introduction to building fault tolerant systems and Paxos.

*. "Paxos Made Simple (2001)
    1. The kernel of Paxos is that given a fixed number of processes, any majority of them must have at least one process in common. For example given three processes A, B and C the possible majorities are: AB, AC, or BC. If a decision is made when one majority is present eg AB, then at any time in the future when another majority is available at least one of the processes can remember what the previous majority decided. If the majority is AB then both processes will remember, if AC is present then A will remember and if BC is present then B will remember.
    2. Paxos can tolerate lost messages, delayed messages, repeated messages, and messages delivered out of order.
    3. It will reach consensus if there is a single leader for long enough that the leader can talk to a majority of processes twice. Any process, including leaders, can fail and restart; in fact all processes can fail at the same time, the algorithm is still safe. There can be more than one leader at a time.
    4. Paxos is an asynchronous algorithm; there are no explicit timeouts. However, it only reaches consensus when the system is behaving in a synchronous way, ie messages are delivered in a bounded period of time; otherwise it is safe. There is a pathological case where Paxos will not reach consensus, in accordance to FLP, but this scenario is relatively easy to avoid in practice.

*.   "Consensus in the presence of partial synchrony" (1988)
    1. There are two versions of partial synchronous system: in one processes run at speeds within a known range and messages are delivered in bounded time but the actual values are not known a priori; in the other version the range of speeds of the processes and the upper bound for message deliver are known a priori, but they will only start holding at some unknown time in the future.
    2. The partial synchronous model is a better model for the real world than either the synchronous or asynchronous model; networks function in a predicatable way most of the time, but occasionally go crazy.

*.   "Consensus on Transaction Commit" (2005).
    1. A third phase is only required if there is a fault, in accordance to the Skeen result. Given 2n+1 TM replicas Paxos Commit will complete with up to n faulty replicas.
    2. Paxos Commit does not use Paxos to solve the transaction commit problem directly, ie it is not used to solve uniform consensus, rather it is used to make the system fault tolerant.
    3. Recently there has been some discussion of the CAP conjecture: Consistency, Availability and Partition. The conjecture asserts that you cannot have all three in a distributed system: a system that is consistent, that can have faulty processes and that can handle a network partition.
    4. Now take a Paxos system with three nodes: A, B and C. We can reach consensus if two nodes are working, ie we can have consistency and availability. Now if C becomes partitioned and C is queried, it cannot respond because it cannot communicate with the other nodes; it doesn't know whether it has been partitioned, or if the other two nodes are down, or if the network is being very slow. The other two nodes can carry on, because they can talk to each other and they form a majority. So for the CAP conjecture, Paxos does not handle a partition because C cannot respond to queries. However, we could engineer our way around this. If we are inside a data center we can use two independent networks (Paxos doesn't mind if messages are repeated). If we are on the internet, then we could have our client query all nodes A, B and C, and if C is partitioned the client can query A or B unless it is partitioned in a similar way to C.
    5. a synchronous network, if C is partitioned it can learn that it is partitioned if it does not receive messages in a fixed period of time, and thus can declare itself down to the client.

*.   "Co-Allocation, Fault Tolerance and Grid Computing" (2006).

[REF] http://betathoughts.blogspot.com/2007/06/brief-history-of-consensus-2pc-and.html

�?/a> 2010-08-12 23:37 发表评论

Lock-Free

Tue, 20 Jul 2010 08:58:00 GMT

A "wait-free" procedure can complete in a finite number of steps, regardless of the relative speeds of other threads.

A "lock-free" procedure guarantees progress of at least one of the threads executing the procedure. That means some threads can be delayed arbitrarily, but it is guaranteed that at least one thread makes progress at each step.

CAS�Q�assuming the map hasn't changed since I last looked at it, copy it. Otherwise, start all over again.

Delay Update�Q�In plain English, the loop says "I'll replace the old map with a new, updated one, and I'll be on the lookout for any other updates of the map, but I'll only do the replacement when the reference count of the existing map is one."

[REF]http://www.drdobbs.com/cpp/184401865

�?/a> 2010-07-20 16:58 发表评论

Lessons Learned from scaling Farmville

Fri, 16 Jul 2010 07:06:00 GMT

1. Interactive games are write-heavy. Typical web apps read more than they write so many common architectures may not be sufficient. Read heavy apps can often get by with a caching layer in front of a single database. Write heavy apps will need to partition so writes are spread out and/or use an in-memory architecture.

2. Design every component as a degradable service. Isolate components so increased latencies in one area won't ruin another. Throttle usage to help alleviate problems. Turn off features when necessary.

3. Cache Facebook data. When you are deeply dependent on an external component consider caching that component's data to improve latency.

4. Plan ahead for new release related usage spikes.

5. Sample. When analyzing large streams of data, looking for problems for example, not every piece of data needs to be processed. Sampling data can yield the same results for much less work.

The key ideas are to isolate troubled and highly latent services from causing latency and performance issues elsewhere through use of error and timeout throttling, and if needed, disable functionality in the application using on/off switches and functionality based throttles.

�?/a> 2010-07-16 15:06 发表评论

php copy on write

Tue, 18 May 2010 14:45:00 GMT

1.如果是非引用赋��|��用于赋值的变量指向的zval的is_ref=0�Q�则直接指向�Q�refcount++�Q�若zval的is_ref=1�Q�则copy on write�Q�原zval refcount不变, 新变量指向一个新的zval�Q�is_ref=0, refcount=1;

2.如果是引用赋��|��用于复制的变量指向的zval的is_ref=0�Q�则copy on write�Q�原zval refcount--�Q�新变量和引用变量同时指向新的zval�Q�is_ref=1,refcount=2; 若zval的is_ref=1�Q�则直接指向,refcount++;

�?/a> 2010-05-18 22:45 发表评论

理论片午午伦夜理片久久,99久久做夜夜爱天天做精品,99精品国产99久久久久久97

A brief history of Consensus, 2PC and Transaction Commit.

Lock-Free

Lessons Learned from scaling Farmville

php copy on write