面向海量電子憑據的分層可擴展存儲架構

李鳳華，李丁焱，金偉，王竹，郭云川，耿魁

（1. 中國科學院信息工程研究所，北京 100093；2. 中國科學院大學網絡空間安全學院，北京 100049）

1 引言

隨著互聯網在各個領域的不斷深入，云計算、電子商務、電子支付、社交網絡等新型服務模式得到了迅猛發展，各類網絡業務的興起極大地促進了電子憑據的發展，產生了海量的電子憑據數據。以電子發票服務體系為例，自 2016年起，我國電子發票進入廣泛推廣期，根據智研咨詢集團《2018—2024年中國電子發票市場運營態勢及前景預測報告》預計，到2022年我國電子發票開具總量高達545.5億張，并保持年均超過100%的高速增長。

海量的數據使單個節點難以存儲，節點的訪問請求無法被及時處理，且無法滿足用戶的快速訪問需求，因此必須擴展系統的性能，加快節點訪問請求的處理速度。傳統的集中式存儲方案更傾向于縱向擴展，不斷升級設備的硬件配置，但是這種方式帶來的性能提升遠不及數據快速增長造成的壓力。海量的數據更適合采用分布式的存儲方案[1-2]，易于水平擴展，更符合實際的使用需求，然而，目前，大數據存儲系統在數據定位、數據緩存和負載均衡方面都存在顯著挑戰。

在數據定位方面，目前，常用的數據節點定位方式主要有以下3種。1) 基于文件目錄進行定位[3]。將數據節點的元信息集中存儲到中心服務器上，訪問數據時先到中心服務器定位數據節點，然后訪問相應的數據節點。但是當數據量和訪問量很大時，數據定位所需的開銷會比較大，中心服務器容易成為系統瓶頸。2) 基于一致性hash算法進行定位[4]。將數據映射到一個環狀區間，在增刪節點時，只有鄰近的節點會受到影響，這避免了節點規模變動時數據遷移代價過高的問題。為了保證節點較少時數據依然能夠均勻分布，亞馬遜公司在Dymano系統中引入了虛擬節點的概念，增加了從虛擬節點到物理節點的映射。但是由于采用了完全去中心化的設計，要定位到數據所在的節點，需要的時間復雜度為O(n)，當系統規模很大時，定位的開銷將會很大。3) 基于索引進行定位[5]。通過跳表、位圖等數據結構構建分層索引，訪問數據時先通過索引快速定位數據所在的節點，避免了額外的查詢開銷，這種方法的缺點是實現比較復雜、索引的維護代價比較高。

在數據緩存方面，目前，使用較為廣泛的大數據存儲系統大多直接對磁盤進行讀寫，這為加快上層應用的訪問速度，進一步提升了系統性能，且出現了基于緩存的分層式架構[6]，將部分數據放置到隨機訪問性能更好的固態硬盤或內存中。在分布式緩存中，Redis和Memcached這兩款內存數據庫應用的較為廣泛[7]，它們使用最近最少使用（LRU,least recently used）算法作為默認的緩存替換策略。LRU算法是一種常見的內存頁面置換算法，簡單易用，但是該算法只考慮了“時間”因素，忽略了對“頻率”因素的考慮，因此在緩存策略方面依然存在著很大的改進空間。

在負載均衡方面，文獻[8]對當前分布式系統中的任務分配與負載均衡模型進行了分析，并從控制模型、資源優化、可靠性、協作性和網絡結構這 5個方面對當前的研究進行了討論，提出了最小化響應時間、最小化任務完成時間、最大化任務吞吐量以及最大化任務可靠性這4個優化目標，指出了沒有任何一種方案能在4個方面都達到最優效果，因此在實現時需要有所側重。文獻[9]對大數據系統中的任務調度框架進行了研究，從任務粒度、執行時間、調度時機、實現架構這4個方面進行了分類總結，指出了當前大數據系統中的調度技術主要聚焦于集群環境下的任務批處理，在動態資源供應、分布式與異構網絡、維持穩定執行時間等方面還有很大的改進空間。

