Slicer: Auto-Sharding for Datacenter Applications

語言: CN / TW / HK

Google Slicer是什麼

根據Paper定義:

Slicer is Google’s general purpose sharding service. It monitors signals such as load hotspots and server health to dynamically shard work over a set of servers. Its goals are to maintain high availability and reduce load imbalance while minimizing churn from moved work.

幾個key words:

  • General purpose sharding service:通用的分片服務,通用即意味著不限制應用場景
  • Shard work over a set of servers:關注分佈在眾多節點上的工作負載的熱點和健康狀態
  • High availability and load balance:目標是(應用的)高可用和節點的負載均衡

Slicer是Google內部通用分片(Shard)服務,旨在解決大規模分散式應用(單機應用就無需殺雞用牛刀)執行時的高可用、負載均衡等問題。為上層應用提供分散式應用通用問題解決方案,避免所有應用重複造輪子。

誕生背景

Google記憶體在眾多的複雜應用,這些應用使用者量大,全球部署,且需要提供7 * 24服務。

Slicer誕生之前,每個業務都需要自己搞定這些應用邏輯之外的事情,如多節點甚至跨AZ、Region部署,節點負載不均衡、難以彈性等問題,這些問題比應用本身複雜度更高,這顯著提升了應用的開發和運維難度。

因此Google內部急需一個統一的服務來幫他們解決這些難題,讓應用就像執行在單機上一樣簡單可靠,且機器資源利用率高,這就是Google Slicer誕生的背景。

整體架構

首先吐槽一下,論文中畫的圖夠粗糙的。在該架構中存在如下的基本概念:

Slicer Service: Slicer核心服務,對應用提供統一的Slice服務。Slicer內部維護Slice和Task的對映關係,同時,監控應用伺服器上的負載,在必要時將Slice在Task之間進行遷移

Clerk: 所有需要訪問應用服務的客戶端都透過Clerk與Slicer Server互動,它本質上是一個lib

Server: 也稱為Task,表示應用的一個執行例項,每個Server處理部分Slice請求

Slicelet: Server(Task)上執行的代理,負責同Slicer Service通訊,主要是彙報Server狀態、執行來自Slicer Service管理命令等

Job: 應用所有的Server稱為Job,這個名字怪怪的

Assigner :Slicer Service的核心模組,負責將Slice排程至Task,同時處理負載均衡,節點容錯等問題

Slice :一段Slice key,每個Slice被Assigner對映至某個Task,Slice也是負載遷移的基本單位

Application key :應用提供的shard key(一個字串,每個使用Slicer的應用都需要提供key,例如User id)。Slicer會將應用的key對映到Slice key space(2^63)。

Slicer的典型應用

In-memory Cache Applications

這也是Slicer最為常見的應用型別。

Flywheel

Google內部專為移動裝置設計的http proxy service,主要用來優化傳統網站對移動裝置的資料量不夠友好問題,通過壓縮、格式轉化(如原始網站圖片PNG轉WebP格式)等手段降低移動裝置訪問網站時的資料傳輸量,節約使用者成本。

作為Proxy,Flywheel內部有一些Task專門用來追蹤那些最近不可訪問的網站,這樣客戶端訪問這些網站時就可以立即返回錯誤而無需再去原始網站訪問直到超時,提升使用者體驗。

Flywheel為該功能專門建立了一些Task。沒有Slicer時,請求(更新與查詢)會被髮往任意一個Task,雖然可以工作,但效率比較低(如對於某個網站的狀態更新被髮往Task-A,而查詢網站狀態請求發往Task-B,但B上並沒有快取狀態,於是,上層認為該網站還是可服務的,但實際並不是,於是應用會直接訪問原始網站,導致超時,相當於快取並未生效,直到超時後應用將Task-B上狀態也更新)。

採用Slicer後,Flywheel將website url定義為key,這樣,相同key的請求會被髮往同一個Task,自然就解決了上面的問題。

In-memory Store Applications

這類應用不同於In-memory cache application,一旦請求在Task上未獲取到狀態,會從底層store中載入狀態(而cache則是無法處理)。

Aggregation Applications

這類應用特點是會將特定key的寫入請求聚合成batch寫入底層儲存以減輕下層壓力(在Google內很常見?)。

Event analysis

這類應用收集event,根據source id做聚合然後建模分析。

使用Slicer之前,應用不得不對每個event做複雜處理(例如多個節點寫入同樣的source id的event時需要處理併發控制等),代價非常大。

