物聯(lián)網(wǎng)傳感器和全球定位系統(tǒng)（GPS）智能設(shè)備的海量數(shù)據(jù)流正涌入數(shù)據(jù)庫系統(tǒng)進(jìn)行進(jìn)一步的處理和分析。新數(shù)據(jù)和歷史數(shù)據(jù)的實時檢索能力已被證明是利用這些數(shù)據(jù)流實現(xiàn)智能制造和智能城市實際應(yīng)用的關(guān)鍵。在本文中，我們提出了一個簡單有效的分布式解決方案來實現(xiàn)每秒數(shù)百萬個單元插入和毫秒級的臨時范圍查詢處理。為此，我們提出了一種新的數(shù)據(jù)劃分方案，該方案充分利用了工作負(fù)載的特點，避免了代價高昂的全局?jǐn)?shù)據(jù)合并。另外，為了解決吞吐量瓶頸，我們使用基于模板的索引方法，在相對穩(wěn)定的傳入元組分布上跳過不必要的索引結(jié)構(gòu)調(diào)整。為了實現(xiàn)數(shù)據(jù)的并行插入和查詢處理，我們提出了一種快捷的調(diào)度機制和有效的負(fù)載均衡策略，充分利用計算資源的工作負(fù)載感知方式。在集成工作負(fù)載和實際工作負(fù)載方面，我們的解決方案始終優(yōu)于進(jìn)的開源系統(tǒng)至少一個數(shù)量級。

隨著物聯(lián)網(wǎng)[21]傳感器和位置信息[25]智能設(shè)備產(chǎn)生的高速數(shù)據(jù)的爆炸性增長，人們對高吞吐量數(shù)據(jù)接收和實時數(shù)據(jù)檢索的需求迅速上升。它也是支持智能制造和智能城市應(yīng)用的關(guān)鍵的數(shù)據(jù)處理功能之一，使系統(tǒng)用戶能夠根據(jù)需要快速檢索歷史數(shù)據(jù)和新數(shù)據(jù)。在圖1中，我們給出了一個實時索引和查詢處理的示例應(yīng)用程序，其中分析系統(tǒng)嘗試實時分析網(wǎng)絡(luò)流量，并以非常高的速率在電信公司的骨干網(wǎng)絡(luò)上采集樣本。對流數(shù)據(jù)的典型查詢從指定的IP范圍和給定的時間間隔檢索所有示例數(shù)據(jù)包，以識別網(wǎng)絡(luò)攻擊的潛在風(fēng)險和識別網(wǎng)絡(luò)故障。因此，系統(tǒng)必須支持低響應(yīng)延遲的時間和范圍查詢，同時保證洪水樣本到達(dá)后立即可見。

上述所有應(yīng)用程序都要求系統(tǒng)支持極高的元組插入吞吐量和對指定域上的時間范圍查詢的實時響應(yīng)。表1回顧了我們的目標(biāo)應(yīng)用程序的新系統(tǒng)性能保證。鍵值存儲，如HBase[17]和leveldb[24]，將數(shù)據(jù)元組組織成排序映射，并支持快捷的鍵值范圍查詢。然而，非關(guān)鍵屬性（如時態(tài)查詢）的范圍查詢不是一等公民，因此無法有效執(zhí)行。此外，雖然這些系統(tǒng)使用LSM樹[33]代替?zhèn)鹘y(tǒng)的B+樹來降低更新成本，但更新仍然需要與歷史數(shù)據(jù)相結(jié)合，這導(dǎo)致了大量的數(shù)據(jù)整合成本，限制了插入吞吐量。時間序列數(shù)據(jù)庫，如Druid[47]、gorilla[36]和btrdb[2]，是為實間序列數(shù)據(jù)攝取和具有時間限制的低延遲查詢而設(shè)計的。但是，由于缺少輔助范圍索引，它們無法對非時間屬性提供有效的范圍查詢。

本文提出了一種簡單有效的分布式解決方案waterwheel，它支持每秒100萬元組以上的實時索引和具有鍵和時間范圍約束的低延遲查詢。據(jù)我們所知，這是個同時支持快捷時間和范圍查詢以及極高吞吐量數(shù)據(jù)插入的框架。waterwheel面臨的主要挑戰(zhàn)是在時間域和關(guān)鍵域中快捷地索引數(shù)據(jù)元組，同時在查詢到達(dá)時保持新傳輸元組可見。我們利用實際工作負(fù)載的特點來解決這個問題，即到達(dá)幾乎是有序的，分布演化緩慢。首先，流元組到達(dá)系統(tǒng)的順序與生成它們的順序幾乎相同。例如，在圖1中的動機示例中，樣本包的收集幾乎遵循樣本包時間戳上的順序。其次，傳入元組的分布通常不會隨時間發(fā)生顯著變化?？紤]到各種數(shù)據(jù)源，如圖1中由智能設(shè)備、監(jiān)控攝像機和智能建筑生成的網(wǎng)絡(luò)數(shù)據(jù)包，在IP地址域中樣本數(shù)據(jù)包的分布通常是緩慢和平緩的。

基于以上觀察和直覺，我們重新設(shè)計了海量數(shù)據(jù)流的實時索引和查詢處理架構(gòu)。水車背后的關(guān)鍵思想是利用實際工作負(fù)載的特點，通過物理分區(qū)，將輸入的數(shù)據(jù)作為獨立的數(shù)據(jù)塊，在不同的時間和關(guān)鍵范圍內(nèi)進(jìn)行維護。在每個數(shù)據(jù)塊中，建立模板B+樹索引結(jié)構(gòu)，支持有效的元組插入和數(shù)據(jù)檢索。通過模板的使用，B+樹不需要調(diào)整內(nèi)部節(jié)點的結(jié)構(gòu)，節(jié)省了索引維護成本，獲得了較高的性能。這種簡單的兩層數(shù)據(jù)索引方案使系統(tǒng)能夠根據(jù)不同的工作負(fù)載輕松地重新擴展。為了提高系統(tǒng)的性能和魯棒性，設(shè)計了模板更新方法和動態(tài)密鑰分配機制，使系統(tǒng)適應(yīng)動態(tài)工作負(fù)載。為了充分利用查詢處理中的計算資源，提出了一種同時保持負(fù)載平衡和數(shù)據(jù)局部性的查詢調(diào)度算法?？偟膩碚f，與現(xiàn)有的開源解決方案相比，waterwheel的性能有了顯著的提高。

1） 我們提出了一個通用的兩層索引架構(gòu)，它可以每秒插入數(shù)百萬個單元，并以毫秒為單位查詢密鑰范圍。

2） 設(shè)計了一種增強的基于模板的B+樹，大大降低了索引維護開銷，實現(xiàn)了高并發(fā)性。

3） 為了充分利用集群中的計算資源，設(shè)計了分布式查詢調(diào)度算法和負(fù)載均衡機制。

4） 與文獻(xiàn)中進(jìn)的解決方案相比，我們使用合成和實際工作負(fù)載來評估原型系統(tǒng)，并顯示出顯著的性能改進(jìn)。