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

在審

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

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

2.根據權利要求1所述的一種基于特定索引結構的高效調度算法，其特征在于：所述索引結構和相應的并發調度設計方法如下：

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

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

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

3.根據權利要求2所述的一種基于特定索引結構的高效調度算法，其特征在于：所述事務由若干命令和record組成，將事務集合O_T的全序表示為(T，＜_T)，其中T＝{t_i|i＝1，2…}，＜_T；令表示事務t_i的所有record的集合，表示所有訪問記錄r_j的事務集合。

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

5.根據權利要求2所述的一種基于特定索引結構的高效調度算法，其特征在于：所述事務隊列是為了使調度器提供高效的依賴性檢測和并發執行能力，t_r中的所有事務都組織在FIFO/先進先出隊列中，其作為對應于recordr的布隆過濾器的value部分，記錄r的事務隊列tq_r實際上是一個相對順序的集合因此，對于記錄r，在隊列的末尾插入事務或從事務頭移除事務的時間復雜度為0(1)，事務可能存在于不同的事務隊列中，因為事務通常會操作多個記錄。

6.根據權利要求5所述的一種基于特定索引結構的高效調度算法，其特征在于：所有所述事務隊列可以共同形成一個簡化的依賴圖，其順序與全序一致，但與原始的完全依賴關系圖相比結構簡單得多，由于事務隊列中的所有事務對于記錄都屬于同一等價類，因此不必通過事務內的成對比較顯式地建立完整的全序關系，因此，提出的索引結構可以有效地降低事務依賴關系檢測和調度的開銷。

7.根據權利要求2所述的一種基于特定索引結構的高效調度算法，其特征在于：自由事務：如果表示事務的頂點在依賴圖中沒有入邊，則這個事務可以執行，當工作線程執行完成一個事務時，可以從依賴關系圖中刪除此頂點及其出邊，在算法中，當一個事務t_i被插入到調度器中，如果它是自由的，當且僅當如果事務仍在事務隊列中，則表示該事務可能正在執行或尚未執行，即，未完成。

8.根據權利要求1所述的一種基于特定索引結構的高效調度算法，其特征在于：細粒度鎖：在調度過程中，操作鎖定的粒度是調度器中的一個記錄，當調度程序在上述索引結構上操作事務t_i時，調度程序將只鎖定與事務t_i記錄相對應的那些事務隊列，在hashmap的同一位置/即事務隊列的操作是互斥的，而在不同位置的操作是并發的，因此，可以保證這些操作之間的最大并發性。