面向海量電子憑據(jù)的分層可擴展存儲架構(gòu)

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

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

1 引言

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

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

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

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

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

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

1) 分層可擴展存儲架構(gòu)

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

2) 基于熱數(shù)據(jù)的緩存方案

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

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

為了避免節(jié)點負載不均衡對系統(tǒng)整體性能的影響，設(shè)計了基于訪問時延的負載均衡方案，基于訪問時延評估當前節(jié)點的負載狀況，并依據(jù)評估結(jié)果調(diào)整下一時刻的節(jié)點負載。

2 相關(guān)工作

2.1 分布式存儲架構(gòu)

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

2.2 數(shù)據(jù)緩存

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

2.3 負載均衡

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

1) 資源權(quán)重法[16]

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

2) 狀態(tài)探測法[18]

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

3) 負載預測法[19]

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

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

3 分層可擴展架構(gòu)設(shè)計

3.1 分層可擴展架構(gòu)概述

如圖1所示，系統(tǒng)的整體架構(gòu)包括3層，分別是應(yīng)用網(wǎng)關(guān)層、hash取模層和一致性hash層。

圖1 分層可擴展架構(gòu)

應(yīng)用網(wǎng)關(guān)層是分層可擴展架構(gòu)的第一層，負責對外提供用戶級接口，包括插入、查找等操作；提供基于hash取模算法的數(shù)據(jù)映射規(guī)則，將數(shù)據(jù)定位到hash取模層的節(jié)點上；可以在應(yīng)用網(wǎng)關(guān)層指定基于hash取模算法的橫向擴展規(guī)則，在增刪節(jié)點時減少遷移的數(shù)據(jù)量。

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

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

3.2 橫向擴展

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

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

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

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

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

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

圖2 節(jié)點倍增

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

圖3 節(jié)點枝剪

圖4 節(jié)點刪除

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

3.3 數(shù)據(jù)緩存

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

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

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

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

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

算法1數(shù)據(jù)熱度更新和緩存替換算法

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

輸出當前熱度信息集合heatt

8) end for

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

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

11)返回heatt

12) else if heatt的規(guī)模大于cachesize

13)while heatt的規(guī)模大于cachesize

14)刪除熱度值最小的數(shù)據(jù)

15)end while

16)返回heatt

17) end if

3.4 負載均衡

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

根據(jù)線性關(guān)系，可得

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

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

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

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

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

4 實驗分析

4.1 實驗環(huán)境

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

表1 各個節(jié)點的配置

4.2 效果分析

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

1) 存儲均衡分析

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

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

2) 訪問均衡分析

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

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

圖5 不同規(guī)模下的數(shù)據(jù)分布

圖6 網(wǎng)關(guān)g1下各個副節(jié)點負載

圖7 網(wǎng)關(guān)g2下各個副節(jié)點負載

3) 查詢效果分析

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

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

圖8 緩存命中率對比

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

圖9 平均訪問時延對比

5 結(jié)束語

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