針對海量電子憑據數據存儲時面臨的問題，本文提出了一種面向海量電子憑據的分層可擴展存儲架構，貢獻如下。

1) 分層可擴展存儲架構

為了快速地定位數據所在的節點，提出了基于hash取模算法與一致性hash算法的分層存儲架構，該架構的數據定位的時間復雜度為O(1)。同時針對hash取模算法模數變化時數據遷移成本過高的問題提出了改進方案，增強了系統的可擴展性。

2) 基于熱數據的緩存方案

為了進一步加速數據訪問的過程，減少對下層數據節點的訪問，設計了基于熱數據的緩存方案，識別用戶高頻訪問的數據并且緩存到中間層，當用戶再次訪問這些數據時，可以直接從緩存中返回結果，不需要再訪問下層的數據節點。

3) 基于訪問時延的負載均衡方案

為了避免節點負載不均衡對系統整體性能的影響，設計了基于訪問時延的負載均衡方案，基于訪問時延評估當前節點的負載狀況，并依據評估結果調整下一時刻的節點負載。

2 相關工作

2.1 分布式存儲架構

目前，主要的分布式存儲架構大體可以分為主從架構和對等網絡（P2P, peer to peer）架構兩類。在主從架構中[10]，主節點負責管理整個系統，監視從節點的狀態，對從節點的負載進行調度，這種架構設計和維護相對簡單，但是主節點可能會成為系統瓶頸。在P2P架構中[11]，每個節點都是對等的，負責管理自己的區域，可以靈活地增刪節點，并且不會對系統性能造成較大影響，但是系統設計復雜，不易實現。未來的研究趨勢是將這2種架構結合，靈活地運用兩者的優勢。

2.2 數據緩存

對于訪問頻繁的數據，如果每次都從磁盤上讀取，勢必會造成I/O瓶頸，使用緩存技術可以很好地解決這個問題。雖然內存的訪問速度遠大于磁盤的訪問速度，但是由于價格比較昂貴，因此一般不會將磁盤的數據全部緩存到內存中，而是在達到一定容量后再進行替換。常用的緩存替換算法[12-13]包括LRU算法、最近最不常用（LFU, least frequently used）算法、自適應緩存替換（ARC, adaptive replacement cache）算法、最短最近使用（LIRS, low inter-reference recency set）算法等，這些算法以訪問時間和訪問頻率等信息作為替換標準，但是適用的訪問模式往往比較固定，例如，LRU算法適用于高局部性的訪問模式，LFU算法適用于順序或隨機的訪問模式，當訪問模式變化時，緩存命中效果比較差。文獻[14]指出了云環境下內存緩存與傳統的CPU緩存區別很大，不能采用固定的行為模式，需要動態地對應用進行感知。文獻[15]提出了一種針對HBase的索引熱點數據緩存方案，不斷統計數據的訪問頻率，利用指數平滑的思想識別熱點數據，比LRU算法擁有更高的命中率。

2.3 負載均衡

負載均衡是分布式設計中的關鍵問題之一，在實際運行環境中，難以準確預測節點的任務量，可能會出現部分節點負載過重的情況，此時需要對節點的負載進行動態的調整，并且盡可能地減小調整過程的開銷。實施負載均衡的第一步是對節點的負載進行估算，常用的方法包括如下3類。

1) 資源權重法[16]

資源權重法通過獲取節點的 CPU使用率、內存使用率、帶寬使用率、磁盤I/O使用率等指標，為每一個指標賦予一個權重，綜合評估節點的負載。但是這種方法通用性差，容易產生很大的偏差。根據多項指標評估節點的狀態是一個典型的組合優化問題，這類問題更適合用智能算法[17]來解決。智能算法對于解決復雜的NP問題或者非線性問題有較好的效果，但是會消耗過多的資源和時間，對于實時性的訪問并不適用。

2) 狀態探測法[18]

