自從有了計算機以來，算力的角逐就已經開始，從1942 年 Atanasoff-Berry Computer（ABC）第一臺超級計算機出現，幾十年來計算在規模、性能以及計算的通用性等各個方面都有了突飛猛進的發展。從企業內部的單機系統，私有云、公有云，算力從各個分散的點逐漸整合為規格更為統一的數據中心，同時分佈式計算也逐步發展為解決如何處理互聯網產生的大量數據的重要途徑。
公有云等雲計算基礎設施和服務出現以後，對於有計算和存儲需求的用戶來說，越來越不關心底層網絡，服務器等硬件基礎設施，只需要根據使用雲計算服務，按使用量或者是使用時長付費，不斷降低用戶的使用門檻，同時集中統一化的雲服務為用戶提供了更加穩定的環境。在上雲趨勢之下，越來越多的私有云和中小企業用戶逐漸把服務遷移到公有云，公有云成為企業級 OS 的趨勢。通過雲上的各種服務，對於初創公司相比自建私有云，產品研發週期大大縮短，可能直接影響著用戶商業化週期。
從數據中心出現開始，私有云到公有云，數據和計算逐漸越來越往中心靠攏，雲服務逐漸從以人為中心設計的雲（例如：web service ）發展到下一個時代，設計以機器為中心雲（如：邊緣計算、IOT PAAS），以支持更大規模計算和調度。和公有云互補的是邊緣計算，邊緣計算在網關層面做簡單處理之後，大部分數據還是會迴歸中心的公有云，是中心雲的擴展，思想為把中心雲服務部分計算推到邊緣，網關節點一般為更靠近某個區域的數據中心服務器。
在大量智能設備出現和大量空閒算力的今天，Gravity 把空閒算力整合成標準化的計算單元VCU，通過 P2P 的 NFV 網絡，把異構的算力組成虛擬數據中心，通過一個去中心化的調度網絡在異構的節點（包括：手機、智能設備、礦機、PC、路由器等）組成一個更為分散和具有資源和作業調度能力的邊緣雲基礎設施，把邊緣設備組成一個具有大數據計算和存儲能力的分佈式計算網絡，把數據中心的計算拓展到邊緣雲，也是現有云計算的強有力互補。
在整合閒置算力提供大數據計算的過程中，
我們面臨著幾大挑戰
- 計算節點平臺，OS 和計算能力異構
- 節點分散在距離用戶較近的位置，沒有數據中心級別的網絡環境
- 未來的節點規模大，百萬級
- 動態化的節點拓撲（相對數據中心節點拓撲來說）
在業界也出現了很多 benchmark 來測評相關指標。比如 Sort Benchmark 中的 TeraByte Sort，主要面向大數據領域，曾經是巨頭們爭相追逐的指標。這種評測是典型考驗調度能力的方法，優異的調度能力會在指定數據和算法任務中勝出。我們從現在主流的計算和資源調度進行一個對比，來說明我們是怎麼解決以上問題的。
常見的調度模型分為：
來源：Omega: flexible, scalable schedulers for large compute clusters論文
Monolithic 統一調度架構
單一的調度器通過集群狀態信息，負責統一的資源和任務的調度，許多調度系統最初被設計為這種模式，這種架構一致性強，擴展性較差，在集群規模增大時，可用性和處理能力可能會隨之下降。
Two-Level 兩級調度
通過資源動態劃分，使用中央協調器來確定每個子集群可以分配的資源，每個子調度器不具備全局資源視圖，可能造成資源使用量不均衡等問題。代表性的兩級調度有 Mesos 和 Yarn (有爭議）
Shared State 共享狀態調度
調度系統同時存在多個調度器，調度器共享全局資源視圖，通過樂觀鎖機制，調度衝突概率大，比如 Borg 和 Omega.
<strong>
主流開源調度器的
橫向對比
Yarn
Yarn 是 Hadoop 裡的調度系統，主要面向大數據計算。由 Resource Manager、NodeManager、Container 和 Application Master 組成，是一個典型的多級調度。來源於早期的原生 MapReduce 任務的調度，目前可以支持 Spark、Flink 等運行在 Hadoop 集群。
Yarn 的 NodeManager 複雜宿主機管理，其中的 Container 主要是進程級的管理，運行MapReduce 任務時會啟動 TaskManager 和 TaskExector 進程。
Yarn 啟動任務時會由 Resource Manager 指定一個 Node 啟動 Application Master,成為二級管理者，來負責子作業運行管理，比如 MapReduce 的 JobManager 或者 Spark 的 Master.
Yarn 默認使用公平調度策略，用隊列形式管理任務，隊列可以嵌套，也可以配置優先級。總體來說 Yarn 適合大數據場景，管理迭代計算比較有優勢。
通過 federation 支持節點量級 10k~100k（理論值）
圖片來源：https://hadoop.apache.org/
Mesos
通過將機器、CPU、內存和存儲等其他計算資源抽象出來，agent 向 master 彙報節點資源情況， Master 根據策略決定將 Resource Office 給不同的調度框架。
可以採用一主多備，通過 Zookeeper 來做分佈式協調，節點通過 Slave 的方式加入到集群中，支持大約 10K 級別節點規模。
圖片來源：http://mesos.apache.org/
Kubenetes
通過 Minon 節點彙報節點資源狀態到 Master, Controller Manager 負責管理 Cluster 的各種資源，Scheduler 通過 Cluster 的拓撲結構進行 Pod 調度，無狀態 ApiServer 則 負責對外進行調用理論支持 5K 節點規模。
圖片來源：https://kubernetes.io/
上述的調度系統都是假設節點都在數據中心，網絡和設備可用性很高，而且都是 G 以上網絡互連且能 IP 直通的環境，節點拓撲相對靜態，擴展性都是在 10K 規模的節點集群，不能滿足我們邊緣雲計算的業務背景。
而 Gravity 需要解決節點平臺和 OS 算力異構的問題（比如：PC、手機、礦機、智能盒子等），節點動態加入動態擴容和離開（共享設備隨時可能加入和離開網絡），由於邊緣和閒散算力計算資源都相對較弱，需要滿足海量設備的資源和作業調度。
以下是 Gravity 的實現方案及相關產品：
Gravity PMR (PMR)
PMR 是我們目前已經實現，並且提供公測的調度，面向 MapReduce 大數據處理任務，適合迭代的批量計算。由於 Gravity 是利用公網的共享設備組成計算網絡，網絡和設備穩定性以及異構情況都會很複雜，支持的單集群節點規模也會提升兩個數量級。
Gravity MapReduce 的實現方案
1.節點比較分散，一般家用 PC 或者手機網絡都是在路由器 NAT 之後，沒有對外固定的公網 IP，同時數據中心之外的閒置或邊緣設備數量很大
我們通過節點間的 P2P 網絡，對於在同一個局域網內的節點通過廣播互相通信，對於不在同一個網絡中的其他對等點通過 NAT 穿透，構建一個去中心化的計算網絡，降低了通信成本，不需要使用固定的公網 IP，通過節點 id 唯一標示一個節點，節點網絡統一，局部是自治網絡，通過平衡策略，每一個點不會接收大量節點的連入，橫向擴展能力強。
2.動態化的節點拓撲和自平衡網絡
節點啟動時，節點根據 VRF 和 Bully 選舉算法，會有部分節點自動競選成為作業調度節點，其他節點成為作業執行節點。
首先網絡中所有 Node 都具備任務執行和調度能力，所有節點都是普通的 Node 角色，在啟動過程中，自動轉化為 Idle，在 Idle 狀態下，根據 VRF 和 Bully 選舉算法，在一個隨機超時之後，手中持有大部分選票的節點勝出，進入 GP-Mid 狀態。此階段是一箇中間狀態，節點只具有參與第二輪選舉的權利，其餘節點回到 Node 狀態，第二輪在 GP-Mid 選中節點中，通過 VRF 生成的選票，通過 Bully 選舉，選出滿足網絡初始狀態的所有 Ggroup，其餘節點進入 Gant 狀態。所有 Group 狀態的節點，在當選之後，會受到隨機選擇的多個備選 Ggroup 檢測，同步狀態信息。當 Group 宕機，所有備選會重新選舉，並接管狀態。在新的節點加入過程中，如果沒有找到相應的 Group 節點接受，則和其他沒有被接受的節點進入選舉狀態，最終產生新的 Group 節點。
網絡自平衡策略，紅色為 Job 調度節點，藍色為作業 Task 執行節點，當 Job 提交較多，用戶等待時間較長時，所有 Job 調度器會通過協調者從 Task 執行節點中選舉出新的 Job 調度節點。當Job 減少 Task 較多的情況下，超過一定時間沒有接收到 Job 的調度節點，會自動轉換為 Task執行節點。
3.工作量驗證和容錯機制
其中紅色節點為當前 Job 分發節點，藍色節點為當前 Job 執行 task 節點，黃色節點為紅色節點的檢測者，黃色節點之間互相不知道彼此的作業信息，他們並行從紅色節點獲取作業的狀態彙報，當檢測到當前 Job 調度器宕機或者停止響應時，黃色節點之間通過選舉模塊，選出接管者和檢測者。
藍色節點彼此之間不知道互相的狀態信息，如果檢測者或者 Job 調度器發現其中部分節點作業心跳異常或者執行速度慢於其他藍色節點很多，則會推遲執行，選擇一個藍色節點並執行此 Task ,最後誰最快返回誰獲得計算證明。
4.解決設備和節點計算能力異構的問題
我們通過一個標準化的 benchmark 測試，評估不同設備的算力級別，根據我們邏輯劃分的最小計算單元 VCU，來預估一個設備所能併發接收的 Task 數量和每個 Task 所能執行的數據量。用戶可以通過參數修改併發量，但是在常規情況下不建議用戶修改，修改可能導致節點負載過大等，在 task 執行過程中相比其他節點慢，導致推測執行，拿不到響應的計算激勵。
關鍵點：
在我們整個網絡中，所有節點都為全功能節點，在通過相應的任務負載的情況下，網絡中的調度器數量和計算節點是動態調整的（適者生存），沒有一個全局中心節點，可以水平擴展。
網絡中所有調度器通過 DHT 方式尋址，每個調度器負責一定數量的計算節點，並且能達到跨調度器的資源請求。同時所有調度節點都受多個備用調度節點監測（局部共識）。
任務計算節點如果存在異常，比如併發設置不合理等，會通過推測執行，選擇其他節點同時計算，先完成的將取代慢的（弱肉強食）。
要解決邊緣雲計算的問題，利用閒置算力組成計算網絡，現有的數據中心級別的作業和資源調度是很難解決大規模，動態節點拓撲，網絡節點異構的問題，以上就是我們的一些思考和實踐。基於 Gravity 作業調度之上，已經支持了 MapReduce 作業調度，跨手機、PC、盒子等異構分散設備的計算網絡，歡迎大家關注公眾號參與測試。
閱讀更多 區塊鏈技術謝大炮 的文章
