一向低調(diào)的AWS終于在2022年發(fā)了一篇關于DynamoDB的論文——《 Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service》。（論文地址：https://www.usenix.org/system/files/atc22-elhemali.pdf）這已經(jīng)距離DynamoDB發(fā)表的第一篇論文已經(jīng)過去了15年。當然，業(yè)界的人都知道，15年前的那一篇《Dynamo Amazon's Highly Available Key-value Store》與現(xiàn)在在AWS運行的DynamoDB沒有任何關系，原作者從Amazon跳槽到FaceBook，做出了Cassandra，因此它實際上是Cassandra的理論基礎。所以，外界都只能通過AWS公開的文檔和演講中來對DynamoDB的架構和細節(jié)管中窺豹。從DynamoDB 2012年在AWS上線到現(xiàn)在已經(jīng)十年了，也許這篇文章，就是DynamoDB團隊為大家獻出的十周年慶典回饋活動吧。DynamoDB 2022 Paper是一篇典型的Industry Paper，整篇讀下來沒有復雜的理論和公式，連文章最后的性能測試放上的幾張圖，都感覺有拼湊嫌疑……在文中大量的篇幅，都是在講DynamoDB這十年來面對業(yè)務的需求和面對Serverless這個模式的挑戰(zhàn)下的不斷改進和經(jīng)驗總結。比如論文中還詳細講了DynamoDB怎么去升級和回滾，把版本bug的影響降到最低，這對于同在產(chǎn)業(yè)界的我們來說，這些經(jīng)驗和教訓真的是感同身受。無獨有偶，Lindorm基本上是與DynamoDB正式發(fā)布的差不多時間在阿里上線的。Lindorm在阿里的發(fā)展也十年有余了。Lindorm的發(fā)展路線基本與DynamoDB一致，先是在阿里內(nèi)部支撐海量的電商業(yè)務，如淘寶訂單，菜鳥物流，支付寶風控等等，到后來開始在阿里云上對外售賣，逐漸轉變成一個云原生的多模數(shù)據(jù)庫，以低成本，海量存儲，高吞吐，高擴展性，高性能等特點支持了云上各類客戶。DynamoDB2022Paper中說他在去年的Prime Day購物節(jié)中，最高QPS達到了8000萬/s，而實際上在去年雙十一時，阿里內(nèi)部所有Lindorm集群的峰值吞吐達到了8.8億/s。從這點上來看，Lindorm的實際規(guī)模已經(jīng)遠遠大于DynamoDB的部署。當然，DynamoDB和Lindorm在定位上還是有一些差異的，Lindorm通常面對的都是有海量存儲需求的大客戶，而DynamoDB更看重全托管，開箱即用，按需付費等等。但是同樣做為一個分布式的NoSQL數(shù)據(jù)庫，很多設計的思考都是相通的。特別是這幾年Lindorm也做了一些Serverless的嘗試和熱點自愈的工作，和paper中提到的還是有一些類似的。所以，我這篇文章不單單是DynamoDB論文的一篇解讀文章。我覺得單純解讀太沒意思了，肯定有人會把這篇論文翻譯成中文。我更想在這篇論文中找出幾點我特別有感觸的，講講DynamoDB和Lindorm在對待這些問題上的思考和實現(xiàn)有一些什么異同。讓大家不僅能去了解DynamoDB的設計，還能獲得一些從未對外公開的Lindorm設計細節(jié)的干貨。做為一個Serverless數(shù)據(jù)庫來說，限流是一個再重要不過的能力了。因為DynamoDB就是靠計算用戶的讀寫量去計費的。在DynamoDB中，定義讀4KB的數(shù)據(jù)叫做1個RCU，寫1KB的數(shù)據(jù)叫做1個WCU，然后DynamoDB按照用戶購買的RCU,WCU收取計算費用和限流（Provision模式，On-Demand模式另說）。至于為什么讀4KB會計算成1個RCU，而寫1KB就算成一個WCU我猜測因為DynamoDB的存儲實際上是B樹，對于B樹結構來說，寫的代價要比讀的代價要高。另外DynamoDB有一個硬限制每個Partiton不能超過1000個CU。這樣，DynamoDB在用戶購買時，就會給用戶預分區(qū)。比如文中的舉例，如果用戶購買了3200WCU，那么在初始化表時，DynamoDB會自動分出4個Partition，每個partition限流800WCU。也就是說DynamoDB最初的限流是非常簡單粗暴的，限流就是預先分給每個Partition的值，達到了就會限流。這樣就會出現(xiàn)兩個問題：1. 當單個Partition的訪問量超過了800WCU，立馬就會限流，而達不到用戶買的3200WCU；2. 如果用戶購買了6000WCU，由于DynamoDB的單Partition最多只能承載1000個WCU，DynamoDB會把用戶之前的4個Partition分裂成8個，這樣每個Partition的限流值反而下降為6000/8=750WCU，每個Partition的限流值下降了，如果此時用戶又把6000WCU改回3200WCU，那更糟糕了，每個Partition最多只能請求3200/8=400WCU，用戶提升了然后下降了provision的WCU，Partition能承載的WCU卻降了一半，用戶一臉懵逼。
這樣的使用體驗是很差的。所以DynamoDB做了兩個改進。第一個改進是Burst。所謂burst，就是支持把前幾秒沒用完的Quota攢起來，當用戶超過預設的限流值時，可以先消耗之前攢的WCU，而不會觸發(fā)限流。但這個攢CU是有限的，DynamoDB支持最多攢5分鐘的CU。而且，盡管DynamoDB沒有在論文和任何文檔中提起，我覺得攢的這個CU應該是不能超過每個Partition 1000WCU這個硬限制的。Burst解決了用戶短暫的突發(fā)流量訪問的問題，但是，如果用戶的數(shù)據(jù)訪問本身就是傾斜的（這種Case是非常常見的），burst沒法解決這樣的問題。
因此DynamoDB又做了一個Adaptive Capacity。簡單來說，就是自動地按需調(diào)整每個partition的限流值。如上圖中的例子，用戶買了400WCU，表有4個Partition（除了CU限制，如果Partition大小超過10GB，DynamoDB也會分裂），每個Partition可以有100WCU，如果用戶的請求在Partition4上比較多，DynamoDB會自動地把Partition4的限流設置為150，當然，表上總的CU不能超過購買的400。
在我看來，Adaptive Capacity是一個滯后的調(diào)整方案，也就是說用戶可能先會遭受限流的拋錯，DynamoDB識別到了這種情況，才能做自適應地調(diào)整。而且，整個DynamoDB限流是按Partition來做的初衷是想讓整個架構簡單，不想引入一個中心節(jié)點來做限流控制，而Adaptive Capacity功能使DynamoDB不得不引入一個Global Admission Control（GAC）角色來做整個集群的調(diào)解和控制，原本想極力避免的設計復雜性又不得已加了回來。
其實，DynamoDB的限流策略并非首次公開，Burst和Adaptive Capacity在DynamoDB的文檔中已經(jīng)有過詳細描述。Lindorm在做限流模塊時，也研究過DynamoDB的這些策略，我們覺得DynamoDB的限流策略并不是特別的好（但論文中宣稱做了Burst和Adaptive Capacity后解決了99.99%的數(shù)據(jù)傾斜訪問問題，只能說DynamoDB面對的客戶和Lindorm差異非常大）。
所以Lindorm在設計自己的限流模塊時遵循了3個原則：
1. 數(shù)據(jù)傾斜訪問是常態(tài)，即使用戶只訪問一個Partition，也必須達到用戶在表上設置的限流值；3. 限流中心不能是系統(tǒng)單點，即使限流中心宕機，不影響正常請求。因此，Lindorm設計了如下圖的限流方案。
這個系統(tǒng)設計的核心是，用戶在請求過程中不會和限流中心做交互，全程只和本地的QuotaProxy打交道（全內(nèi)存操作），用戶請求完成后，會告訴QuotaProxy這個請求的消耗（對，Lindorm也用了WCU和RCU的概念，本章的末尾會回來討論Capacity Unit這個東西），QuotaProxy會定期向QuotaCenter匯報用戶的消耗，這樣QuotaCenter的壓力也只和服務器的規(guī)模相關，與用戶的請求無關。QuotaCenter接收各個服務器的匯報后，計算出這個用戶這一秒還有沒有Quota，如果沒有了，就會反饋給QuotaProxy。這樣，下次用戶來請求的時候，就會在Check本地的QuotaProxy過程中收到Quota超限的錯誤。留給讀者思考下，這樣的設計是怎么滿足上面的三個原則的。Lindorm也是用了WCU和RCU的定義來衡量請求的消耗。但靠計算請求的數(shù)據(jù)的大小真的能非常準確地衡量請求的資源消耗嗎？答案是否定的。舉一個簡單的例子，select * from table where a > 1 和 select * from table where a like '%xx%'這兩個請求即使掃描的數(shù)據(jù)一樣，而實際上消耗的CPU完全是不一樣的。所以用數(shù)據(jù)大小來衡量請求消耗只是一個極度簡化的模型。所以像做的比較好的Azure Cosmos的RU（Rquest Unit）模型定義，會更加復雜，他會把請求的編譯時間，CPU的消耗，數(shù)據(jù)量大小都會考慮成RU的一部分。當然，這也是一把雙刃劍，本來用戶去評估需要買的CU就已經(jīng)比較困難了，如果像Cosmos的這種定義，恐怕沒有幾個業(yè)務能夠準確估算自己業(yè)務的預算。
負載均衡是分布式系統(tǒng)一項非常重要的功能，熱點的partition也是切片數(shù)據(jù)庫非常常見的問題。當DynamoDB只有Provision（預留）模式時，負載均衡是非常好做的，因為每個Partition的流量上限是定死的，系統(tǒng)只需要平均分配這些Partition，讓他們provision的總值在各個服務器上差不多即可。如果有用戶改變了Provision的值，只需按照新的預留值該split的split，該重新分配的重新分配服務器，不需要太復雜的算法。但是，當DynamoDB上了On-Demand（按量付費）模式時，負載均衡會變得更加復雜。用戶的每個Partition上沒有固定的限流值了，用戶想用多少就用多少，然后按照請求量取付費。這個模式下會對負載均衡系統(tǒng)提出非常大的挑戰(zhàn)。同時，Burst和Adaptive Capacity也會帶來很多流量會超限的Partition，文中稱其為“noisy neighbors”。DynamoDB2022Paper中提到為了解決負責均衡的問題，他們實現(xiàn)了一套系統(tǒng)去監(jiān)控每個節(jié)點的吞吐，如果出現(xiàn)節(jié)點負載過高或者不均衡的情況，就會自動發(fā)起一次partition的move操作。另外，當Partition的請求達到一定閾值，就會觸發(fā)Partition的分裂，并且這個split point不單單是從Partition的中間，而是會分析流量，找到最佳的split point。并且，文中還特別提到，DynamoDB能夠識別順序?qū)懞蛦蝛ey熱點，這兩種熱點情況，即使split也是沒有效果的。論文中沒有透露DynamoDB中怎么實現(xiàn)這個熱點識別和負載均衡的細節(jié)，但是，Lindorm在處理這些問題上的思路其實和DynamoDB是差不多的，我可以給大家講講在Lindorm中是怎么做的。在Lindorm中，其實負載均衡的問題會更加棘手，因為在Lindorm中是不會給每個partition去設置限流的，因此不能像DynamoDB那樣根據(jù)每個Partition的WCU/RCU去做負載均衡。因此，必須要找到一個準確衡量每個Partition消耗的方式，合理布局Partition到每臺Server上。
Lindorm最先參考的是HBase的StochasticLoadBalancer。這個Balancer和它的名字一樣，異常復雜。它會根據(jù)讀請求數(shù)，寫請求數(shù)，文件數(shù)，本地化率等一系列條件做為輸入，通過用戶配置的權重因子，計算出一個集群均衡指數(shù)，然后再根據(jù)這個指數(shù)來進行Partition的負載均衡。這個算法初衷是挺好的，把能考慮到的因素都計算在內(nèi)了，但在實際的環(huán)境中，有的集群讀多寫少，有的集群讀少寫多，而且集群的情況在時刻變化。如果在Lindorm上使用這樣一個Balancer，面對不同的負載，那么我們的運維將陷入無盡地調(diào)參中不能自拔……
其實，StochasticLoadBalancer是想雨露均沾，合成一個準確衡量Partition資源消耗的值。那有沒有這樣一種衡量手段，能夠非常簡單直白，而又能相對準確地衡量每個Partition的資源消耗，來做為負載均衡的依據(jù)呢？其實是有的，這個值就是CPU時間片的消耗。不論是讀還是寫，只要是CPU時間片消耗的多，我們就可以認為這個Partition資源消耗比較大，因為對IO的消耗，最終也會反應到CPU上。有了每個Partition的CPU時間片消耗這個一個度量衡，那我們就可以對整個集群進行一些Partition（Lindorm中叫做Region）的swap操作，以達到一個每臺服務器的CPU消耗均衡狀態(tài)。這就是Lindorm的CpuUsageBasedBalaner。
另外一個就是熱點Partition的split。和DynamoDB一樣，Lindorm需要識別出熱點Partition的熱點類型，是順序?qū)懀瑔蝛ey熱點還是范圍熱點。如果是前兩者，這樣的熱點Partition是沒法用分裂來解決的，只能隔離。如果是范圍熱點，則需要知道范圍熱點的中間點在哪里，從中間切開，而不是像HBase那樣對等分。為了做到這點，Lindorm是采用了請求采樣的方式去做的。
熱點識別+CPUbased負載均衡+Region Normalizer+單key熱點限流+異常region隔離這幾個模塊統(tǒng)一形成了Lindorm的熱點自愈方案。目前這套方案基本能給Lindorm自動解決90%以上的線上熱點問題。對于絕大部分分布式數(shù)據(jù)庫來說，最繞不開的就是路由表了，從DynamoDB論文中的架構圖可以看到，任何請求都需要去路由表上查詢下真實后臺服務器的地址。如果路由表的服務出現(xiàn)問題，那么用戶的請求一定會受到影響。
減輕路由表服務壓力的通常做法是加一層緩存。但是DynamoDB認為加緩存可能遇到冷啟動時會造成緩存擊穿，會造成各個系統(tǒng)的不穩(wěn)定甚至級聯(lián)宕機。而且命中緩存和不命中緩存的請求RT差異巨大，不利于降低請求毛刺。因此DynamoDB現(xiàn)在的做法是加了一個分布式內(nèi)存存儲MemDS來存儲路由信息，MemDS可以水平擴展能夠承受整個集群的請求。用戶的請求只會和MemDS交互來查詢對應key的路由信息。如果發(fā)生Partition的路由變動，也會通知MemDS來做一個內(nèi)存信息的更改。如果用戶請求從MemDS這里得到了滯后的路由信息，則會觸發(fā)MemDS去查詢真正的路由表來獲取對的路由。這樣的話，對路由表的查詢壓力量級大大減少，只有在拋錯的情況下，MemDS才會去查詢真正的路由表。冷啟動時，路由表的信息也可以由其他MemDS節(jié)點同步，不會有冷啟動打爆的問題。
在寫這篇文檔前，我也拜讀過PingCap CTO黃東旭寫的這篇《Some notes on DynamoDB 2022 paper》，這里面提到DynamoDB做這個改變也可能是2015年這次重大故障（https://aws.amazon.com/cn/message/5467D2/）后的反思。簡單來說，那次DynamoDB上了全局二級索引后，對路由表的請求劇增導致了路由模塊的崩潰，進而導致整個服務崩潰。其實Lindorm早期在使用HBase的架構時，meta表是一個強單點，同樣有這樣的血淚教訓。所以Lindorm在設計客戶端路由時，雖然沒有去設計一個分布式內(nèi)存存儲，但實際上做的事情，也是有異曲同工的效果。
在Lindorm的設計中，每個QueryProcesser節(jié)點中都有一個RegionLocator模塊，用戶的請求不會直接去請求meta表，而是由RegionLocator模塊代為請求。用戶請求只會和RegionLocator交互，RegionLocator里會緩存路由信息。這樣無論用戶的客戶端有多少，請求有多少，meta表的壓力只與RegionLocator的數(shù)量有關。同樣在收到請求路由錯誤時，RegionLocator會去meta表里更新region的地址。自從Lindorm采用這套路由架構后，再也沒出現(xiàn)過meta表打爆的情況了。
DynamoDB做為業(yè)界一款優(yōu)秀的NoSQL數(shù)據(jù)庫，其10年的經(jīng)驗能讓人收獲不少反思。DynamoDB的誕生，發(fā)展并沒有什么驚天地泣鬼神的新功能，我從文中看到看到的，是一代代AWS工程師在面對業(yè)務挑戰(zhàn)，面對故障后不斷地對系統(tǒng)作出改進和修復，在業(yè)務的驅(qū)動下，一步一步地走到今天。做為數(shù)據(jù)庫行業(yè)的從業(yè)人員，在閱讀這篇Paper時，里面講的痛點總是有一種讓人“似曾相識”的感覺。Lindorm也走過了它的十年，Lindorm也是在海量的數(shù)據(jù)壓力下，各類業(yè)務的不斷呼喊以及各種故障的血淚教訓中不斷成長起來的。除了有些課題需要前沿的理論支持，絕大部分情況下，做數(shù)據(jù)庫就是要去不斷去攻克一個個的工程難題。最近，國產(chǎn)數(shù)據(jù)庫異?；鸨谖铱磥?，大家都是在各自的視角，各自的角度去嘗試解決客戶的問題，與一些老牌數(shù)據(jù)庫相比，我覺得這個里面沒有太多的技術壁壘，更多的是時間的積累還有彎道超車的勇氣，殊途同歸，大家一起共勉吧。做為國產(chǎn)自研數(shù)據(jù)庫中不可或缺的一員，我希望不久的將來，大家也可以看到Lindorm的Paper出現(xiàn)在頂會上。 / End /