狀態探測法是周期性地獲取各個節點的狀態，例如是否空閑、任務隊列長度等，根據節點狀態進行選取，但是獲取節點狀態的過程可能會有較大的開銷。

3) 負載預測法[19]

負載預測法通過記錄節點的歷史負載信息，依據數學模型以及當前負載狀態預測下一階段的負載。這種算法在負載比較穩定的情況下可以得到較好的預測結果，但是卻忽略了對服務器性能差異的考慮。

針對上述問題，本文提出了一種面向海量電子憑據的分層可擴展存儲架構，采用hash取模算法和一致性hash算法實現快速的數據定位，同時還增強了系統的可擴展性。此外，本文設計并實現了相應的數據緩存和負載均衡方案，進一步保障了系統整體的訪問性能。

3 分層可擴展架構設計

3.1 分層可擴展架構概述

如圖1所示，系統的整體架構包括3層，分別是應用網關層、hash取模層和一致性hash層。

圖1 分層可擴展架構

應用網關層是分層可擴展架構的第一層，負責對外提供用戶級接口，包括插入、查找等操作；提供基于hash取模算法的數據映射規則，將數據定位到hash取模層的節點上；可以在應用網關層指定基于hash取模算法的橫向擴展規則，在增刪節點時減少遷移的數據量。

hash取模層是分層可擴展架構的第二層，負責管理下層的數據節點，轉發來自應用網關層的操作請求，緩存訪問頻繁的數據。hash取模層的節點提供基于一致性hash算法的數據映射規則，是一個中心化的節點，中心化的結構可以避免在分布式結構中的定位開銷，加快數據定位的速度。在數據訪問的過程中，hash取模層對熱數據進行識別，并將其緩存到內存中，當有重復的數據訪問請求時可以直接返回結果。此外，還對下層數據節點進行負載及異常行為監測，根據監測結果進一步實現節點間動態的負載均衡。

一致性hash層位于架構的第三層，是數據節點所在層，負責實際的數據存儲和備份。為了保證數據的可用性，一致性hash層采用主從模式進行數據備份，而且采用讀寫分離的方式，即其中一個節點作為主節點，負責寫操作，其余節點作為副節點，用于同步主節點的數據，負責讀操作。在訪問副節點時，需要一定的策略來保證節點間的負載均衡，防止部分節點過載導致的系統性能下降。

3.2 橫向擴展

hash取模算法在增刪節點時會導致數據映射關系失效，需要遷移大量的數據。一種改進的方案[20]是在增刪數據節點時，采用成倍增加或大幅減少的方式，可以在系統擴展的同時減少遷移的數據量。但是該方案的一個明顯缺點是節點數必須成倍變化，不夠靈活，難以滿足實際的使用需求。為了在減少遷移的數據量的同時，能夠更加靈活地增刪節點，本文在上述方案的基礎上分別對節點增加方案和節點刪除方案進行了改進。

節點增加的過程可以分為節點倍增和節點枝剪2個步驟。假設當前有2n(n＞0)個數據節點，編號為0～(2n-1)，數據與節點映射時對2n取?！，F在需要添加2m(0≤m＜n)個節點，編號為2n～(2n+2m-1)。對于新添加的每個節點，都需要獲得2個集合，集合 set1中是添加節點后需要重定向到該節點的節點編號，集合set2中是需要復制數據到該節點的節點編號。首先進行節點倍增，生成編號為0～(2n+1-1)的節點，但是由于編號為(2n+2m)～(2n+1-1)的節點不是真實存在的，因此需要進行節點枝剪，將不存在的節點重定向到編號為2n～(2n+2m-1)的節點上。集合set1和集合set2分別為

其中，x位于2n～(2n+2m-1)之間，集合set1中的所有元素都位于2n～(2n+1-1)之間，集合set2中的所有元素都位于0～(2n-1)之間，set2中所有節點的數據需要復制到對應集合set1中編號最小的節點上，數據與節點映射時對2n+1取模，將set1中所有的節點都重定向到集合中編號最小的節點上。如果需要把節點數目恢復成2n個，可以將編號為2n～(2n+2m-1)中每個節點上的數據復制到對應set2中每個編號對應的節點上，數據與節點映射時對2n取模。

