Google 怎麼解決長尾延遲問題
The Tail at Scale，是 Google 2013 年發表的一篇論文，大規模在線服務的長尾延遲問題。緩存
要知道怎麼解決長尾問題，先要理解長尾延遲是個什麼問題，在開發在線服務的時候，咱們都知道要關注服務的 p99/p999 延遲，要讓大部分用戶都可以在預期的時間範圍內得到響應。服務器
下面是一個不一樣響應時間的請求數分佈圖：網絡
大部分系統也都遵循這種分佈規律，如今互聯網的系統規模比較大，一個服務依賴幾十上百個服務的狀況都是有可能的。單一模塊的長尾延遲會在有大量依賴的狀況下，在服務粒度被放大，《The Tail at Scale》論文裏給出了這樣的例子。併發
考慮一個系統，大部分服務調用在 10ms 內響應，但 99 分位數的延遲爲 1 秒。若是一個用戶請求只在一個這樣的服務上處理，那麼 100 個用戶請求中只有一個會很慢（一秒鐘）。
這裏的圖表概述了在這種假設的狀況下，服務級別的延遲是如何被很是小几率的大延遲值影響的。
若是一個用戶請求必須從100個這樣的服務並行收集響應，那麼 63% 的用戶請求將須要超過一秒鐘（圖中標記爲 "x"）。
即便對於只有萬分之一律率在單臺服務器上遇到超過一秒的響應延遲的服務，若是服務的規模到達 2000 實例的話，也會觀察到幾乎五分之一的用戶請求須要超過一秒（圖中標記爲 "o"）。
Xargin 注：負載均衡
- 由於請求是並行的，因此只受最慢的那個影響，100 個請求都落在 99 分位內延遲纔會小於 1s，因此延遲小於 1s 的機率是 pow(0.99, 100) = 0.3660323412732292，也就是說必定有 63% 的機率會超過 1s。
- 第二個，咱們落在 99 分位的機率是 pow(0.9999, 2000) = 0.8187225652655495，也就是將近 20% 的用戶響應會超過 1s。
上面的表格列出了一個真實的谷歌服務的測量結果，該服務在邏輯上與前文簡化過的場景類似；根服務經過中間服務將一個請求分發到很是多的葉子服務。表展現了大量扇出(fan-out)調用時，對延遲分佈的影響。分佈式
在根服務器上測量的單個隨機請求完成的 99 分位延遲是 10ms。然而，全部請求完成的 99 分位數延遲是 140ms，95% 的請求 99 分位數延遲是 70ms，這意味着等待最慢的 5% 的慢請求要對總的 99 百分位數延遲的一半負責。對這些慢請求場景進行優化，會對服務的總體延遲產生巨大影響。ide
爲何會有長尾延遲？
單個服務組件的長尾高延遲可能因爲許多緣由產生，包括：測試
共享資源(Shared resources，Xargin: 混部如今愈來愈多了)。機器可能被爭奪共享資源(如 CPU 核心、處理器緩存、內存帶寬和網絡帶寬)的不一樣應用所共享，而在同一應用中，不一樣的請求可能爭奪資源。
守護程序(Daemons)。後臺守護程序可能平均只使用有限的資源，但在運行時可能會產生幾毫秒的峯值抖動。
全局資源共享(Global resource sharing)。在不一樣機器上運行的應用程序可能會爭搶全局資源(如網絡交換機和共享文件系統)。
維護活動(Maintenance activities)。後臺活動(如分佈式文件系統中的數據重建，BigTable等存儲系統中的按期日誌壓縮，以及垃圾收集語言中的按期垃圾收集)會致使週期性的延遲高峯。
排隊(Queueing)。中間服務器和網絡交換機中的多層隊列放大了這種可能性。優化
同時也是由於當前硬件的趨勢：ui
功率限制(Power limits.)。現代 CPU 被設計成能夠暫時運行在其平均功率之上(英特爾睿頻加速技術)，若是這種活動持續很長時間，以後又會經過節流(throttling)限制發熱；
垃圾收集(Garbage collection)。固態存儲設備提供了很是快的隨機讀取訪問，可是須要按期對大量的數據塊進行垃圾收集，即便是適度的寫入活動，也會使讀取延遲增長 100 倍；
能源管理(Energy management)。許多類型的設備的省電模式能夠節省至關多的能量，但在從非活動模式轉爲活動模式時，會增長額外的延遲。
解決方案
模塊內儘可能下降長尾延遲
**服務分級 && 優先級隊列(Differentiating service classes and
higher-level queuing)**。差別化服務類別能夠用來優先調度用戶正在等待的請求，而不是非交互式請求。保持低級隊列較短，以便更高級別的策略更快生效。
減小隊頭阻塞(Reducing head-of-line blocking)。將須要長時間運行的請求打散成一連串小請求，使其能夠與其它短期任務交錯執行；例如，谷歌的網絡搜索系統使用這種時間分割，以防止大請求影響到大量其它計算成本較低的大量查詢延遲。(隊頭阻塞還有協議和鏈接層面的問題，須要經過使用更新的協議來解決，好比 h1 -> h2 -> h3 的升級思路)
**管理後臺活動和同步中斷(Managing background activities and
synchronized disruption)**。後臺任務可能產生巨大的 CPU、磁盤或網絡負載；例子是面向日誌的存儲系統的日誌壓縮和垃圾收集語言的垃圾收集器活動。能夠結合限流功能，把重量級操做分解成成本較低的操做，並在總體負載較低的時候觸發這些操做(好比半夜)，以減小後臺活動對交互式請求延遲的影響。
請求期間內的一些自適應手段
對衝請求(Hedged requests)。 抑制延遲變化的一個簡單方法是向多個副本發出相同的請求(Go 併發模式中的 or channel)，並使用首先響應的結果。一旦收到第一個結果，客戶端就會取消剩餘的未處理請求。不過直接這麼實現會形成額外的多倍負載。因此須要考慮優化。
一個方法是推遲發送第二個請求，直到第一個請求到達 95 分位數尚未返回。這種方法將額外的負載限制在 5% 左右，同時大大縮短了長尾時間。
捆綁式請求(Tied requests)。不像對衝同樣等待一段時間發送，而是同時發給多個副本，但告訴副本還有其它的服務也在執行這個請求，副本任務處理完以後，會主動請求其它副本取消其正在處理的同一個請求。須要額外的網絡同步。
跨請求的自適應手段
微分區(Micro-partition)。把服務器區分紅不少小分區，好比一臺大服務器分紅 20 個 partition，這樣不管是流量調整或者故障恢復均可以快很是多。以細粒度來調整負載即可以儘可能下降負載不均致使的延遲影響。
選擇性的複製(Selective replication)。爲你檢測到的或預測到的會很熱的分區增長複製因子。而後，負載均衡器能夠幫助分散負載。 谷歌的主要網絡搜索系統採用了這種方法，在多個微分區中對流行和重要的文件進行額外的複製。(就是熱點分區多準備些實例啦，感受應該須要按具體業務去作一些預測)
將慢速機器置於考察期(Put slow machines on probation)。當檢測到一臺慢速機器時，暫時將其排除在操做以外(circuit breaker)。因爲緩慢每每是暫時的，監測什麼時候使受影響的系統從新上線。繼續向這些被排除的服務器發出影子請求，收集它們的延遲統計數據，以便在問題緩解時將它們從新歸入服務中。(這裏就是簡單的熔斷的實現)
一些其它的權衡
考慮「足夠好」的響應(Consider 'good enough' responses)。一旦全部的服務器中有足夠的一部分作出了響應，用戶可能會獲得最好的服務，即獲得輕微的不完整的結果，以換取更好的端到端延遲。(這裏應該是你們常說的降級，若是不完整的結果對於用戶來講已經足夠有用，那不重要的不展現也能夠)
使用金絲雀請求(canary requests)。在具備很是高扇出的系統中可能發生的另外一個問題是，一個特定的請求觸發了未經測試的代碼路徑，致使崩潰或同時在成千上萬的服務器上出現極長的延遲。爲了防止這種相關的崩潰狀況，谷歌的一些 IR 系統採用了一種叫作「金絲雀請求」的技術；根服務器並非一開始就把一個請求發送給成千上萬的葉子服務器，而是先把它發送給一個或兩個葉子服務器。其他的服務器只有在根服務器在合理的時間內從金絲雀那裏獲得成功的響應時纔會被查詢。