有了Slicer,應用將source id定義為key,擁有相同key的event會被髮往同一個Task處理。從而避免了多Task同時處理相同source id的event帶來的複雜邏輯(併發控制、event聚合等)。

其實沒有太搞清楚前面兩類應用在使用Slicer上有什麼本質上的區別。根據論文描述:

The in-memory caches in the previous section handle shard reassignment by discarding state, causing future requests to the moved keys to see a cache miss. In contrast, the tasks of an in-memory store load any missing data from an underlying store, and thus resharding events only affect latency; the stored data remains available.

理解一下也就是說:In-memory store Applications如果Task發現某個key在本地沒有,會從底層儲存中load上來再服務,也就是說,只會影響latency。In-memory cache Application難道不是這樣?

應用對接Slicer

Slicelet 介面

Application Server通過Slicelet提供的API與Slicer互動。主要的API有:

interface Slicelet { 
  boolean isAffinitizedKey(String key); 
  Opaque getSliceKeyHandle(String key); 
  boolean isAssignedContinuously(Opaque handle); 
} 
 
interface SliceletListener { 
   void onChangedSlices(List<Slice> assigned, 
       List<Slice> unassigned); 
}

一些簡單Application,例如上面提到的Flywheel可以完全忽略這些實現這些API,因為每個Server都可以處理任意的Request。

另外,應用還可以註冊一個SliceletListener,這樣,應用便可以對slice的來到(為server分配了新slice)或者離去(將slice從server上遷移走)進行處理(例如新slice來到時可以進行狀態預取,slice遷移走時可以進行資源回收)。

isAffinitizedKey 用於判斷key是否由該server處理(這個難道不是由Slicer處理的麼?),對於某些請求,可能將key發往錯誤的server,此時轉發可能比在該錯誤server上處理代價更小。

getSliceKeyHandle 是為了支援某些應用場景中,key需要由某個Server獨佔處理以維護一致性語義(難道Slicer本來不就是這樣麼?這塊沒有太清楚)。

Clerk Interface

interface Clerk { 
  Set<Addr> getAssignedTasks(String key); 
}

這個介面含義是將key對映到Server(Task)上,多數應用都可以無需實現這個介面,因為會有預設的實現。先將應用指定的key對映到一個Slice key space的某個Slice上,然後再將其對映至Task。

Slicer利用了Google的Stubby來實現流量的負載均衡。Slicer擴充套件了Stubby,在每個請求中攜帶Slice key,Stubby首先選擇與客戶端最近的data center(可能很多資料中心都部署了應用的Task),然後Slicer從該data center中根據該key定位到所在的Task。

在每個Data center內部又使用了GFE(Google Front End),它是資料中心內的HTTP請求代理層:

The GFE is an HTTP proxy that accepts requests from the Internet and routes each to an internal task .

實現

Slicer的核心目標是:

Slicer aims to combine the high-quality, strongly consistent sharding decisions of a centralized system with the scalability, low latency, and fault tolerance associated with local decisions.

Assigner

Assigner是Slicer最為核心的模組。Assigner的主要工作是根據分片演算法生成assignment(其實就是Slice到Task的對映)。

為了提供高可用能力,Google在全球多個數據中心部署了Assigner服務,任意一個Assigner都可以為任意的data center中的Job生成assignment。

多Assigner部署解決了服務可用性問題,但問題是同時assign可能會導致的衝突問題,Slicer這麼解決:

Assigner從底層的一個一致性儲存系統中讀取狀態(狀態內容是什麼?),生成新的assignment,併為該assignment分配一個新的全域性遞增的generation number,然後將該assignment寫回到底層storage(通過事務模式)並且攜帶了讀取時的value(這個value是上次讀取時最後一個assigment的generation number嗎?)。如果有多個Assigner併發寫,本次事務將放棄,重新走一遍上面的流程。

顯然,上面這種樂觀的事務衝突模型會影響assign效率。於是,Slicer進行了進一步優化,策略也很簡單:對於某個Job,只讓一個特定的Assigner為其服務,避免了競爭。怎麼做到的呢?每個Assigner會poll Google的全域性load balancer服務,去檢查一下它自己是否是當前所服務的Job裡面最近的一個(可能有多個Assigner服務一個Job,每個Job都去檢查一下它與Job所在的資料中心的網路距離)。如果是,它就作為Job的唯一服務方,如果不是,應該就會放棄服務權。

