配電網監測數據索引集群的分布緩存方法

屈志堅，吳廣龍，帥誠鵬，梁家敏

（1.華東交通大學軌道交通基礎設施性能監測與保障國家重點實驗室，南昌 330013；2.華東交通大學電氣與自動化工程學院，南昌 330013）

近年來智能電網建設進程穩步推進，太陽能、風電和電動汽車充電樁的接入使配電網規模不斷增加，配電網監測需求提高，導致配電網設備的狀態采樣點和監測傳感器的數量也大幅增加；加上設備采樣頻率的提升，使得配電網監控系統采集的數據急劇增長，數據體量已超過TB級[1?3]，遠遠超過了關系型數據庫TB級容量限制。配電網監測數據的增加不僅增大了系統的維護難度，而且導致產生的延遲越來越大，配電網監控系統響應時間過長可能導致關鍵故障信息的遲報甚至界面卡頓。

配電網監測數據的急劇增加，對配電網監測數據的快速處理提出了要求，如何高效處理配電網監測數據從而實現海量數據的監測和電能質量監控成為亟待解決的問題。目前，相關學者在海量數據的高效存取研究方向已經取得了一定的研究成果，文獻[4]研究的擴展關系型數據庫方法將數據存儲在不同主機的磁盤，但關系型數據庫的存儲空間有限，需要通過增加主機數量來增加數據庫容量；文獻[5]研究的基于內存計算的內存數據庫方法能提高數據的處理性能，但內存數據庫存在內存容量不足、輸入輸出壓力大、緩存命中率低和數據安全性較差等問題；文獻[6]提出基于Hadoop 架構存儲反向傳播BP（back propagation）神經網絡的短期負荷預測數據的方法；文獻[7]提出基于Hadoop 分布式文件系統HDFS（hadoop distributed file system）的數據存儲優化技術；文獻[8]提出一種將數據自動生成非結構化查詢語言NoSQL（not only structured query language）存儲結構的平臺。

NoSQL以HBase[9]分布式列數據庫為主要代表，HBase 分布式鍵值對數據庫基于主鍵的查詢很快，但基于非主鍵的查詢需要全表掃描，對系統資源的耗費較大。針對這一問題，文獻[10?11]基于MapRe?duce 進行研究，存儲數據時生成元數據，查詢時讀取元數據構造查詢樹；文獻[12]提出基于協處理器的HBase索引構建方案，通過協處理器構建二級索引并根據HBase 表的數據更新自動更新索引并持久化索引；文獻[13]驗證了引入緩存技術能有效提升大數據集群處理性能；文獻[14]提出在數據庫系統中基于低延遲和高帶寬的內存建立緩存以提升查詢速度并減輕底層磁盤壓力；文獻[15]設計出一種基于日志結構合并樹LSM?Tree（log structured merge?Tree）的分布式索引方案，該方案采用讀寫分離和批量更新的方法更新索引數據；文獻[16]描述了瞬態數據緩存策略性能的基本限制，測試了瞬態數據使用傳統緩存策略的性能，并提出一種新的緩存策略，該策略同時使用流行度和剩余生命期（數據變得冗余之前剩余的時間）進行緩存決策，測試顯示新的緩存策略優于傳統的緩存策略；文獻[17]對數據設計了特殊的緩存結構，有效提高了搜索引擎的查詢性能。

海量數據的主流處理方法為NoSQL索引集群，本文將監測數據存儲在NoSQL分布式索引集群中，通過緩存技術將出現頻繁的數據存儲在緩存中，查詢時可以直接從緩存中獲取結果。但一方面原有的熱數據鏈表HDL（hot data linked?list）緩存方法是將數據存儲在鏈表中，當緩存空間占滿時，需要通過更新鏈表中存儲的數據實現緩存記錄的更新；當緩存記錄更新頻繁時會使鏈表節點頻繁移動，內存消耗較大。另一方面，索引集群啟動初期緩存系統中沒有存儲緩存記錄，使索引系統啟動初期難以命中緩存，無法充分發揮緩存技術的優勢；若能在索引系統啟動初期將熱點數據存入緩存系統，可以提高熱點數據的查詢速度，加快監控系統的響應速度。

