劉淑平 李仲游

摘要：為了改善服務器端系統(tǒng)登錄模塊運行環(huán)境， 采用云數據庫解決方案，但該方式可能引發(fā)額外的網絡延時消耗，導致系統(tǒng)性能下降?；贐loom filter算法設計過濾器，提前判定數據是否在數據庫中，能夠減少數據庫讀取次數，進而降低網絡延時帶來的額外性能損耗。結合Redis良好的分布式性能及持久化方案對Bloom filter進行管理。實驗結果表明，當查詢非命中率達到0.5%時，可以有效降低系統(tǒng)整體網絡延時及響應延時。得出結論：采用基于Bloom filter的過濾器對數據是否在數據庫中進行判定，能夠降低網絡延時帶來的影響，從而提高系統(tǒng)整體響應性能。

關鍵詞：云數據庫；Bloom filter；Redis；網絡延時

DOIDOI：10.11907/rjdk.181296

中圖分類號：TP391

文獻標識碼：A 文章編號：1672-7800（2018）010-0183-04

英文摘要Abstract：To reduce the performance loss of the login module caused by the network delay running on cloud database.，we use the filter which base on Bloom filter to judge if each data have been load in database or not to reduce the number of database read so that the performance loss caused by the network delay can be reduced. Bloom filter is managed by Redis distributed version which can promise high availability. Experiment results show that when the total query proportion of missing Sql query is more than 0.5% in the database base， the overall system network delay can be effectively reduced by using Bloom filter and the overall system response delay can be reduced. Thus we can get a conclusion that the filter based on Bloom filter can reduce the impact of network delay and improve the overall system response.

英文關鍵詞Key Words：cloud database；Bloom filter； Redis；network delay

0 引言

近年來，云數據庫技術發(fā)展迅速。與傳統(tǒng)數據庫相比，云數據庫具有以下優(yōu)勢[1]：①高可用性，異地多機熱備份；②低維護成本，無需維護數據庫運行服務器，運維交由云廠商負責；③具有彈性伸縮配置等特性，無需數據遷移，可根據需要提高數據庫運行硬件配置。因此，越來越多公司采用云數據庫中的RDS（relational Database Service）服務代替企業(yè)內部自建的Mysql、Oracel、Sql Server、Postgre Sql等數據庫服務器。然而，由于云數據庫是通過網絡提供服務的，所以服務器訪問數據可能出現(xiàn)網絡延時現(xiàn)象。所以如何降低網絡延時的影響，使服務器更高效地對外提供服務，是一個亟待解決的問題。

對于云數據庫運行環(huán)境，網絡延時的優(yōu)化可以從兩個角度出發(fā)：①請求服務器端；②云數據庫服務端。但依靠云數據庫服務端優(yōu)化網絡延時需要云廠商配合，實現(xiàn)難度較高。因此，本文從請求服務器端優(yōu)化角度出發(fā)，借鑒現(xiàn)有的Hbase[5]、Spark、Tensorflow等系統(tǒng)中的過濾器（filter）思想[7]，利用Bloom filter算法實現(xiàn)過濾器[13]，同時結合Redis對數據庫數據存在與否進行判斷[6]，以減少不存在的數據訪問數據庫的消耗，進而彌補網絡延時帶來的系統(tǒng)總體損失。

1 相關技術

1.1 Bloom filter

Bloom filter由Burton Bloom于1970年提出，該算法基于哈希算法原理，用于判斷一個元素是否在集合中，具有高效、占用內存少的優(yōu)點。但是標準Bloom filter具有容量固定的缺陷，需要通過再次定義并擴大Bloom filter容量的方法加以解決。Bloom filter屬于概率性數據結構（probabilistic data structure），可適用于允許有假陽性（false positive）、不允許有假陰性（false negative），并且無需知道元素出現(xiàn)次數的場合。因此，Hbase底層利用Bloom filter判斷數據是否在數據庫中。Bloom filter具有許多變種，如動態(tài)增長Bloom filter[9]、Counting Bloom filter、Cuckoo filter[4]等，但是變種Bloom filter可能產生新的問題，如Counting Bloom filter會增加內存占用，動態(tài)增長Bloom filter會導致假陽性幾率增加，Cuckoo filter基于多維數組進行存儲不利于管理等。因此，本文采用標準Bloom filter，標準Bloom filter原理及具體實現(xiàn)如下：