如果一個使用者的Job部署在多個數據中心。那麼Slicer首先根據Google load balancer選擇一個數據中心,然後在資料中心內部選擇一個Task。

Scalable of assignment

Slicer的核心任務是將Slice key space 對映到應用Tasks上,每個對映就是一次assigment,某些大型Job可能會有成千上萬 Task,會產生大量assigment。這些assigment資訊需要被傳遞至所有的Task以及client上去(統一稱之為subscribers。有幾個問題:1. 為什麼需要被傳遞至Task上去?Task維護自身的不就可以嗎?2. Client直接同Slicer要不就可以嗎,效率太低?),尤其是assigment時刻在動態變化,如何將這些變化迅速反饋呢?

Slicer使用了兩層distribution樹來解決該問題,如下圖:

Assigner生成assignment,將其分發給Distributor,Distributor再將其分發給client。確切地說,是一種pull的模式:Client向Distributor獲取Job的assigment,如果Distributor沒有,Distributor自身會從Assigner獲取。Distributor本身也是基於Google Load balancer構建的服務。Distributor本身應該也有watch機制來監聽Assigner上的assignment變化,但肯定是非同步的,這可能會導致某些對一致性要求較高的Application出問題,這通過一種獨立的控制通道來解決該問題。

沒有看出來這個兩層Distribution架構帶來了什麼好處?

容錯

Slicer通過以下方式進行服務容錯:

Backup Assignment Retrieval Path

Slicer包含一個 Backup Distributor, 一旦正常的Distributor無法服務, Backup Distributor 會從Store中直接讀取assignment直接讀取狀態並對外提供服務。一旦Assigner和Distributor都掛了,Backup Distributor還可以對外提供一種只讀服務。

Geographic Diversity

Assigner和Distributor可以全球部署,任何的client可以通過Google load balancer聯絡任意的Distributor,Distributor也可以聯絡任意的Assigner。

每個Job有prefered Assigner(網路距離最近的那個),一旦Job的prefered Assigner掛掉,其他任意Assigner可以接手。這種策略可以容忍機器、資料中心以及網路故障。

Geographic Proximity

每個Job的prefered Assigner是與Job網路距離最近的那一個,Distributor也會在Assigner所在資料中心部署,這些策略都減少了跨資料中心的網路傳輸,提升效率且減少網路故障帶來的影響。

甚至,如果應用需要,整個Slicer service都可以與應用統一獨立部署。

Fate-Shared Storage Placement

這也叫命運共同體式部署。將Assigner同應用部署在相同資料中心(儲存同樣在一起)。可以進一步減少資料中心之間的網路分割槽對服務造成的影響。

Service-Independent Mode

在Clerk中增加cache。這樣,即使所有的service都不可用了,靠著cache還可以勉強支撐。

Load Balance

Slicer的對映模型是首先將Application自定義的key(如user id)通過hash計算對映到一個key space(2^63),然後將這個key space劃分為多個slice(key range),然後再將slice對映至Task。

一般來說,通過第一步的hash計算得到的key分佈應該是均勻的,但某些熱點key還是會造成某些Task的負載上升。

有兩種方式可以緩解負載不均衡:為key增加額外Task、改變key的對映。

另外,Slicer還支援slice的split和merge。通過將熱點Slice進行split,一個Slice可以變為兩個,進而負載自然就會分解到多個Task。同時,Merge可以控制系統Slice數量。

Sharding Algorithm: Weighted-move

描述流程性的東西,核心思想就是基於負載的遷移,忽略。

Rebalancing suppression

一旦達到某些負載均衡指標,遷移就會被抑制,避免無意義工作。

Limitations

當前的balance演算法沒有考慮兩個方面:1. Task的異構性(沒有太理解)2. 記憶體使用(記憶體使用和CPU利用率不一定正向相關)

A rejected design alternative

paper闡述了為什麼沒有采用一致性hash( load-aware consistent hashing ),有以下幾點:

  1. Sevolving clients is burdensome
  2. consistent hashing gives us less control over hot spots

The load-aware consistent hashing algorithm we abandoned is similar to that in Centrifuge [10]. It was more sophisticated in that it supported key replication, asym- metric replication, and proportional response to imbal- ance for faster reaction. After 18 months in service, we replaced it with the weighted-move algorithm, which balances better with less key churn.

參考