針對上述問題，本文提出一種配電網監測數據索引集群的分布緩存方法。首先，構建配電網監測數據的倒排索引結構，設計一種熱點數據部分鏈表HDPL（hot data part linked?list）緩存方法，為緩存記錄添加時間戳，通過選取部分數據存入鏈表的方式減少鏈表的長度，根據緩存記錄的訪問時間間隔（HDPL值）大小淘汰緩存記錄，降低內存消耗，提高緩存淘汰效率；然后，設計合理數目的預熱查詢，將熱點數據存入緩存實現索引集群的熱啟動，加快集群的響應速度。最后，以工程數據為測試算例，驗證了所提方法的有效性。

1 配電網海量監測數據的處理

1.1 數據庫存儲

關系型數據庫是在關系型數據模型的基礎上，借助集合代數的數學方法處理數據的數據庫。關系型數據庫通過行和列的形式存儲數據，在關系型數據庫中，實體之間的聯系由單一的結構類型來表示，這種邏輯結構是二維表，多個二維表構成了關系型數據庫。笛卡爾積可以表示成一個二維表。一組具有相同類型的值的集合稱為域，給定一組域{E1,E2,???,Em} ，這些域中可以有相同的部分，則該域的笛卡爾積可表示為

式中，(e1,e2,???,em)為域的每個元素，稱為一個m元組，元素中的每一個值ei稱作一個分量。笛卡爾積可以表示成一個二維表，表中每列對應一個域，每行對應一個元素。

由于關系型數據庫的原子性、一致性、隔離性和持久性，數據一致性高，使關系型數據庫廣泛應用于輸入輸出IO（Input Output）讀寫密集型系統。但是關系型數據庫的容量主要通過增加服務器上的磁盤空間來擴展，隨著數據的增長，需要不斷增加硬盤空間，并且需要更快的機器來運行，具有一定的局限性。

綜上，本文基于NoSQL數據庫搭建配電網監測數據索引集群，將配電網監測數據結構改變為倒排索引；引入緩存技術加快查詢速度，針對原緩存方法效率低的問題提出HDPL 緩存方法來提高緩存效率；設計預熱查詢結構提高索引系統啟動初期的緩存命中概率，實現更高效率的查詢。具體數據處理流程如圖1所示。

圖1 配電網監控系統的數據處理Fig.1 Data processing of distribution network monitoring system

1.2 配電網海量監測數據的倒排索引集群

本文搭建倒排索引集群處理配電網海量監測數據。為了掌握供電設備的狀態，需要收集各站所設備的運行參數信息。由于傳感器數量的增加及測控終端采樣頻率的增加，導致配電網數據中心的監測數據急劇增加。傳感器采集的數據主要包括現場環境的測量參數和現場設備的狀態數據，采集的數據通過光纖通道傳輸至配電網數據中心。配電網數據中心由應用服務器、存儲設備、網絡設備等構成。在數據庫集群中將數據改變為倒排索引結構，監測數據的倒排索引結構如圖2所示。

圖2 監測數據的倒排索引結構Fig.2 Inverted index structure of monitoring data

運行狀態數據的屬性包括站所號、采樣名、采樣值、采樣時間戳等。通過映射的方式將所有數據組成的多個文檔映射為倒排索引結構，左邊為原始文檔，右邊為映射后的倒排索引結構。如站所223出現位置為id：1_station字段。

1.3 索引集群的緩存查詢

考慮到監測數據的高重復度，引入緩存能夠避免對高頻數據重復查詢從而增加查詢的工作效率。當緩存空間占滿時，緩存系統按照HDL更新緩存記錄。該方法通過鏈表結構存儲緩存記錄，具體淘汰方法如圖3所示。

圖3 HDL 淘汰方法Fig.3 HDL elimination method