1.1.1 標準Bloom filter原理

Bloom filter具有H1，H2…Hk共K個相互獨立的散列函數，其值域為{0，1，…，m-1}，還需一個長度為M的數組作為散列表（數組中每一位只能為0或1），初始化時數組每一位都為0。對于任意一個數據對象x （x∈S，S為一個具體數據對象集，x為S中一個數據對象） ，將第i（1≤i≤k）個哈希函數映射的位置Hash i（x） 置為 1。 同理，當需要插入一個數據對象S時，步驟如下：①假設{x1，x2..，xn}∈S，對于任意一個x∈{x1，x2..，x3}，分別計算出{hash1（x），hash2（x），…，hashk（x）}；②將計算出散列函數值對應的散列表位置都置為 1。類似地，需要判斷任意一個數據對象Q是否在Bloom filter中，重復上述步驟①，然后對比計算散列函數對應的散列表位置是否都為 1，若全為1表明Q在Bloom filter表達的數據集合中，反之則不存在。

1.1.2 初始化操作

（1）初始化一個長度為M的數組作為散列表，默認初始化數組中每一位為0，數組每一位也只允許兩種狀態(tài)：0或1。該表達方式剛好對應內存底層實現(xiàn)1bit位的定義。因此，出于節(jié)省空間考慮，可以用1bit位直接映射數組每一位，而不是用32bit表達數字[11]。

（2）初始化K個相互獨立且值域都在{0，1，…，m-1}范圍內的哈希函數，用于元素哈希映射[16]。

（3）對于任意一個x，其中x∈{x1，x2..，xn}∈S，先利用MD5或SHA-1（一般工業(yè)應用上選用Murmur3算法）等雜湊算法將不定長的內容x映射為一固定長度的字符串str。對于str中的每一位，計算K個哈希函數對應的散列表位置，并將散列表對應位置置為1[14]。如果散列表對應的位置已置為1，則不作任何修改。該狀況也稱為沖突，沖突的出現(xiàn)是假陽性出現(xiàn)的必要條件。

1.1.3 數據存在檢驗

該方式類似于數據集合的載入操作，不同之處在于數據檢驗時不需要將散列表對應位置置為1，只需判斷所有映射在散列表中的數據是否為1。極端情況下，數據并不存在于數據集合中，但由于數據集合某次映射將散列表某位改變?yōu)?，假如所有用于數據存在檢驗的散列表映射位都為1，則出現(xiàn)了誤判現(xiàn)象（即假陽性出現(xiàn)的原因）[12]。

1.2 Redis

Redis是一種基于內存的 Key-Value 數據庫產品，其支持多種數據類型的存儲： 字符串（string） 、 鏈表（list）、集合（set） 、有序集合與哈希類型（利用Redis中的哈希類型實現(xiàn)Bloom filter）。各種類型都支持多種操作，還提供了部分數據結構原子性操作功能。由于數據都保存在內存中，為了保障數據安全，Redis還實現(xiàn)了數據持久化操作，其可以定期將內存中更新的數據異步寫入磁盤，同時不影響對外服務。在此基礎上，Redis還具有主從復制功能，這對于預防單點故障及提高負載能力有很大幫助。利用該特性，可以將Bloom filter順利部署到多個機器上，從而實現(xiàn)分布式部署。Redis的出現(xiàn)在很大程度上彌補了 Memcached 的不足，其不僅支持更加豐富的數據類型與操作，而且在讀寫效率上也比Memcached 更勝一籌。

2 問題分析

2.1 網絡延時原因分析

以國內某云廠商為例，如圖1所示，所有的數據庫請求都需要通過ECS（服務器端）傳輸到RDS（云數據庫端）。其中有多個環(huán)節(jié)，包括：ECS（云主機）→DNS→SLB→Proxy→RDS（云數據庫），而ECS自建數據庫是ECS→ECS，RDS的網絡鏈路比ECS自建數據庫多3個網絡鏈路環(huán)節(jié)。這些網絡鏈路的網絡延時即為RDS對外服務的網絡延時。為了簡化測算，本文采用ECS到RDS服務的SLB網絡延時作為網絡延時，RDS內部網絡延時對外視作透明。

