基于Bloomfilter降低云數(shù)據(jù)庫(kù)網(wǎng)絡(luò)延時(shí)的影響

劉淑平 李仲游

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

關(guān)鍵詞：云數(shù)據(jù)庫(kù)；Bloom filter；Redis；網(wǎng)絡(luò)延時(shí)

DOIDOI：10.11907/rjdk.181296

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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.

英文關(guān)鍵詞Key Words：cloud database；Bloom filter； Redis；network delay

0 引言

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

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

1 相關(guān)技術(shù)

1.1 Bloom filter

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

1.1.1 標(biāo)準(zhǔn)Bloom filter原理

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

1.1.2 初始化操作

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

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

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

1.1.3 數(shù)據(jù)存在檢驗(yàn)

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

1.2 Redis

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

2 問題分析

2.1 網(wǎng)絡(luò)延時(shí)原因分析

以國(guó)內(nèi)某云廠商為例，如圖1所示，所有的數(shù)據(jù)庫(kù)請(qǐng)求都需要通過ECS（服務(wù)器端）傳輸?shù)絉DS（云數(shù)據(jù)庫(kù)端）。其中有多個(gè)環(huán)節(jié)，包括：ECS（云主機(jī)）→DNS→SLB→Proxy→RDS（云數(shù)據(jù)庫(kù)），而ECS自建數(shù)據(jù)庫(kù)是ECS→ECS，RDS的網(wǎng)絡(luò)鏈路比ECS自建數(shù)據(jù)庫(kù)多3個(gè)網(wǎng)絡(luò)鏈路環(huán)節(jié)。這些網(wǎng)絡(luò)鏈路的網(wǎng)絡(luò)延時(shí)即為RDS對(duì)外服務(wù)的網(wǎng)絡(luò)延時(shí)。為了簡(jiǎn)化測(cè)算，本文采用ECS到RDS服務(wù)的SLB網(wǎng)絡(luò)延時(shí)作為網(wǎng)絡(luò)延時(shí)，RDS內(nèi)部網(wǎng)絡(luò)延時(shí)對(duì)外視作透明。

2.2 網(wǎng)絡(luò)延時(shí)測(cè)算

2.2.1 測(cè)算環(huán)境

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

（2）云數(shù)據(jù)庫(kù)：阿里云RDS（通用型）。具體配置如下：CPU為1 核，內(nèi)存為1GB（單機(jī)基礎(chǔ)版），硬盤為20GB，數(shù)據(jù)庫(kù)為MySQL 5.7。

2.2.2 測(cè)試方式

具體測(cè)試步驟如下：

（1）在數(shù)據(jù)庫(kù)中建立測(cè)試庫(kù)test，test下建立測(cè)試表user_login。以12位定長(zhǎng)int數(shù)據(jù)結(jié)構(gòu)字段id為主鍵，45位不定長(zhǎng)數(shù)據(jù)結(jié)構(gòu)字段str作為模擬用戶登錄表。

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

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

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

（5）通過Linux自帶的ping命令每隔1s采集一次ECS到SLB的延時(shí)，采集時(shí)長(zhǎng)為86 400s（24h整），網(wǎng)絡(luò)延時(shí)數(shù)據(jù)如表3所示。

（6）為了簡(jiǎn)化實(shí)驗(yàn)，利用Python實(shí)現(xiàn)Bloom filter算法并測(cè)試Bloom filter性能，對(duì)應(yīng)Bloom filter（1 000w次測(cè)試性能）數(shù)據(jù)如表4所示。

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

3 登錄模塊改進(jìn)方案

3.1 模塊改進(jìn)方案

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

3.2 模塊改進(jìn)方案性能測(cè)試

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

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

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

4 結(jié)語(yǔ)

本文針對(duì)采用云數(shù)據(jù)庫(kù)解決方案改善登錄模塊運(yùn)行

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

參考文獻(xiàn)：

[1] 林子雨，賴永炫，林琛，等.云數(shù)據(jù)庫(kù)研究[J].軟件學(xué)報(bào)，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] 呂健波，戴冠中，慕德俊.絕對(duì)延遲保證在Web應(yīng)用服務(wù)器數(shù)據(jù)庫(kù)連接池中的實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用研究，2012，29（5）：1838-1841.

[5] 劉元珍.Bloom filter及其在網(wǎng)絡(luò)中的應(yīng)用綜述[J].計(jì)算機(jī)應(yīng)用與軟件，2013（9）：219-220.

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

[7] 羅軍，陳席林，李文生.高效Key-Value持久化緩存系統(tǒng)的實(shí)現(xiàn)[J].計(jì)算機(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í)行策略的分布式數(shù)據(jù)庫(kù)中間件的設(shè)計(jì)與實(shí)現(xiàn)[D].太原：太原理工大學(xué)，2016.

[10] 王韌，朱金連，周亮，等.中間件技術(shù)在移動(dòng)應(yīng)用數(shù)據(jù)庫(kù)開發(fā)中的運(yùn)用[J].電子設(shè)計(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中間件數(shù)據(jù)過濾算法研究[J].計(jì)算機(jī)應(yīng)用研究，2015（5）：1441-1444.

[13] 張進(jìn)，鄔江興，劉勤讓.4種計(jì)數(shù)型Bloom filter的性能分析與比較[J].軟件學(xué)報(bào)，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.

（責(zé)任編輯：黃 ?。?/p>