當第1 次查詢station：站所236 時，緩存空間中存在站所236 的記錄，則命中緩存；此時將進行緩存記錄的更新，將查詢結果站所236 存入鏈表的表頭位置，鏈表內站所223 記錄需后移一位，完成緩存記錄的更新。當執行第2 次查詢時，查analog?name：遙測16387，未命中緩存，查詢結果存入緩存空間；此時緩存空間已占滿，依照HDL 方法更新緩存，接著將第2 次查詢結果存入鏈表表頭，鏈表內的緩存記錄依次后移一位。第3 次查詢未命中緩存，同樣按照上述過程更新緩存記錄。

在HDL方法更新緩存記錄時，將鏈表內所有的緩存記錄更新，若緩存記錄更新頻繁，該操作會占用大量集群資源，影響集群的查詢響應時間。

1.4 HDPL 分布緩存方法

針對原有的HDL 緩存方法更新緩存時需要將鏈表結構中的緩存數據移動，從而出現緩存更新效率低的問題。本文設計了一種HDPL 方法管理緩存，實現更高效的緩存淘汰。具體實現過程如下。

（1）查詢結果存入緩存中時會被添加時間戳，假如該查詢記錄存入緩存后一直未被命中，則該緩存記錄的時間戳始終不變；假如后續查詢命中該緩存，則更新該緩存記錄的時間戳為當前時間節點t。隨機選取一定的緩存記錄，根據當前時間節點t和緩存記錄的時間戳ti計算第i個預熱查詢選取的緩存記錄訪問時間間隔Δt為

式中，l為預熱查詢的總次數。

（2）根據訪問時間間隔計算緩存記錄的HDPL值crHDPL為

crHDPL=t?Δt，即

（3）將式（3）化簡后可得

crHDPL=ti

緩存記錄的時間戳越小，則緩存記錄的HDPL值越小。根據HDPL 值的大小將選取的緩存記錄依次存入鏈表結構，當緩存空間占滿需要淘汰緩存記錄時，將鏈表中HDPL 值最小的緩存記錄淘汰，同時將新的查詢結果存入緩存空間。之后每次淘汰緩存記錄時，隨機從緩存空間中選取5條緩存記錄，計算緩存記錄的HDPL 值，只要選舉的緩存記錄比鏈表中的任意一條緩存記錄的HDPL 值小，則根據HDPL 值的大小將緩存記錄插入到鏈表的適當位置，將鏈表表尾的HDPL 值最小的緩存記錄淘汰，同時將新的查詢結果存入緩存空間；若選舉的緩存記錄比鏈表中的任意一條緩存記錄的HDPL值都大，則直接將鏈表表尾的HDPL 值最小的緩存記錄淘汰，同時將新的查詢結果存入緩存空間，完成緩存淘汰。

HDPL緩存方法只針對選取的緩存記錄執行緩存淘汰，通過淘汰局部最小HDPL 值的緩存記錄代替淘汰全局HDPL 值最小的緩存記錄。相較于原本的HDL 方法，無需維護一個很長的鏈表，更新緩存記錄時無需將鏈表中所有的緩存記錄移位，降低了內存的操作復雜度，提升了緩存性能。

2 熱點數據的預熱查詢

2.1 集群的數據分布策略及分布式查詢

在索引集群中，數據以文檔的方式存儲，文檔存儲在集群分片中，分片在不同的集群節點中。集群使用哈希算法對文檔唯一標識ID（identification）字段的散列值進行計算，根據計算得到的唯一ID字段的散列值將文檔分配至對應的分片，使得每個分片上的文檔數量大致均衡。

執行分布式查詢時，客戶端向集群的任意節點發送查詢請求，接收到查詢請求的節點充當查詢控制器。查詢控制器獲取集群其他節點的身份，構造分布式查詢的子查詢并將子查詢任務分發給其他分片的副本。副本是指當集群的一個分片有2 個以上節點時，1 個節點通過選舉成為該分片的領導者，該分片的其他節點成為副本。其他分片的副本完成子查詢任務后將子查詢結果發送給查詢控制器，查詢控制器匯總所有子查詢結果并將最終的查詢結果返回給客戶端完成分布式查詢。

