摘要：?這個(gè)是Amazon Aurora 發(fā)的第二篇文章, 發(fā)在2018 年SIGMOD上, 題目很吸引人避免在I/O, commit, 成員變更的過(guò)程使用一致性協(xié)議. 在大家都在使用一致性協(xié)議(raft, multi-paxos)的今天, Aurora 又提出來(lái)了不用一致性協(xié)議來(lái)做, 主要觀點(diǎn)是現(xiàn)有這些協(xié).

這個(gè)是Amazon Aurora 發(fā)的第二篇文章, 發(fā)在2018 年SIGMOD上, 題目很吸引人避免在I/O, commit, 成員變更的過(guò)程使用一致性協(xié)議. 在大家都在使用一致性協(xié)議(raft, multi-paxos)的今天, Aurora 又提出來(lái)了不用一致性協(xié)議來(lái)做, 主要觀點(diǎn)是現(xiàn)有這些協(xié)議太重, 而且會(huì)帶來(lái)額外的網(wǎng)絡(luò)開(kāi)銷, 也可以理解, 畢竟Aurora 是6副本, 主要的瓶頸是在網(wǎng)絡(luò)上. 那么他是怎么做的?

因?yàn)锳urora 很多細(xì)節(jié)還是沒(méi)有揭露, 所以很多內(nèi)容是我自己的解讀, 以及問(wèn)的作者, 如果錯(cuò)誤, 歡迎探討

這篇文章也主要回答這個(gè)問(wèn)題.

Aurora is able to avoid distributed consensus during writes and commits by managing consistency points in the database instance rather than establishing consistency across multiple storage nodes.

在Aurora 中, storage tier 沒(méi)有權(quán)限決定是否接受write, 而是必須去接受database 傳過(guò)來(lái)的write. 然后都是由database tier 去決定是否這個(gè) SCL, PGCL, VCL 是否可以往前推進(jìn), 也就是說(shuō) storage tier 本身并不是一個(gè)強(qiáng)一致的系統(tǒng), 而僅僅是一個(gè)quorum 的系統(tǒng), 需要database tier 來(lái)配合實(shí)現(xiàn)強(qiáng)一致.

這個(gè)也是與當(dāng)前大部分的系統(tǒng)設(shè)計(jì)不一樣的地方, 當(dāng)前大部分的系統(tǒng)都是基于底層強(qiáng)一致, 穩(wěn)定的KV(當(dāng)然也可以叫Block storage) 存儲(chǔ), 然后在上層計(jì)算節(jié)點(diǎn)去做協(xié)議的解析和轉(zhuǎn)換. 而Aurora 提出底層的系統(tǒng)只需要是一個(gè)quorum 的系統(tǒng), storage tier + database tier 實(shí)現(xiàn)一個(gè)強(qiáng)一致的方案.

比如像Spanner 里面, 每一個(gè)spanservers 本身是多副本, 多副本之間通過(guò)multi-paxos 來(lái)保證數(shù)據(jù)的一致性, 然后上層的F1 這一層主要做的協(xié)議轉(zhuǎn)換, 把SQL 協(xié)議轉(zhuǎn)換成kv 請(qǐng)求去請(qǐng)求spanserver.

我們的PolarDB 也是這樣的一套系統(tǒng), 底層的存儲(chǔ)節(jié)點(diǎn) polarstore 是一個(gè)穩(wěn)定可靠的強(qiáng)一致系統(tǒng), 上層的計(jì)算節(jié)點(diǎn)PolarDB 是一個(gè)無(wú)狀態(tài)的節(jié)點(diǎn).

接下來(lái)具體的 Aurora 是如何實(shí)現(xiàn)的呢?

Term:

• LSN: log sequence number

每一條redo log 有一個(gè)唯一的單調(diào)遞增的 Log Sequence Number(LSN), 這個(gè)LSN 是由database 來(lái)生成, 由于Aurora 是一寫多讀的結(jié)構(gòu), 很容易滿足單調(diào)遞增

• SCL: segment complete LSN

