背景介紹
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