2.2 集群的分布式查詢時間模型

設集群節點接收客戶端發送查詢請求后，構造分布式查詢的子查詢并將子查詢任務分發給其他分片的副本時間為tr。

先考慮查詢未命中緩存。執行查詢時，由于各節點性能差異的影響，不同分片的查詢時間會有差異，當最慢子查詢和最快子查詢完成查詢的時間段內沒有查詢結果通過網絡傳輸至查詢控制器時，即等待所有子查詢完成后，再依次將數據通過網絡傳輸至查詢控制器進行總查詢結果的構建，此時得到索引集群的最大查詢時間Tmax可表示為

式中：tr為子查詢任務分發r個查詢結果的副本時間；n為索引集群的分片數；tq(k)為不同分片k各自完成子查詢的時間；v為不同分片傳輸查詢結果至查詢控制器的速度；r為所有分片傳輸的總查詢結果數；tε為查詢控制器匯總各分片的查詢結果并形成最終查詢結果的時間；ts為集群將查詢結果返回給客戶端的時間。

當最慢子查詢和最快子查詢完成查詢的時間段內都有查詢結果通過網絡傳輸至查詢控制器時，此時索引集群的查詢時間為最小值，即

將式（5）化簡后可得

由于不同子查詢完成的過程具有隨機性，在子查詢執行過程中，不一定所有時間都進行查詢結果的網絡傳輸，此處需要引入調節因子α(0 ～1)，用來描述網絡傳輸的利用率，引入該調節因子后，得到查詢時間表達式為

經過上述分析可知，在未命中緩存的情況下，索引集群的查詢時間Tc取值為[]Tmin,Tmax區間的一個隨機值。為了便于后續比較，將式（7）改寫為

當查詢命中緩存時，索引集群從緩存中獲取數據。設索引集群從緩存中獲取數據的時間為tqh，此時索引集群的查詢時間Th為

2.3 預熱查詢結構的設計

索引集群啟動初期，緩存未存儲緩存記錄，導致系統啟動初期緩存命中率低。本文設計了一種預熱查詢結構，解決索引集群啟動初期緩存命中率低的問題。在索引集群啟動初期，設置熱點數據的預熱查詢，將熱點數據提前加載至索引集群緩存中。通過搜索管理器統計查詢數據的熱度排名，對排名較高的數據設計預熱查詢。

在初始階段，緩存空間存在大量空閑，設置預熱查詢的數據可以直接存入緩存空間，隨著查詢結果逐步存入緩存，緩存空間被逐步占滿。當緩存占滿時，需要更新緩存記錄，將訪問熱度最低的數據塊從緩存中剔除，以便將熱度高的數據調入緩存，此時按照HDL緩存方法更新緩存記錄，然后將新的查詢結果存入緩存空間，完成緩存更新。

構建預熱查詢后熱點數據存儲在緩存中，后續查詢命中緩存的查詢時間為式（9）中的Th，未命中緩存的查詢時間為式（8）中的Tc。將兩者做減法運算得到命中一次預熱查詢帶來的查詢時間增益Tg，可表示為

泊松分布用于描述單位時間內隨機事件發生的次數，設計預熱查詢的熱點數據單位時間內被多次訪問的概率服從參數為λ的泊松分布，泊松分布的概率函數為

由式（11）可得設計預熱查詢的熱點數據單位時間內查詢的次數等于λ。對集群設計預熱查詢，用預熱查詢產生的查詢時間增益減去構建預熱查詢花費的時間可得

式中，Φ(i)為第i條預熱查詢時間函數，其為i的單調增函數。由式（12）可得，隨著預熱查詢數目i的增加，存在以下3種情況：

（1）當i較小時，λTg＞Φ(i)，即預熱查詢產生的延遲小于帶來的時間增益。

（2）當i增加，Φ(i)增加，會使λTg=Φ(i)，即預熱查詢產生的延遲與帶來的時間增益相等。

（3）當i增加到一定值，會使λTg＜Φ(i)，即預熱查詢產生的延遲大于帶來的時間增益。