2.2 網絡延時測算

2.2.1 測算環(huán)境

（1）服務器：阿里云（默認配置為ECS.xn4.small）。具體配置如下：CPU為Intel Xeon E5-2682v4 1核，內存為 1GB，硬盤為1240 IOPS 40GB高效云盤，系統(tǒng)為 Centos 7.3。

（2）云數據庫：阿里云RDS（通用型）。具體配置如下：CPU為1 核，內存為1GB（單機基礎版），硬盤為20GB，數據庫為MySQL 5.7。

2.2.2 測試方式

具體測試步驟如下：

（1）在數據庫中建立測試庫test，test下建立測試表user_login。以12位定長int數據結構字段id為主鍵，45位不定長數據結構字段str作為模擬用戶登錄表。

（2）在ECS端隨機插入1千萬條用戶信息。

（3）從RDS端抽取一百萬條不重復主鍵ID，放入ECS中。ECS逐次查詢這些用戶信息（查詢用戶都存在于數據庫內），模擬線上登錄，采集并監(jiān)控RDS運行狀態(tài)，每隔5s（減緩監(jiān)控壓力，以避免影響查詢性能）采集一次，如圖2所示。RDS命中數據查詢性能如表1所示。

（4）在ECS端隨機生成不存在于數據庫中的ID共一百萬條，逐條輸入以模擬線上輸入錯誤，采集并監(jiān)控RDS運行狀態(tài)，每隔5s（減緩監(jiān)控壓力，以避免影響查詢性能）采集一次，RDS不命中數據查詢性能如表2所示。

（5）通過Linux自帶的ping命令每隔1s采集一次ECS到SLB的延時，采集時長為86 400s（24h整），網絡延時數據如表3所示。

（6）為了簡化實驗，利用Python實現(xiàn)Bloom filter算法并測試Bloom filter性能，對應Bloom filter（1 000w次測試性能）數據如表4所示。

綜上所述，查詢平均耗時為1.193ms，網絡平均耗時為0.108ms。查詢總耗時為1.193+0.108=1.301ms，其中網絡耗時占0.108/1.301≈8%。因此，減少網絡延時對于降低查詢總體延時，以及改進登錄模塊總體耗時具有重要意義。

3 登錄模塊改進方案

3.1 模塊改進方案

改進前的登錄模塊結構如圖3所示，為了提高代碼復用率，實現(xiàn)高內聚、低耦合的設計理念，對于登錄模塊的改進將會通過改進數據庫中間件加以實現(xiàn)，以實現(xiàn)功能與代碼的復用[10]。對數據庫中間件運行機制改進如下：①初始化數據庫連接池；②生成獨立任務隊列，并初始化數據緩存；③開啟隊列監(jiān)聽，當有任何任務進入隊列，先查詢數據是否在緩存中，如果緩存命中，返回緩存結果，否則，立即對RDS執(zhí)行相應的Sql請求。如果是核心業(yè)務請求，則通過持久化技術將請求保持在磁盤上；④RDS返回Sql請求，中間件按照請求參數判斷是否緩存請求結果，并且設定緩存有效期；⑤中間件將結果返回到模塊的相應進程中。改進后流程如圖4所示。

3.2 模塊改進方案性能測試

實驗時所有實驗環(huán)境都關閉緩存，避免緩存的命中率干擾實驗的準確性與公平性。改進前網絡總延時為：x*f+（1-x）*t+n，x為數據不存在于數據庫中的數學期望值概率，f為Sql查詢數據庫中不存在數據的查詢耗時，t為查詢數據庫中存在數據的查詢耗時，n為網絡傳輸耗時。改進后網絡總延時為：x*c+（1-x）*（t+c+n）*（1-bf）+（1-x）*（f+c+n）bf，其中c為Bloom filter查詢數據是否在數據集內的查詢耗時，bf為Bloom filter假陽性出現(xiàn)概率，最壞情況下是t+c+n（RDS命中消耗，加上Bloom filter的額外消耗）。