SCL(segment complete LSN) 表示的是當(dāng)前這個(gè)segment 所知道的最大的LSN, 在這個(gè)SCL 之前的所有記錄當(dāng)前這個(gè)節(jié)點(diǎn)已經(jīng)收到, 到SCL 位置的數(shù)據(jù)都是連續(xù)的.?這里與VCL 的區(qū)別是, VCL 是所有節(jié)點(diǎn)確認(rèn)的已經(jīng)提交的LSN, 而SCL 是自己認(rèn)為確認(rèn)已經(jīng)提交的LSN, VCL 可以認(rèn)為是storage node 的commit index, 而SCL只是記錄當(dāng)前節(jié)點(diǎn)的LastLogIndex?Aurora 也會(huì)使用這個(gè)SCL來(lái)進(jìn)行節(jié)點(diǎn)間交互去補(bǔ)齊log.

• VCL: volume complete LSN

這個(gè)VCL 就是storage node 認(rèn)為已經(jīng)提交的LSN, 也就是storage node 保證小于等于這個(gè)VCL 的數(shù)據(jù)都已經(jīng)確認(rèn)提交了, 一旦確認(rèn)提交, 下次recovery 的時(shí)候, 這些數(shù)據(jù)是保證有的. 如果在storage node recovery 階段的時(shí)候, 比VCL 大于的數(shù)據(jù)就必須要?jiǎng)h除, VCL 相當(dāng)于commit Index. 這個(gè)VCL 只是在storage node 層面保證的, 有可能后續(xù)database 會(huì)讓VCL 把某一段開(kāi)始的 log 又都刪掉.

這里VCL 只是storage node 向database 保證說(shuō), 在我storage node 這一層多個(gè)節(jié)點(diǎn)已經(jīng)同步, 并且保證一致性了.這個(gè)VCL 由storage node 提供.

• PGCL: Protection Group Complete LSN

每一個(gè)分片都有自己的SCL, 這個(gè)SCL 就叫做PGCL. 等于說(shuō)SCL 是database 總的SCL, 每一個(gè)分片有各自的PGCL, 然后這個(gè)database 的SCL 就等于最大的這個(gè)PGCL

• CPL: consistency point LSN

CPL 是由database 提供, 用來(lái)告訴storage node 層哪些日志可以持久化了, 其實(shí)這個(gè)和文件系統(tǒng)里面保證多個(gè)操作的原子性是一樣的方法.

為什么需要CPL, 可以這么理解, database 需要告訴storage node 我已經(jīng)確認(rèn)到哪些日志, 可能有些日志我已經(jīng)提交給了storage node了, 但是由于日志需要truncate 進(jìn)行回滾操作, 那么這個(gè)CPL就是告訴storage node 到底哪些日志是我需要的, 其實(shí)和文件系統(tǒng)里面保證多個(gè)操作原子性用的是一個(gè)方法, 所以一般每一個(gè)MTR(mini-transactions) 里面的最后一個(gè)記錄是一個(gè)CPL.

• VDL: volume durable LSN

因?yàn)閐atabase 會(huì)標(biāo)記多個(gè)CPL, 這些CPL 里面最大的并且比VCL小的CPL叫做VDL(Volume Durable LSNs). 因?yàn)閂CL表示的是storage node 認(rèn)為已經(jīng)確認(rèn)提交的LSN, 比VCL小, 說(shuō)明這些日志已經(jīng)全部都在storage node 這一層確認(rèn)提交了, CPL 是database 層面告訴storage node 哪些日志可以持久化了, 那么VDL 表示的就是已經(jīng)經(jīng)過(guò)database 層確認(rèn), 并且storage node層面也確認(rèn)已經(jīng)持久化的Log, 那么就是目前database 確認(rèn)已經(jīng)提交的位置點(diǎn)了.

所以VDL 是database 這一層已經(jīng)確認(rèn)提交的位置點(diǎn)了, 一般來(lái)說(shuō)VCL 都會(huì)比VDL 要來(lái)的大, 這個(gè)VDL 是由database 來(lái)提供的, 一般來(lái)說(shuō)VDL 也才是database 層面關(guān)心的, 因?yàn)閂CL 中可能包含一個(gè)事務(wù)中未提交的部分.

• MTR: mini transaction