由上述分析可知，預熱查詢數目i存在極值點，此時設置預熱查詢減少的查詢時間最多。測試時不斷增加預熱查詢數目，當繼續增加預熱查詢數目導致查詢時間增加時，則未增加前的預熱查詢數目為最佳預熱查詢數目io，此時產生的時間增益最大。

3 算例測試

3.1 集群搭建

鐵路配電網也屬于電力系統的一部分，運行期間會產生大量的監測數據，本文以某鐵路10 kV 配電網的數據采集與監控SCADA（supervisory control and data acquisition）系統導出的監測數據為數據源，建立數據源中站所號、遙測名、遙測值、時間戳等非主鍵屬性的倒排索引集群，該配電網監測系統示意如圖4所示。

圖4 配電網監測系統示意Fig.4 Schematic of distribution network monitoring system

采用4 臺計算機構建倒排索引集群，4 臺計算機的操作系統均為Linux（Centos7）系統，將數據導入索引集群，測試所提技術的實際效果。索引集群的4臺計算機節點的詳細配置如表1所示。

表1 集群節點詳細配置Tab.1 Detailed configuration of cluster nodes

3.2 測試不同方法對查詢時間的影響

1）不同查詢條件下不同方法的查詢時間

在配電網監測數據索引集群正常運行時，分別向集群導入1×107、4×107、8×107、1.2×108、1.6×108條記錄，使用掃描查詢（無緩存）、HDL緩存查詢、關系型數據庫方法和HDPL 緩存查詢對不同重復度的數據進行查詢性能測試。進行3 組不同條件的測試，單線程為只執行一個查詢任務，多線程為執行多個查詢任務。第1組單線程下執行單條件，站所223的查詢；第2組單線程下執行雙條件，站所223&遙測值16390的查詢；第3組多線程下執行單條件，站所223的查詢。每組進行12次測試，舍棄最小值和最大值，剩下的10次測試結果取平均，測試結果如圖5所示。

圖5 不同方法對比結果Fig.5 Comparison results of different methods

由圖5 可知，在單條件?單線程查詢條件下，當集群數據規模為1× 107條時，HDPL 緩存查詢與HDL緩存查詢時間相差1 ms，但當數據規模增加至1.2×108、1.6×108條時，HDPL 緩存查詢相比于HDL緩存查詢分別減少78 ms、135 ms的查詢時間；在多條件?單線程查詢條件下，當數據規模為1.2×108條時，HDPL 緩存查詢相比于HDL 緩存查詢、關系型數據庫方法和掃描查詢分別減少了134 ms、192 ms、203 ms，HDPL 緩存查詢的查詢時間最短；在單條件?多線程查詢條件下，在數據規模分別為1.2×108、1.6×108條時，HDPL緩存查詢相比于HDL緩存查詢的查詢耗時分別減少84 ms、140 ms。

綜上表明，在不同實驗條件下，HDPL緩存查詢的查詢性能始終優于其他3種方法。HDPL緩存查詢通過尋找局部最優解的方式代替尋找全局最優解，僅將一部分數據存儲在鏈表中，減少了緩存空間中存儲數據的鏈表長度及緩存更新時節點移動操作，避免了額外空間的浪費，降低了內存的消耗。HDPL緩存查詢能夠提高配電網海量監測數據索引集群基于非主鍵查詢的查詢性能。

2）數據更新時間間隔對查詢性能的影響

在配電網監測數據索引集群正常運行時，向集群導入1.6×108條監測數據，持續向集群導入監測數據，導入監測數據的時間間隔分別為8 ms、16 ms、24 ms、32 ms、40 ms、48 ms和56 ms，使用HDL、HD?PL 方法對不同重復度的關鍵詞數據進行查詢性能測試，測試結果如圖6所示。

圖6 不同數據更新間隔時查詢性能比較Fig.6 Comparison of query performance at different data update intervals