節點刪除時，假設當前有2p(p＞0)個數據節點，編號為0～(2p-1)，數據與節點映射時對2p取?！，F在需要刪除2q(0≤q＜p-1)個節點，編號為(2p-2q)～(2p-1)。對于即將被刪除的每個節點，都需要將其重定向到其他節點上。根據式(4)進行計算，其中，deleteNum是要刪除的節點編號，redirectNum是重定向后的節點編號。

將被刪除節點的數據復制到重定向后的節點上，數據與節點映射關系保持不變，仍然對2p取模。如果需要把節點數再恢復成2p個，根據式(4)找到重定向節點，然后將數據復制回本節點。數據與節點映射關系保持不變，仍然對2p取模。

接下來，用示例進行說明。向已有的22=4個節點（node0～node3）中添加 21=2個節點（node4和node5）的過程分別如圖2和圖3所示，初始時數據與節點映射對22=4取模。由式(1)可得d=2，由式(2)可得node4和node5對應的set1分別為{4,6}和{5,7}，由式(3)可得node4和node5對應的set2分別為{0,2}和{1,3}。在修改數據與節點的映射關系前，將node0和node2中的數據復制到node4，將node1和node3的數據復制到node5。數據與節點映射時對22+1=8取模，由于node6和node7并不存在，因此將node6中的數據重定向到node4中，node7中的數據重定向到node5中，這個過程遷移了一半的數據。圖3中下劃線標記的數據是在新的映射關系下失效的數據，需要進一步刪除。

圖2 節點倍增

在已有的 23=8個節點（node0～node7）中刪除21=2個節點（node6和node7）的過程如圖4所示，初始時數據與節點映射對 23=8取模。根據式(4)可得node6和node7的重定向節點分別為node4和node5，在刪除node6和node7之前將數據分別復制到node4和node5，數據和節點的映射關系保持不變。圖4中下劃線標記的數據是重定向后的數據。

圖3 節點枝剪

圖4 節點刪除

從圖3和圖4中可以看出，無論是增加節點還是減少節點，最終都會打破原先數據均衡分布的局面。但需要注意的是，橫向擴展方案針對的是 hash取模層節點的變動，存儲數據并不由該層節點負責，而是由下層的多個一致性 hash層節點負責，所以對于橫向擴展后數據量較多的 hash取模節點，可以在下層為其部署更多的一致性 hash節點，這樣能夠保證最終每個一致性hash節點上存儲的數據依然比較均衡。

3.3 數據緩存

現實中的數據訪問往往遵循“二八定律”，即80%的業務訪問集中在20%的數據上，這20%的數據被稱為熱數據。如何準確地識別熱數據對于數據緩存來說十分重要，將訪問頻繁的熱數據緩存到內存中，能夠加快數據訪問的速度、提升系統的性能。

在對數據的訪問信息進行量化時，如果只考慮當前時間段內的訪問信息，會將一部分用戶隨機訪問的冷數據誤當作熱數據而進行緩存，為了避免這種情況的發生，需要同時結合歷史訪問信息和當前訪問信息來識別熱數據。

選擇固定時間段內的數據訪問次數作為數據熱度的量化指標，采用式(5)進行計算。

其中，α用于決定當前時間段內的訪問信息和歷史熱度信息各自所占的比重，也稱作衰變系數，滿足0≤α≤1；countΔt1是時間段Δt1內統計到的數據訪問的次數；heatt-1是數據的歷史熱度信息；heatt是更新后的當前熱度信息。α值越大，表明當前時間段內訪問信息所占比重越大，歷史熱度信息在迭代的過程中減小得越快；反之則是當前時間段內訪問信息所占比重越小，歷史熱度信息在迭代過程中減小得越慢。