本文通過模擬不同的x值，進行改進后的系統(tǒng)性能分析。經實驗測試，當E（x）≈0.005 7時，改進后模型與舊有模型系統(tǒng)性能一致；當E（x）>0.005 7，如圖5所示，改進后的性能優(yōu)于改進前模塊性能（生產環(huán)境中查詢數據不命中率遠大于0.005 7，接近0.02。據統(tǒng)計，人的輸入犯錯率大約為0.03～0.01）。

因此，實驗表明將Bloom filter用于提前判定數據是否在數據庫中，能夠減少數據庫讀取次數，進而降低云數據庫網絡延時帶來的額外性能損耗，該方案具有可行性。然而，Bloom filter自身無法保證高可用性，也無法滿足分布式下的一致性等生產環(huán)境需求。為了提高Bloom filter的可用性，可以利用Redis管理存放Bloom filter所占用的內存。借助Redis的一主多從特性，將所有插入請求發(fā)送到Redis中的master下，即可保證Bloom filter在分布式環(huán)境下數據的強一致性[8]。利用Redis自帶的持久化保存方案，還能保證數據不丟失，減少Bloom filter重建對數據庫的查詢壓力。

4 結語

本文針對采用云數據庫解決方案改善登錄模塊運行

環(huán)境后，導致額外網絡延時消耗的問題，詳細分析了云數據庫網絡延時帶來的系統(tǒng)消耗以及Bloom filter的系統(tǒng)消耗，論證了利用Bloom filter提高模塊整體性能的可行性，并且通過模擬不同數據的命中概率，給出不同數據命中概率下的具體性能表現(xiàn)，從而降低了登錄模塊整體耗時，提高了系統(tǒng)整體響應性能。

參考文獻：

[1] 林子雨，賴永炫，林琛，等.云數據庫研究[J].軟件學報，2012，34（5）：1148-1166.

[2] CORMODE G. Count-min sketch[J]. Encyclopedia of Algorithms， 2009，29（1）：64-69.

[3] FAN B， KAMINSKY M， ANDERSEN D G. Cuckoo filter： better than bloom[J].The magazine of USENIX & SAGE， 2013，38：36-40.

[4] 呂健波，戴冠中，慕德俊.絕對延遲保證在Web應用服務器數據庫連接池中的實現(xiàn)[J].計算機應用研究，2012，29（5）：1838-1841.

[5] 劉元珍.Bloom filter及其在網絡中的應用綜述[J].計算機應用與軟件，2013（9）：219-220.

[6] 徐愛萍，王波，張煦.基于Hbase的時空大數據關聯(lián)查詢優(yōu)化[J].計算機應用與軟件，2017，34（6）：37-42.

[7] 羅軍，陳席林，李文生.高效Key-Value持久化緩存系統(tǒng)的實現(xiàn)[J].計算機工程，2014，40（3）：33-38.

[8] BHUSHAN M， BANERJEA S， YADAV S K. Bloom filter based optimization on Hbase with MapReduce[C].International Conference on Data Mining and Intelligent Computing. IEEE， 2014：1-5.

[9] 李文昊.基于確定性執(zhí)行策略的分布式數據庫中間件的設計與實現(xiàn)[D].太原：太原理工大學，2016.

[10] 王韌，朱金連，周亮，等.中間件技術在移動應用數據庫開發(fā)中的運用[J].電子設計工程，2015（2）：170-172.

[11] MOSHARRAF N， JAYASUMANA A P， RAY I. Compacted bloom filter[C].International Conference on Collaboration and Internet Computing. IEEE， 2017：304-311.

[12] 馮鋒，吳杰.基于Bloom filter的RFID中間件數據過濾算法研究[J].計算機應用研究，2015（5）：1441-1444.

[13] 張進，鄔江興，劉勤讓.4種計數型Bloom filter的性能分析與比較[J].軟件學報，2010，21（5）：1098-1114.

[14] MOSHARRAF N， JAYASUMANA A P， RAY I. Compacted bloom filter[C]. IEEE， International Conference on Collaboration and Internet Computing. IEEE， 2017：304-311.

（責任編輯：黃 ?。?/p>