664      阿裏雲  技術社區[雲棲]

Sparrow: 適用於細粒度tasks低延遲調度的去中心化無狀態分布式調度器

背景介紹

Sparrow的論文收錄在SOSP 2013，在網上還可以找到一份作者的talk ppt，值得一提的是作者是位PPMM。她之前發表過一篇The Case for Tiny Tasks in Compute Clusters，這篇文章我沒有仔細看過，但是當時在看mesos粗細粒度模式的時候，組裏有討論過這篇論文。再結合她的github上的項目，發現她和AMP實驗室裏Mesos，spark等項目，在研究方向和合作上還是有很多淵源的。透過Sparrow，結合對Mesos、YARN的一些了解，可以在理論和實際項目中獲得更多一些關於資源調度的東西。

適用場景

Sparrow是一個去中心化(分散)的無狀態的分布式調度者，為細粒度task提供低延遲的調度。在一個由次秒級的tasks組成的workload裏，調度器必須每秒為百萬tasks提供毫秒級別延遲的調度決策，同時容忍調度失敗。Sparrow主要借助Batch Sampling + Late Binding + Constraints來達到較好的效果。下麵會具體介紹Batch Sampling 和 Late Binding，而Constraints是指用戶可以對每個job進行一些約束和設定，比如所有tasks必須跑在有GPU的worker上，也就是在選擇worker的時候增加一些條件約束。Constraints可能會讓用戶在使用Sparrow的時候保持更高的好感，而真正的低延遲調度的提速應該還是取決於Batch Sampling + Late Binding的策略。

基礎

sparrow假設每個worker針對每個framework已經有一個long-runing的executor進程，最基礎的是random，將Job的tasks往隨機選擇的兩個worker上分配，worker自身維護了一個或多個queue(當對用戶產生隔離或對優先級有要求的時候會維護多個queue)。

這種最基礎的分配task的方法出自The Power of Two Choices in Randomized Load Balancing，讓調度器探測兩個隨機選擇的worker，把task分配到queue較短(僅考慮了已存在tasks數目)的worker上。Sparrow基於The Power of Two Choices in Randomized Load Balancing的思想，提出了自己的三個改進的方法，並且給出了一些測試數據，說明了每種特性帶來的效果提升。

Sparrow基於random的分配方式，進行的第一種改進是Per-task sampling，即針對每個task都進行一次random操作，由scheduler發送probe(探測器，一個輕量級RPC)到worker上，然後選擇一個隊列比較短的worker分配task。之後的task重新進行random的work選擇。

Batch Sampling

上麵的分配方式會讓尾部的tasks等待較長的時間，Batch Sampling改進了之前為task單獨分配random worker的方式，讓scheduler同時為一個job的m個tasks探測m*d個workers(d>1)，為tasks一起監控很多個worker。下圖即scheduler為兩個task同時探測四個worker。批量取樣的性能不會隨著job並行化的增加而降級。

Late Binding

之前random模式裏提到過，scheduler對worker的選擇是從已進行探測的備選worker裏選擇一個queue長度最短的worker放置新的task，但是有可能造成較長的等待時間，因為沒有考慮到已經排隊的tasks的執行時間。如果task直接被分配在某個worker上排隊，會造成較長的等待時間。

延遲綁定結合上麵的批量采樣的方式的話，就可以同時監控d*m個worker，隻要worker queue空了，就可以把task放置過去進行執行。下圖中，承接上麵的圖示，Scheduler選擇了四個worker進行batch sampling，當檢測到第一個worker隊列空了之後，就可以真正將job的兩個tasks中的一個放到該worker上執行了，而另一個task繼續由scheduler對四個worker進行監控。

在性能方麵，下圖展示了各個方法帶來的延遲對比，其中黑色的虛線是假設調度器對於worker和task無所不知的情況下可以做出的最優調度，最靠近最優性能的是batch + Late Binding的曲線，從左往右對應的是上麵的一個個圖示，也證明了Sparrow的改進在百萬級別細粒度tasks低延遲調度方麵的進步。

Sparrow & Spark

為了證明Sparrow的可用性，作者為Spark加了個sparrow調度插件，將spark的每個stage提交成為一個Sparrow Job，提交給sparrow的schedulers。但是Sparrow由於是無狀態的，所以framework使用的scheduler如果fail了，需要自己檢測到並且去連接備用scheduler。在測試中client端獲得一個scheduler列表，通過發送心跳的方式檢測正在使用的scheduler有沒有fail，如果fail了，那應對措施也需要針對使用場景而設置，若放棄這次job重新在別的sheduler上啟動重新分配tasks去執行的話，要保證冪等。Sparrow同時也不會管worker的fail事件。項目分支地址。

我感覺Sparrow在地位上，比較像Spark LocalScheduler內的LocalTaskSetManager，但是大於它，Sparrow自己有一些schedulers。Sparrow假設每個worker針對每個framework已經有一個long-runing的executor進程，而這個executor可以是跑在mesos上的一個executor process，也可以是spark standalone模式下在各個slave上起的long-running進程，Sparrow做的事情是我給你一個schedulers列表，你用我的scheduler來處理你的job裏的tasks怎麼調度和分發，具體分發完執行的事情和worker fail了與Sparrow沒有關係。

下麵圖中，在Spark Standalone模式下，Spark不借助於Mesos或者YARN這樣的第三方資源調度係統，而是使用自己的調度模塊。Spark自己的調度模塊裏有FIFO pool和FAIR pool，如果換成Sparrow的話，tasks的調度不再是簡單的先進先出(FAIR pool內部仍然是先進先出的)，而應該是上麵的Batch sampling + lazy binding + constraints的方式來調度到slave上。

(下圖是我在閱讀Spark源碼時畫的一張大圖的一部分，右下角ClusterScheduler部分接的是mesos調度模塊，在SchedulerBackend處可以接粗粒度或者細粒度的mesos scheduler backend，左下方使用的是自己的調度模塊LocalScheduler，在0.8裏除了之前的FIFO pool外，也新加入了FAIR pool，在我之前的這篇博文裏也介紹過。)

類似地，Sparrow也實現了一個優先級隊列，還實現了不同user之間的queue隔離性，這種情況下每個worker就維護了多個queue。

(全文完)

------------------------我是補充分割線------------------------

Sparrow vs Mesos/YARN

Sparrow通過自己的scheduler，讓job的tasks能在適合workers上得到低延遲的調度，適合細粒度大量tasks的低延遲調度。和mesos、yarn等涉及到資源分配的調度器不一樣。我理解Sparrow是mesos/yarn之上的task分發，分發到的workers是實際已經啟動了long-running executor並得到資源了的slaves

最後更新：2017-04-03 14:54:36

  上一篇： CentOS-6.4-x86_64-minimal 最小化安裝之後開機服務的配置建議

  下一篇： android 自定義Dialog背景透明及顯示位置設置