Distributed system時間篇

上次講到,Lesie Lampert主張用replicated state machine去處理distributed system,而其中最難就係consensus problem。點解呢?最難明白既,就係時間。唔同電腦之間,要對x有共識,即係要對x既sequence有共識,而咁樣基本上就係時間既共識。但係愛因斯坦話你知,咁樣係無可能。根據相對論,時間係決取於你既reference frame同加速度,而唔係獨立架。舉個例,如果銀河系有兩個星球,星球A同星球B都各住左一隻怪獸。假設佢地互相感應,而一齊唱歌,你會聽到邊隻怪獸既歌聲先?個答案就係,睇你近邊個星球多啲。你係I區,你就會聽到係A先;係II區,又會聽到係B先;而係III,就會同時聽到。所以,如果你將怪獸當返入電腦,而你係第三部電腦,嘗試判斷兩部電腦,邊一部講x先,你跟本唔會得出一致既答案。


既然係咁,如果每部機睇到既時間都唔同,可以點樣考慮次序呢?Leslie Lamport提出了因果序(Causal Order)。簡單講,係同一部電腦,就係按執行先後。而唔同電腦,就按收發先後。最後,如果A先於B,B先於C,則A先於C。如果兩者之間無先後,就係同時發生。如下圖,則A先於B,B先於C;C先於D;E先於D。而A和E同時發生。B和E都係同時發生。


由此可見,一個系統既所有事(event),按因果序只係局部有序(Partial order),而唔係全部有序(Total order)。調返轉講,如果某algorithm既events係total order,咁證明correctness就同單機無分別,唔洗考慮concurrent execution。比如apache zookeeper既證明,其中一步就係證明電腦既加入同退出,係total order。去到應用層面,如果想推測一個系統既causal order,可以用Lampert clock或者Vector clock。兩者各有限制。


以上就係distributed system既時間觀念。

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.