由于內存空間有限，本文無法將全部的數據都進行緩存，因此事先指定數據緩存空間的大小，在每次更新完成數據熱度值后，按照熱度值進行排序，如果排序后的數據量小于緩存空間，就把所有的數據進行緩存；如果排序后的數據量大于緩存空間，就從熱度值最低的數據開始淘汰，直至剩余數據量小于緩存空間。數據熱度更新和緩存替換算法如算法1所示。

算法1數據熱度更新和緩存替換算法

輸入Δt1內的訪問信息集合countΔt1，歷史熱度信息集合heatt-1，緩存空間大小cachesize

輸出當前熱度信息集合heatt

8) end for

9) 根據熱度值對heatt中的元組進行排序

10) if heatt的規模小于或等于cachesize

11)返回heatt

12) else if heatt的規模大于cachesize

13)while heatt的規模大于cachesize

14)刪除熱度值最小的數據

15)end while

16)返回heatt

17) end if

3.4 負載均衡

當進行讀操作時，需要從多個副節點中選取負載最小的節點進行訪問。訪問請求響應時間的長短是衡量節點負載狀況的一個重要標準，文獻[21]指出單位時間內的平均訪問時延與在該單位時間內處理的并行請求總數，能比較準確地反映節點的狀況，因此本文也基于訪問時延對節點的性能進行評估。

根據線性關系，可得

其中，Resp表示請求的平均訪問時延；k表示直線的斜率，反映了隨著請求數增加導致平均響應時間增長的快慢，是節點性能的評價指標；Req表示請求的數目；c表示其他因素導致的響應時間的增量。為了獲得更加準確的估計值，根據多次采樣的結果進行擬合，多點擬合直線常用的方法是最小二乘法，假設多次采樣的結果分別為和Resp=，可以根據式(7)～式(11)進行計算。

采用基于指數平滑的方法進行評估，有

其中，Reqt為節點的當前負載估算結果；Reqt-1為節點的歷史負載；xΔt2為當前時間間隔內的請求數；θ為衰變系數，滿足0≤θ≤1，θ越大，表示歷史信息的影響越小，反之歷史信息的影響越大。

選取訪問節點時，使用最新估算的節點性能指標與節點負載指標，根據式(6)進行計算并選取結果最小的節點，意味著該節點可以使請求的平均響應時間最小，提供更加快速的訪問。

在系統橫向擴展時，新的數據查詢訪問請求立即按照新的規則進行分發，但是被影響的hash取模節點上可能仍然存在一些舊的數據查詢請求，這部分請求仍然會在失效數據被刪除前得到服務，導致當前訪問的副節點的負載偏高，在下個周期會選擇其他副節點進行訪問，同樣也導致新選擇的副節點負載偏高，最終殘留的查詢請求被多個副節點分攤，而且由于這部分請求數量有限，所以每個副節點負載偏高的幅度很低，處理過程很快，系統在短時間內就可恢復穩定。

4 實驗分析

4.1 實驗環境

基于本文架構在局域網中搭建實驗環境，實驗環境包括一個應用網關層網關g0，2個hash取模層網關g1和g2，4個數據主節點node1～node4，以及若干客戶機模擬用戶訪問。根據存儲單元的硬件配置，g1管理node1和node4這2個數據主節點，g2管理node2和node3這2個數據主節點。本文中副節點的配置與各自主節點相同，其中，node1的 2個副節點分別為node11和node12，node2的2個副節點分別為node21和node22，node3的 2個副節點分別為node31和node32，node4的2個副節點分別為node41和node42，各個節點的配置如表1所示。

表1 各個節點的配置

4.2 效果分析

用戶對數據的訪問往往遵循“二八法則”，這滿足Zipf分布的典型特征[22]，因此本文在實驗中對數據節點發起Zipf分布的訪問請求。

1) 存儲均衡分析

在不同的數據規模下，將數據存儲到2 000個節點上，測試數據分布的均衡狀況。計算每個節點的數據偏差δ為