那么事務(wù)commit 的過(guò)程就是這樣, 每一個(gè)事務(wù)都有一個(gè)對(duì)應(yīng)"commit LSN", 那么這個(gè)事務(wù)提交以后就去做其他的事情, 什么時(shí)候通知這個(gè)事務(wù)已經(jīng)提交成功呢? 就是當(dāng)VDL(VDL 由databse 來(lái)發(fā)送, storage service來(lái)確認(rèn)更新) 大于等于"commit LSN" 以后, 就會(huì)有一個(gè)專門的線程去通知這個(gè)等待的client, 你這個(gè)事務(wù)已經(jīng)提交完成了.

如果這個(gè)事務(wù)提交失敗, 那么接下來(lái)的Recovery 是怎么處理的呢?

首先這個(gè)Recovery 是由storage node 來(lái)處理的, 是以每一個(gè)PG 為維度進(jìn)行處理, 在database 起來(lái)的時(shí)候通過(guò) quorum 讀取足夠多的副本, 然后根據(jù)副本里面的內(nèi)容得到VDL, 因?yàn)槊恳粋€(gè)時(shí)候最后一條記錄是一個(gè)CPL, 這些CPL 里面最大的就是VDL, 然后把這個(gè)VDL 發(fā)送給其他的副本, 把大于VDL 的redo log 清除掉, 然后恢復(fù)這個(gè)PG的數(shù)據(jù)

• SCN: commit redo record for the transaction

也就是一個(gè)transaction 的 commit redo record, 每一個(gè)transaction 生成的redo record 里面最大commit LSN. 主要用于檢查這個(gè)事務(wù)是否已經(jīng)被持久化了

這里就是通過(guò)保證SCN 肯定小于VCL 來(lái)進(jìn)行保證提交的事務(wù)是一定能夠持久化的, 所以Aurora 一定是將底下的VCL 大于當(dāng)前這個(gè)transaction 的SCN 以后才會(huì)對(duì)客戶端進(jìn)行返回

• PGM-RPL: Protection Group Minimum Read Point LSN

這個(gè)LSN 主要是為了回收垃圾使用, 表示的是這個(gè)database 上面讀取的時(shí)候最低的LSN, 低于這個(gè)LSN 的數(shù)據(jù)就可以進(jìn)行清理了. 所以storage node 只接受的是PGMRPL -> SCL 之間的數(shù)據(jù)的讀請(qǐng)求

那么寫入流程是怎樣?

在database tier 有一個(gè)事務(wù)需要提交, 那么這個(gè)事務(wù)可能涉及多個(gè)分片(protection group), 那么就會(huì)生成多個(gè)MTRs, 然后這些MTRs 按照順序提交log records 給storage tier. 其中每一個(gè)MTR 中有可能包含多條log records, 那么這多條log records 中最后一條的LSN, 也稱作CPL. storage tier 把本地的SCL 往前移. database tier 在接收到超過(guò)大多數(shù)的storage node 確認(rèn)以后, 就把自己的VCL 也往前移. 下一次database tier 發(fā)送過(guò)來(lái)請(qǐng)求的時(shí)候, 就會(huì)帶上這個(gè)新的VCL 信息, 那么其他的storage node 節(jié)點(diǎn)就會(huì)去更新自己的VCL 信息.

那么讀取的流程是怎樣?

在aurora 的quorum 做法中, 讀取的時(shí)候并沒(méi)有走quorum.

從master 節(jié)點(diǎn)來(lái)說(shuō), master 在進(jìn)行quorum 寫入的時(shí)候是能夠獲得并記錄每一個(gè)storage node 當(dāng)前的VDL, 所以讀取的時(shí)候直接去擁有最新的VDL 的storage node 去讀取即可.

對(duì)于slave 節(jié)點(diǎn), master 在向storage node 寫redo record 的同時(shí), 也異步同步redo log給slave 節(jié)點(diǎn), 同時(shí)也會(huì)更新VDL, VCL, SCL 等等這些信息給從節(jié)點(diǎn), 從節(jié)點(diǎn)本身構(gòu)造本地的local cache. 并且slave 節(jié)點(diǎn)也擁有全局的每一個(gè)storage node 的VDL 信息, 因此也可以直接訪問(wèn)到擁有最新的storage node 的節(jié)點(diǎn).