由圖6 可知，在不同的數據更新間隔時，HDPL緩存查詢的查詢時間始終在21 ms左右，波動較小，而HDL 緩存查詢的查詢時間為125 ms 左右，查詢時間在一定的范圍內波動；HDPL 緩存方法始終優于HDL 緩存方法，且在間隔時間為16 ms 時，HDPL緩存查詢相比于HDL 緩存查詢能夠節省111 ms 查詢時間。相比于HDL 緩存方法，HDPL 緩存方法在存儲部分緩存記錄的鏈表中更新緩存記錄，降低內存的消耗，節省內存空間。

3.3 測試預熱查詢數目對查詢性能的影響

執行查詢請求，利用查詢管理器獲取熱點數據；之后針對熱點數據設置預熱查詢，改變預熱查詢的設置數目，測試查詢時間的變化。在集群數據規模為1.6×108條時進行4組不同條件的測試：第1組未設置預熱查詢；第2 組構建3 條熱點數據的預熱查詢，分別為站所223、遙測16390、3 400.000 00；第3 組構建4 條熱點數據的預熱查詢，分別為站所223、遙測16390、3 400.000 00 和站所443；第4 組構建5條熱點數據的預熱查詢，分別為站所223、遙測16390、3 400.000 00、站所443和遙測16391。

預熱查詢數目對查詢性能影響的測試結果如圖7 所示。單條件查詢為站所223，雙條件查詢為站所223&遙測16390，三條件查詢為站所223&遙測16390&3 400.000 00。

圖7 預熱查詢數目對查詢時間的影響Fig.7 Impact of the number of preheated queries on query time

圖7（a）為在單線程下對比設置不同預熱查詢數目和未設置預熱查詢的查詢時間。由圖7（a）可知，在單線程、單條件查詢且未設置預熱查詢時，查詢時間為301 ms，設置3條預熱查詢時，查詢時間為277 ms；增加預熱查詢數目至4、5條，查詢時間分別增長至287 ms、292 ms；設置3條預熱查詢減少的查詢時間最多，對應式（12）的情況（1）。在三條件查詢時，預熱數目為5 條時，對應式（12）的情況（2），此時預熱查詢產生的時間增益和產生的延遲相等。對于雙條件、三條件查詢，均為設置3 條預熱查詢時查詢時間最短，減少的查詢時間最大值為48 ms。預熱查詢條數i=3、4、5 時均能減少查詢時間，其中，i=3 時減少的查詢時間最多。

圖7（b）為多線程下對比設置不同預熱查詢數目和未設置預熱查詢的查詢時間。由圖7（b）可知，在多線程下，三條件查詢且未設置預熱查詢時，查詢時間為752 ms，設置3 條預熱查詢時的查詢時間為712 ms；在預熱查詢數目為4條時，對比設置3條預熱查詢，查詢時間有所增加；在預熱查詢數目為5條時，查詢時間大于未設置預熱查詢的查詢時間，對應式（12）的情況（3）。上述結果說明多線程下三條件查詢的最佳預熱數目為3 條；雙條件查詢時，i=3 為最佳預熱查詢數目，減少的查詢時間為72 ms；在單條件查詢時，最佳預熱查詢數目為i=4，此時減少80 ms的查詢時間。

4 結 論

通過熱點數據部分鏈表緩存方法的研究，算例測試了不同條件的查詢和預熱查詢的影響，測試結果表明以下結論。

（1）在不同查詢條件下，HDPL方法均優于其他3 種方法；在不同數據更新間隔下，HDPL 緩存查詢的查詢時間波動較小，且始終優于HDL 緩存查詢，在數據更新間隔為16 ms時，HDPL緩存查詢相比于HDL 緩存查詢能夠節省111 ms 的查詢時間。測試結果驗證了所設計的HDPL 分布緩存方法能有效減少集群的查詢時間。

（2）單線程下均為在預熱數目i=3 時減少的查詢時間最多；多線程下，雙條件、三條件查詢時，均為i=3 時減少的查詢時間最多；單條件查詢時，i=4 減少的查詢時間最多。測試結果驗證了設計的預熱查詢存在最佳數目，且能夠實現搜索器的熱啟動，有效減少查詢時間，提高集群工作效率。