其中，x表示節點上的真實數據量，表示理想情況下節點的數據量。實驗結果如圖5所示，實驗數據表明，在不同數據規模下，大部分節點的數據偏差都在 8%以內，而且隨著數據規模的不斷增大，節點的數據偏差依然能保持穩定。這說明即使數據規模很大，本文所提方案也能有效地將數據均衡地存儲在各個節點。

2) 訪問均衡分析

節點在處理訪問請求的過程中需要耗費一定的資源，包括CPU資源、內存資源和磁盤I/O資源，但是對不同資源的消耗程度并不相同，因此本文為上述3種資源賦予不同的權重來更客觀地綜合評估節點的負載。采用式(14)來對每個節點的負載狀況進行量化，其中，C代表CPU使用率；M代表內存占用率；D代表磁盤I/O占用率；α、β、γ分別為這3種資源的權重值，滿足式(15)。

實驗發現，在訪問請求處理的過程中，CPU資源對于節點負載的影響程度要高于內存資源和磁盤I/O資源，內存資源和磁盤I/O資源對于節點負載的影響程度相近，所以為 CPU資源賦予較高的權重值，為內存資源和磁盤I/O資源賦予相同的權重值，經過多次實驗，最終確定α、β、γ的值分別為0.4、0.3、0.3。在客戶端持續訪問的3 h內，每隔0.5 h對節點的負載率L進行一次測算，實驗結果如圖6和圖7所示。從圖6和圖7可以看出，隨著時間的變化，單個節點的實際負載一直在波動，但是多個節點之間負載的波動趨勢大致相同，負載率也比較接近，說明了本文所提負載均衡方案的有效性。

圖5 不同規模下的數據分布

圖6 網關g1下各個副節點負載

圖7 網關g2下各個副節點負載

3) 查詢效果分析

通過客戶端對數據節點發起符合 Zipf分布的數據訪問請求，測試數據緩存對查詢效果的影響。查詢效果可以由平均訪問時延體現，緩存大小可以用緩存數據量占數據總量的百分比表示，在本文架構下對平均訪問時延進行測試。

圖8對比了LRU算法、LIRS算法、ARC算法和本文算法的緩存命中率。實驗數據表明，隨著緩存規模的增大，所有算法的緩存命中率都在提升，但是本文算法的緩存命中效果總是優于其他3種算法。

圖8 緩存命中率對比

圖 9給出了平均訪問時延隨緩存大小的變化情況。從圖 9可以看出，數據訪問延時隨緩存增加而降低。訪問時延由計算時延、網絡時延和查詢時延這三部分組成，其中，計算時延包括2次hash計算，時間復雜度為O(1)，經測試平均耗時為5 ms；網絡時延經測試一般不會超過50 ms；當數據規模為1 000億條、節點規模為2 000個時，平均每個節點的數據量為5 000萬條，按照最差情況下會有8%左右的偏差，本文在數據節點上存儲5 400萬條數據進行實驗，在無緩存情況下，經測試平均查詢時延約為165 ms。由上述分析可知，即使在無緩存情況下，數據平均訪問時延約為220 ms，能滿足實際需求。

圖9 平均訪問時延對比

5 結束語

本文針對海量電子憑據數據的存儲與快速訪問需求帶來的挑戰，從橫向擴展、數據緩存和負載均衡三方面提出了改進方案，其中，橫向擴展方案降低了數據遷移的成本，數據緩存方案對熱數據的訪問進行了優化，負載均衡方案可以將訪問請求均勻地分布在各個節點上，并結合上述改進方案設計了一種分層可擴展存儲架構，能夠顯著加快數據訪問的過程。未來的工作還包括對分層可擴展架構中緩存方案和負載均衡方案的進一步優化。本文所提方案已應用于國家重點研發計劃“安全電子憑據服務及其監管關鍵技術”項目中，能夠滿足千億級數據毫秒量級查詢響應的應用需求。