[發明專利]一種基于特定索引結構的高效調度算法

在審

• 申請號: 202010979603.6
• 申請日: 2020-09-17
• 公開（公告）號: CN112181617A
• 公開（公告）日: 2021-01-05
• 發明（設計）人: 吳剛;趙國棟;宋一東;楊靜磊;崔鍇倩;李雪玉;喬百友;韓東紅;王波濤;劉輝林
• 申請（專利權）人: 東北大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/54
• 代理公司: 北京君泊知識產權代理有限公司 11496
• 代理人: 李丹

本發明公開了一種基于特定索引結構的高效調度算法，由一個特殊的布隆過濾器和每個過濾器元素對應的事務隊列組成，所述布隆過濾器和事務隊列組成特殊的索引結構，其分別進行高效的依賴檢測和保留必要的依賴信息，通過布隆過濾器，在一定時間內檢測出事務之間的依賴關系，事務隊列具有保持總順序關系和簡化依賴關系圖的特性，借助于索引結構，調度器支持記錄粒度鎖，從而支持并發事務調度操作。本發明提出的方法高效的解決了依賴圖調度中由于基于兩兩比較而調度開銷過大導致的性能損失問題，保證了在各種依賴率工作負載下的并行執行能力，正式證明了副本調度與其他調度安全的一致性，調度器比對比方法具有更高的效率、可擴展性和健壯性。

技術領域

本發明涉及狀態機復制技術領域，尤其涉及一種基于特定索引結構的高效調度算法。

背景技術

狀態機復制(SMR)是一種設計容錯服務的基本方法。然而，它對事務確定性執行的要求常常導致副本成為單線程模型，不能完全利用當今處理器的多核處理能力。因此，并行SMR成為近年來研究的熱點。其基本思想是，獨立事務可以并行執行，而相互依賴的事務必須以相對順序執行，以確保副本之間的一致性。基于依賴檢測的并行SMR方法要么是成對比較要么是batch比較，它們不能同時保證高效的依賴檢測的和事務的并行執行能力。除此之外，這些方法的調度器的執行過程也不能并行執行，進一步增加了主要由依賴檢測帶來的調度開銷，為了進一步降低調度開銷同時保證事務的并行執行程度，為此，提出一種基于特定索引結構的高效調度算法。

發明內容

本發明提出的一種基于特定索引結構的高效調度算法，解決了上述背景技術中提出的問題。

為了實現上述目的，本發明采用了如下技術方案：

一種基于特定索引結構的高效調度算法，由一個特殊的布隆過濾器和每個過濾器元素對應的事務隊列組成，所述布隆過濾器和事務隊列組成特殊的索引結構，其分別進行高效的依賴檢測和保留必要的依賴信息，通過布隆過濾器，在一定時間內檢測出事務之間的依賴關系，事務隊列具有保持總順序關系和簡化依賴關系圖的特性，借助于索引結構，調度器支持記錄粒度鎖，從而支持并發事務調度操作。

優選的，所述索引結構和相應的并發調度設計方法如下：

索引結構的主要部分是由單個hashmap構造的簡化版的布隆過濾器，hashmap的每個鍵表示事務訪問的一條記錄/record，在不實際構造和遍歷依賴關圖的情況下，當事務被映射到布隆過濾器同一個位置時，確定事務之間的依賴關系；

hashmap的每個鍵對應的值/value是一個FIFO隊列，其中包含訪問該鍵記錄的所有事務，hashmap的所有事務隊列頭部的事務都可以并行執行；

采用特殊的索引結構，非常自然的使調度器支持record粒度鎖的并發調度過程，并可以同時保證調度的安全性和正確性。

優選的，所述事務由若干命令和record組成，將事務集合O_T的全序表示為(T,_T)，其中T＝{t_i|i＝1,2…},_T；令表示事務t_i的所有record的集合，表示所有訪問記錄r_j的事務集合。

優選的，所述布隆過濾器是由單個hashmap構造的，盡管布隆過濾器通常由多個散列函數組成，但這里唯一使用了hashmap中的hash函數，原因是的布隆過濾器不僅用于檢測依賴性，還用于根據訪問的記錄對事務隊列進行索引,其通過讓record作為要散列的key，讓所有事務作為value來實現的，因此，對于事務t來說，查找與其record有關的所有依賴事務的時間復雜度為0(1)。