個(gè)人觀點(diǎn):

這篇文章開(kāi)頭講的是通過(guò) quorum I/O, locally observable state, monotonically increasing log ordering 三個(gè)性質(zhì)來(lái)實(shí)現(xiàn)Aurora, 而不需要通過(guò)一致性協(xié)議. 那我們一一解讀

這里的monotonically increasing log ordering 由LSN 來(lái)保證, LSN 類似于Lamport 的 logic clock(因?yàn)檫@里只有一個(gè)節(jié)點(diǎn)是寫入節(jié)點(diǎn), 并且如果寫入節(jié)點(diǎn)掛了以后有一個(gè)恢復(fù)的過(guò)程, 因此可以很容易的保證這個(gè)LSN 是遞增的)

locally observable state 表示當(dāng)前節(jié)點(diǎn)看到的狀態(tài), 也就是每一個(gè)節(jié)點(diǎn)看到的狀態(tài)是不一樣的, 每一個(gè)節(jié)點(diǎn)(包含database node 和 storage node) 都有自己認(rèn)為的 SCL, VCL, VDL 等等信息, 這些信息表示的是當(dāng)前這個(gè)節(jié)點(diǎn)的狀態(tài), 那么就像Lamport logic clock 文章中所說(shuō)的一樣, 在分布式系統(tǒng)中沒(méi)有辦法判斷兩個(gè)不同節(jié)點(diǎn)中的狀態(tài)的先后順序, 只有當(dāng)這兩個(gè)狀態(tài)發(fā)生消息傳遞時(shí), 才可以確定偏序關(guān)系. 那么在這里就是通過(guò)quorum I/O 確定這個(gè)偏序關(guān)系

quorum I/O 在每一次的quorum IO達(dá)成確認(rèn)以后, 就相當(dāng)于確認(rèn)一次偏序關(guān)系. 比如在一次寫入成功以后, 那么我就可以確定當(dāng)前的data node 的狀態(tài)一定是在其他的storage node 之前. 在一次gossip 節(jié)點(diǎn)間互相確認(rèn)信息以后, 主動(dòng)發(fā)起確認(rèn)信息的節(jié)點(diǎn)的狀態(tài)也一定在其他節(jié)點(diǎn)之前. 所以整個(gè)系統(tǒng)在寫入之后或者在重啟之后的gossip 一定能夠存在一個(gè)在所有節(jié)點(diǎn)最前面的狀態(tài)的節(jié)點(diǎn), 那么這個(gè)節(jié)點(diǎn)的狀態(tài)就是當(dāng)前這個(gè)系統(tǒng)的狀態(tài), 這個(gè)狀態(tài)所包含的SCL, VCL, VDL 信息就是一致性信息

在每一次讀取的時(shí)候, 他所在的節(jié)點(diǎn)一定是當(dāng)前這個(gè)偏序關(guān)系最前面的位置, 因?yàn)樽x取操作之前一定是write 或者 recovery 操作, 在write, recovery 操作的過(guò)程中, 就與超過(guò)半數(shù)的節(jié)點(diǎn)達(dá)成一致, 走在了偏序關(guān)系的最前面. 獲得了當(dāng)前節(jié)點(diǎn)的local observable state. 所以讀到的一定是最新的內(nèi)容

Aurora 系統(tǒng)很容易實(shí)現(xiàn)的一個(gè)重要原因是他是只有一個(gè)writer 存在, 這樣保證了同一時(shí)刻只可能在發(fā)生一個(gè)事件

剛開(kāi)始看會(huì)覺(jué)得這個(gè)系統(tǒng)比較瑣碎, 不像Paxos/raft 那樣有一個(gè)比較完備的理論證明, 不過(guò)問(wèn)過(guò)作者, 實(shí)現(xiàn)這一套過(guò)程也是經(jīng)過(guò)TLA+的證明

閱讀原文

本文為云棲社區(qū)原創(chuàng)內(nèi)容，未經(jīng)允許不得轉(zhuǎn)載。