接續之前在 Medium 寫了一點的 Matrix 介紹，簡單來說 Matrix 這個東西可以理解成類似 Slack / telegram 的通訊軟體應用，好處是完全去中心化，還有端對端加密（不過這可能不是新聞了），還有它是開源的（方便你去做點事情）
前情提要
簡單帶過 Matrix 的架構，對於一個用戶 A （上圖中的 Matrix client A）來說，每當他想要對用戶 B 傳送一則訊息，它會把這則訊息包裝成 event 之後透過 API 函式調用 A 的 Homeserver（後面簡稱為伺服器），底層的 Homeserver 是實際的訊息交換主體，一旦 A’s homeserver 收到這則事件後，它會直接更新本地端的聊天紀錄副本（與 Raft 不同，他在更新本地副本前不需要取得共識），隨後 A’s homeserver 嘗試向所有同一個聊天室的用戶伺服器廣播這個更新過的副本（在這個例子裡，這個聊天室只有 A 與 B 兩個用戶），B 的伺服器一旦收到 A 伺服器傳過來的更新副本之後也會更新 B 伺服器自己的副本，最後用戶 B 會透過一個背景 GET 拿到新的訊息
這邊提到的「聊天紀錄副本」事實上不是用 Raft 那類簡單的 log 線性紀錄，而是採用樹狀圖做紀錄
Event Graph
Matrix 把所有的事件（包含傳送訊息，改變設定這類都視為事件）作為有向無環圖（DAG）的節點儲存起來，並且所有的 Homeserver 便在這基礎上維護 DAG 的共識
在正常的樹狀圖裡，一個節點通常只會有一個父節點，在 Matrix 父節點的語意則代表「上一則最接近的事件」
然而在 Matrix 的樹狀圖裡，由於先前提到的可能會有多個 Homeserver 在同一個時間段試圖更新同一個 Room 的狀態，我們無法區分哪個節點是「最接近的」，因此在 Matrix 中一個子節點可能會有多個父節點
Matrix 節點透過 depth 這個屬性決定事件的發生先後順序，也就是「對於節點 A, B，其深度表示為 DepA 與 DepB，則如果事件 A 較 B 早發生 ，則 DepA < DepB」
（目前由於還沒看源始碼，因此逆敘述成不成立還不知道，目前先假設它跟 logic clock 類似，也就是逆敘述不成立）
但是我們這樣不就會有衝突嗎？如上圖，Bob 與 Charlie 分別針對 message 1 做出了自己的回應（節點 2, 3），他們自己的伺服器也把這個新增訊息加上去了，這樣要怎麼解決圖的衝突呢？
如上圖，Matrix 採用了一個很機賊聰明的方法，它把衝突留在 DAG 裡，反正每個 homeserver 看到的東西都一樣，上面的 client 要怎麼解釋是 client 的事情 （這樣做等於是把衝突處理轉接給 client，底層伺服器只負責紀錄）
最後如果 Alice 之後又送了一則訊息（節點 4），則這則新訊息會接在上面這兩個衝突事件的下面，導致這個新節點有兩個父節點
Merge Conflict
每次訊息要被傳送時，該訊息會先被傳到該聊天室 （Room），聊天室有它特有的共享資源，描述目前聊天室的狀態，包含當前成員、伺服器、以及最近的訊息（recent unlinked event）
每當有複數個新事件要改變同一個狀態時（筆如有新成員加入），這時候就不能用前面那個機賊聰明的方法了（我們不會想要有些人知道 Charlie 進來了但是也有人不知道）
為了達成共識，這就需要我們的衝突算法（Merge Conflict Algorithm）介入了
有趣的是，它強調這個算法「必須與伺服器狀態完全獨立，也跟收到事件的順序無關下，必然的選擇某個事件（也就是不能靠隨機機率，而是要有一套判斷邏輯）」，簡單理解就是要是一個類 (non-probabilistic) pure function，這可能是因為每個伺服器都需要自行獨立判斷得出最後的共識狀態，因此需要在給定輸入的前提下，總是得到相同的結果（後面 State resolution Algorithm 會提到）
簡單的總結下，一旦發生衝突是 Room 需要去解決，Homeserver 只要去拿處理完的結果就好了，同時 Room 要怎麼處理衝突也跟它的版本相關（比較瑣碎的一點是， Matrix 的版本號不一定用新越好，主要看你的需求，所以 upgrade from version 2 to 1 是有可能的）
儘管看完他的（類）規格書之後，我感覺我的問題只有越變越多的趨勢（這可能也是它需要別人幫它補完規格書的原因）
以下是我看完之後一些腦中跳出來的問題
Questions
Number of DAG(s) ?
儘管我們知道 Matrix 透過 DAG 釐清事件的先後順序，但是 DAG 是每個 room 維護一個，還是整個 Matrix 維護一個 global DAG 而 room 只是這個 DAG 的 partial order 呢？
Where do the “room” locates ?
文章中反覆強調 Room 是一個抽象概念性的結構，並且它也有自己的屬性，那麼這些 Room 實際上是放在哪呢？我目前猜是放在 homeserver 上
Further message conflict ?
在前面的例子裡，衝突只有發生一次（Bob 和 Charlie），如果隨後 Alice 與 Bob 又同時發訊息而衝突了，那麼這兩個衝突節點應該用什麼方式接上去呢？另外，這樣是否會導致樹越來越胖？
如果你也跟我一樣對這些細節，包含實做細節與狀態共識怎麼實現的，那我推薦你也來看看這篇教學 State Resolution v2 for the Hopelessly Unmathematical （這個名字聽起來就很和善 – 給那些不是數學專家的人看的 – 也就是我們 =) ）
State resolution Algorithm
文章開頭就講到「Room 並非只屬於單一個伺服器，而是所有的伺服器共同維護自己的副本，並且獨立的到達一個共識的狀態」（這聽起來的確挺 eventual consistent 的，這代表一旦發生衝突就要開始 rollback）
這邊提到的 State resolution 算法（以下就簡稱為 SR 算法好了）就是用在「想辦法在兩個以上不同的狀態集合（每一個伺服器有屬於自己的狀態集合，可以看成 DAG）中，找到最終一致的狀態」（聽起來就是 eventual consistency 的 rollback 算法 ）
SR 算法有兩個大方向，第一個是 高優先序的優先，像是管理員下的事件應該優先一般用戶處理；另外一個是 先來的優先，這邊就是比較 tricky 的部份了，就算在分佈式系統裡也可以花上巨量時間討論誰先誰後該怎麼定義（e.g. Google spanner），所以 Matrix 也花了大把時間定義順序的問題
由於這邊算法其實挺多的，我決定之後再專門寫一篇 SR 算法的
照例來寫點心得好了，修完分佈式系統真的對看這種系統文章有幫助，不僅可以比較好用類比的方式理解它的運作原理/考量，也可以重新思考為什麼 Raft 要這麼做 / 不這麼做，並且想問題也可以想的比較細一點
再一次推薦大家去學 MIT 6.824 的課，反正課程資源都放網路上開源了，真的寫過一次會很痛苦舒服的 =)
Reference
- Matrix Specification, https://matrix.org/docs/spec/
- Room Version 1, https://matrix.org/docs/spec/rooms/v1