作者 ｜ 一十，攜程資深后端開發(fā)工程師;振青，攜程高級(jí)后端開發(fā)專家。

一、前言

攜程酒店查詢服務(wù)是酒店BU后端的核心服務(wù)，主要負(fù)責(zé)提供所有酒店動(dòng)態(tài)數(shù)據(jù)計(jì)算的統(tǒng)一接口。在處理請(qǐng)求的過程中，需要使用到酒店基礎(chǔ)屬性信息、價(jià)格信息等多維度的數(shù)據(jù)信息。為了保證服務(wù)的響應(yīng)性能，酒店查詢服務(wù)對(duì)所有在請(qǐng)求過程中需要使用到的相關(guān)數(shù)據(jù)進(jìn)行了緩存。隨著攜程酒店業(yè)務(wù)的發(fā)展，查詢服務(wù)目前在保證數(shù)據(jù)最終一致性以及增量秒級(jí)更新延遲的情況下，在包括服務(wù)器本地內(nèi)存以及Redis等多種介質(zhì)上緩存了百億級(jí)的數(shù)據(jù)。

本文將主要討論酒店查詢服務(wù)技術(shù)團(tuán)隊(duì)是如何在保證讀取效率的前提下，針對(duì)存儲(chǔ)在服務(wù)器本地的緩存數(shù)據(jù)進(jìn)行存儲(chǔ)結(jié)構(gòu)選型以及優(yōu)化的過程。

二、內(nèi)存結(jié)構(gòu)選型

為了尋找合適的內(nèi)存結(jié)構(gòu)以達(dá)到理想的效果，本節(jié)將詳細(xì)探討在通用數(shù)據(jù)查詢場景下，不同類型的數(shù)據(jù)結(jié)構(gòu)的可行性與優(yōu)劣勢(shì)。

2.1 緩存結(jié)構(gòu)的基礎(chǔ)需求

2.1.1 支持高性能讀取

在大部分應(yīng)用場景下，之所以需要在服務(wù)器內(nèi)存中存儲(chǔ)緩存數(shù)據(jù)，是因?yàn)檎?qǐng)求處理過程中需要高頻次讀取各類數(shù)據(jù)。為了保證服務(wù)的響應(yīng)性能，我們有的時(shí)候會(huì)選擇將數(shù)據(jù)提前存儲(chǔ)在本地內(nèi)存，利用空間換取時(shí)間。酒店查詢服務(wù)就有這樣的需求：服務(wù)平均每次請(qǐng)求需要讀取數(shù)據(jù)上千次，同時(shí)對(duì)響應(yīng)時(shí)間也有著嚴(yán)格的要求。因此，在這種高頻次訪問緩存的場景下，對(duì)數(shù)據(jù)的查找性能便有著極高的要求。

在常見的數(shù)據(jù)結(jié)構(gòu)中，數(shù)組和散列表都能提供O(1)的查詢速度，是不考慮其他因素下最高性能的選擇。查找復(fù)雜度為O(log2N)的樹則其次，其查找速度和數(shù)據(jù)規(guī)模有關(guān)，一般只能在數(shù)據(jù)規(guī)模很小的場景下選用。

2.1.2 支持高更新頻率

在實(shí)際應(yīng)用場景下，生產(chǎn)環(huán)境的緩存數(shù)據(jù)必然有新鮮度要求。面對(duì)海量數(shù)據(jù)，高頻度的數(shù)據(jù)更新幾乎無可避免。特別是像價(jià)格這類數(shù)據(jù)，一方面更改頻次極高，另一方面又必須保證新的增量數(shù)據(jù)可以在秒級(jí)內(nèi)快速同步至緩存中。這就要求所使用的緩存數(shù)據(jù)結(jié)構(gòu)必須支持高性能并發(fā)讀寫的場景。如果隨意的使用鎖機(jī)制或是線程不安全的存儲(chǔ)結(jié)構(gòu)都會(huì)可能導(dǎo)致一些預(yù)期外的問題與風(fēng)險(xiǎn)：

1)并發(fā)更改風(fēng)險(xiǎn)

眾所周知，Java提供實(shí)現(xiàn)的最常用的散列表HashMap是非線程安全的數(shù)據(jù)結(jié)構(gòu)。若直接使用該類作為緩存結(jié)構(gòu)，則在并發(fā)讀寫時(shí)就可能會(huì)因?yàn)橹匦翲ash而讀到錯(cuò)誤的數(shù)據(jù)，甚至在極端情況下產(chǎn)生死循環(huán)的問題。

2)濫用讀寫鎖

在頻繁并發(fā)更新與讀取的場景下，錯(cuò)誤的鎖機(jī)制很有可能導(dǎo)致在高頻次寫入時(shí)直接卡死應(yīng)用處理請(qǐng)求時(shí)的高頻次讀取，進(jìn)而產(chǎn)生大量請(qǐng)求排隊(duì)以及其他問題。

因此，高更新頻率需求所帶來的線程安全問題，導(dǎo)致大部分的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)都無法適用于存儲(chǔ)生產(chǎn)緩存數(shù)據(jù)。在絕大部分情況下，都需要犧牲一部分性能選擇線程安全的數(shù)據(jù)結(jié)構(gòu)。當(dāng)然，對(duì)于某些特殊場景，也可根據(jù)需要來設(shè)計(jì)定制化的結(jié)構(gòu)與鎖機(jī)制來達(dá)到更優(yōu)的性能。

經(jīng)過上面的簡單分析后，我們可以暫時(shí)認(rèn)為線程安全的數(shù)組和散列表是一個(gè)較優(yōu)的用以承載緩存數(shù)據(jù)的結(jié)構(gòu)。

2.2 低空間開銷的結(jié)構(gòu)選型

由于實(shí)際應(yīng)用的內(nèi)存都是有限的，因此在保障讀寫性能的同時(shí)，我們也需要思考如何降低緩存所消耗的內(nèi)存資源。為了保證服務(wù)正常的響應(yīng)請(qǐng)求，酒店查詢服務(wù)需要在本地存儲(chǔ)千萬量級(jí)的數(shù)據(jù)，而緩存能夠在虛擬機(jī)上使用的內(nèi)存空間卻非常有限。因此，除了對(duì)數(shù)據(jù)本身進(jìn)行過濾等預(yù)處理之外，用以存儲(chǔ)數(shù)據(jù)的通用結(jié)構(gòu)的內(nèi)存開銷也要盡可能的小。

在對(duì)不同數(shù)據(jù)結(jié)構(gòu)進(jìn)行分析前，我們需要從最基礎(chǔ)的問題開始：Java中的一個(gè)對(duì)象是以何種結(jié)構(gòu)存儲(chǔ)在內(nèi)存里的?

2.2.1 Java對(duì)象內(nèi)存結(jié)構(gòu)模型

一個(gè)Java對(duì)象在內(nèi)存中的存儲(chǔ)結(jié)構(gòu)通常包括對(duì)象頭、實(shí)例數(shù)據(jù)與對(duì)齊填充。

對(duì)象頭

對(duì)象頭用于存儲(chǔ)對(duì)象的標(biāo)記位(Mark Word)與類型指針(Class Pointer)。

標(biāo)記位里存儲(chǔ)了包含鎖狀態(tài)與GC標(biāo)記位等信息，其在32位系統(tǒng)上占存4字節(jié)而在64位系統(tǒng)上占存8字節(jié)。

類型指針是一個(gè)對(duì)象指向它元數(shù)據(jù)的指針，因此，其在32位系統(tǒng)上占存4字節(jié)，在64位系統(tǒng)上占存8字節(jié)。同時(shí)，若在64位機(jī)器上開啟指針壓縮參數(shù)-XX:UseCompressedOops，則此時(shí)類型指針在對(duì)象頭中僅占存4字節(jié)。

另外，若實(shí)體為數(shù)組，則會(huì)額外有4個(gè)字節(jié)用以存儲(chǔ)該數(shù)組的長度。

實(shí)例數(shù)據(jù)

實(shí)例數(shù)據(jù)內(nèi)部存儲(chǔ)了對(duì)象所定義的所有成員變量。這些成員變量會(huì)緊密排列，若對(duì)象是由子類創(chuàng)建的，則其父類的成員變量也會(huì)包含在其中。若成員變量為NULL值，則不會(huì)給該成員變量申請(qǐng)指針空間。

對(duì)齊填充

若對(duì)象所申請(qǐng)的內(nèi)存空間不是8的倍數(shù)，則JVM會(huì)添加合適的對(duì)齊填充使得整個(gè)對(duì)象所申請(qǐng)的空間為8的倍數(shù)。

綜上，若一個(gè)簡單實(shí)例對(duì)象內(nèi)部存儲(chǔ)一個(gè)int字段以及一個(gè)byte字段，那么在開啟指針壓縮的64位機(jī)器上其占存應(yīng)為24字節(jié)。其中包含對(duì)象頭的8字節(jié)標(biāo)識(shí)位與4字節(jié)類型指針、內(nèi)部字段int的4字節(jié)與byte的1字節(jié)以及對(duì)齊填充7字節(jié)。

2.2.2 原生HashMap結(jié)構(gòu)內(nèi)存開銷

基于上述的Java實(shí)例內(nèi)存結(jié)構(gòu)的基礎(chǔ)理論，我們將以HashMap為主要示例，詳細(xì)探討JDK原生HashMap內(nèi)部結(jié)構(gòu)以及其內(nèi)存開銷。

下表是一個(gè)簡單的實(shí)驗(yàn)結(jié)果。我們統(tǒng)計(jì)了在開啟指針壓縮的64位機(jī)器上，不同數(shù)據(jù)條數(shù)的鍵值類型均為Integer的HashMap的內(nèi)存占存。作為參考，我們將其所存儲(chǔ)的所有Integer實(shí)例的占存視作數(shù)據(jù)占存，將剩余的占存視作結(jié)構(gòu)占存。從下表的實(shí)驗(yàn)結(jié)果來看，無論在何種數(shù)據(jù)規(guī)模下，HashMap內(nèi)部結(jié)構(gòu)的內(nèi)存開銷占比都很高，占到了整體的55%以上。

需要知道此類現(xiàn)象的成因還是需要從HashMap內(nèi)部存儲(chǔ)結(jié)構(gòu)為入手點(diǎn)進(jìn)行分析。如下圖所示，HashMap主要由一個(gè)哈希桶數(shù)組及多個(gè)存儲(chǔ)在哈希桶中的節(jié)點(diǎn)Node所構(gòu)成。

下面我們來分別具體解析一下哈希桶數(shù)組table和數(shù)據(jù)節(jié)點(diǎn)Node的內(nèi)存開銷。

哈希桶數(shù)組table

哈希桶數(shù)組實(shí)際是用于存儲(chǔ)數(shù)據(jù)節(jié)點(diǎn)Node的數(shù)組。程序?qū)⒏鶕?jù)數(shù)據(jù)Key的HashCode運(yùn)算得到數(shù)據(jù)節(jié)點(diǎn)Node實(shí)際應(yīng)存儲(chǔ)在哈希桶數(shù)組的哪一個(gè)下標(biāo)位置。通過哈希桶打散數(shù)據(jù)后，程序可以通過Key快速的查找到實(shí)際數(shù)據(jù)節(jié)點(diǎn)。其在源碼中實(shí)際定義如下：

那么，在內(nèi)存結(jié)構(gòu)上，哈希桶就是由一個(gè)附帶數(shù)組長度的對(duì)象頭和數(shù)組元素集合組成。因此，一個(gè)長度為N的哈希桶數(shù)組的占存大小就會(huì)是：

8(對(duì)象頭標(biāo)識(shí)位)+ 4(類型指針)+ 4(數(shù)組長度 + 4 (實(shí)體引用)*N (實(shí)體數(shù)量)字節(jié) + 對(duì)齊字節(jié)。即，長度為32的哈希桶數(shù)組則實(shí)際占存即為16 + 4 *32 = 144字節(jié)。

為了提升讀寫性能，HashMap中哈希桶數(shù)組的實(shí)際長度并不會(huì)總是等于實(shí)際存儲(chǔ)的數(shù)據(jù)量。哈希桶數(shù)組的實(shí)際長度在兩個(gè)時(shí)候會(huì)產(chǎn)生變化：

1)初始化

在HashMap進(jìn)行實(shí)例創(chuàng)建的時(shí)候，程序會(huì)按照所指定的容量(默認(rèn)為16)向上取最接近的2的整數(shù)冪作為實(shí)際初始化容量。該容量也是哈希桶數(shù)組的長度。比如外部創(chuàng)建一個(gè)指定容量為100的HashMap，則其內(nèi)部哈希桶數(shù)組的實(shí)際初始長度為128。

2)擴(kuò)容

HashMap為了確保其讀寫效率，當(dāng)內(nèi)部數(shù)據(jù)量到達(dá)一定規(guī)模時(shí)，會(huì)進(jìn)行擴(kuò)容操作。而其負(fù)載因子和當(dāng)前哈希桶數(shù)組的長度二者相乘所得出的擴(kuò)容閾值決定了擴(kuò)容前在哈希表內(nèi)部最大元素?cái)?shù)量。例如，一個(gè)容量為32、負(fù)載因子為默認(rèn)的0.75的HashMap的擴(kuò)容閾值即為32*0.75=24。那么，當(dāng)此HashMap被插入24條數(shù)據(jù)后，其內(nèi)部的原先32長的哈希桶數(shù)組就會(huì)被擴(kuò)容至原長度的2倍64。

綜合上述的哈希桶長度策略，其實(shí)可以很明顯的看到HashMap所存儲(chǔ)的哈希桶實(shí)體數(shù)組在絕大部分情況下總是會(huì)將冗余出比實(shí)際數(shù)據(jù)量多一些的空間，以減少哈希碰撞、提升讀取效率。

下表是在不同數(shù)據(jù)規(guī)模下哈希桶數(shù)組相對(duì)于普通實(shí)體數(shù)組，冗余的數(shù)組長度及其額外的開銷。

那么依據(jù)上面的理論，我們就可以推算出不同數(shù)據(jù)量的HashMap中哈希桶數(shù)組的內(nèi)存開銷及其占比。

數(shù)據(jù)節(jié)點(diǎn)Node

Node類繼承于 Map.Entry，是HashMap中存儲(chǔ)數(shù)據(jù)的基本單元。其內(nèi)部除了存儲(chǔ)了鍵值對(duì)數(shù)據(jù)外，同時(shí)存儲(chǔ)了節(jié)點(diǎn)的哈希值以及是當(dāng)其在鏈表或紅黑樹中時(shí)，其下個(gè)Node節(jié)點(diǎn)的引用。

那么，我們可以依據(jù)其內(nèi)部結(jié)構(gòu)如計(jì)算出一個(gè)Node實(shí)例的字節(jié)數(shù)為32個(gè)字節(jié)。若要使用Node存儲(chǔ)32個(gè)Integer鍵值對(duì)，那么所有32個(gè)節(jié)點(diǎn)實(shí)體一共要占用1024個(gè)字節(jié)。

那么我們可以在前面的實(shí)驗(yàn)數(shù)據(jù)中再添加上Node的數(shù)據(jù)，得到完整的HashMap內(nèi)存開銷各部分的占比：

所以，在原生HashMap消耗了大量的額外空間結(jié)構(gòu)換取其讀寫性能。這使得原生HashMap在大數(shù)據(jù)量且內(nèi)存有限的應(yīng)用上，并不是一個(gè)最優(yōu)的緩存結(jié)構(gòu)選型。

2.2.3 包裝類型損耗

由于Java的泛型機(jī)制，絕大部分的數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)的類型只能聲明為包裝類。因此，即使需要存儲(chǔ)是整型等基礎(chǔ)類型，也將其不得不轉(zhuǎn)換為對(duì)應(yīng)的包裝類型來存儲(chǔ)在內(nèi)存中。這不僅會(huì)有存取時(shí)產(chǎn)生額外的裝拆箱的性能損耗，存儲(chǔ)包裝類相較基礎(chǔ)類型也會(huì)產(chǎn)生更大的內(nèi)存開銷。以實(shí)際應(yīng)用場景中最為常見的整型為例，我們將簡單比較一下Integer[] 和int[] 這兩種數(shù)組的內(nèi)存大小差異。

Integer[]

由于Integer是包裝類，因此數(shù)組中存儲(chǔ)的實(shí)際是4字節(jié)長的Integer的引用。而對(duì)于一個(gè)Integer實(shí)例本身來說，參考前文所述，除了4字節(jié)的實(shí)際數(shù)據(jù)外，其還需要12字節(jié)來保存其對(duì)象頭。所以在集合中要保存一個(gè)Integer的實(shí)際開銷就會(huì)是4 + 12 + 4 = 20字節(jié)。

int[]

基礎(chǔ)類型的int[]則簡單的多：在創(chuàng)建數(shù)組時(shí)，僅需為每個(gè)元素開辟4字節(jié)來保存整型即可。

所以，理論上每個(gè)Integer都會(huì)比int額外產(chǎn)生16字節(jié)的內(nèi)存開銷 。從實(shí)驗(yàn)結(jié)果可以看出，若我們可以直接使用基礎(chǔ)類型來代替包裝類存儲(chǔ)時(shí)，可以大幅減少內(nèi)存占存。此結(jié)論對(duì)其他如HashMap等數(shù)據(jù)結(jié)構(gòu)也同樣有效。

2.2.4 其他結(jié)構(gòu)選型

為了在保證讀寫性能的情況下盡可能壓縮內(nèi)存開銷，我們調(diào)研了一些第三方的開源集合框架來嘗試在內(nèi)存和性能上盡可能取得平衡。

ConcurrentHashMap

ConcurrentHashMap是HashMap的線程安全版本，內(nèi)部也是使用數(shù)組、鏈表與紅黑樹的結(jié)構(gòu)來存儲(chǔ)元素。相較于同樣JDK中線程安全的HashTable來說，其鎖競爭更少、讀寫效率更高。

SparseArray

SparseArray即稀疏數(shù)組，是Android提供的建議替換HashMap的用來存儲(chǔ)整型類型對(duì)象鍵值對(duì)的類。其內(nèi)部主要使用了數(shù)組作為存儲(chǔ)方式，比HashMap要高效輕量。

Guava Cache

Guava Cache是google開源的一款本地緩存工具庫。其使用多個(gè)segments方式的細(xì)粒度鎖，提供了支持高并發(fā)場景的線程安全的存儲(chǔ)結(jié)構(gòu)。

fastutil

FastUtil是一個(gè)高性能的集合框架，提供了以基礎(chǔ)類型為元素的集合來代替JDK原生的集合類型。基礎(chǔ)類型為元素的集合避免了大量的基礎(chǔ)類型的裝箱拆箱。因此，在程序進(jìn)行集合的遍歷、根據(jù)索引獲取元素的值和設(shè)置元素的值的時(shí)候，fastutil可以提供更快的存取速度以及更低的內(nèi)存消耗。

我們實(shí)驗(yàn)了整型鍵值對(duì)不同數(shù)據(jù)規(guī)模下各個(gè)集合的內(nèi)存占比，并且用HashMap的數(shù)據(jù)作為基準(zhǔn)進(jìn)行橫向比較。實(shí)驗(yàn)結(jié)果具體數(shù)據(jù)如下所示。

三、數(shù)據(jù)編碼壓縮

在實(shí)際應(yīng)用場景下，幾乎所有需要緩存的數(shù)據(jù)都有著比較高的重復(fù)率或是其他分布規(guī)律。在內(nèi)存結(jié)構(gòu)選型的基礎(chǔ)上，針對(duì)于不同的數(shù)據(jù)特征，我們可以采用不同的數(shù)據(jù)編碼壓縮方式對(duì)數(shù)據(jù)進(jìn)行壓縮處理，進(jìn)一步降低緩存的內(nèi)存開銷。

下面，我們將介紹幾種常用有效的數(shù)據(jù)編碼壓縮方式。

3.1 常用編碼技術(shù)

3.1.1 位圖編碼

位圖(BitMap)是一種常見的編碼格式，JDK中提供的默認(rèn)實(shí)現(xiàn)為BitSet類。它是用Bit位來存儲(chǔ)數(shù)據(jù)的某種狀態(tài)，通常指示是非有無。在最常見的情況下，當(dāng)需要存儲(chǔ)大量連續(xù)ID是否為True時(shí)，用到此類結(jié)構(gòu)就可以大量減少內(nèi)存的開銷。

在下例中，需要存儲(chǔ)的數(shù)據(jù)的Key為整型， Value為該Key是否有效的狀態(tài)數(shù)據(jù)。若是直接存儲(chǔ)，則一條數(shù)據(jù)至少需要4個(gè)字節(jié)用于存儲(chǔ)整型Key以及4個(gè)字節(jié)用于存儲(chǔ)布爾型的狀態(tài)值。那么，當(dāng)需要存儲(chǔ)Key從1至8的8條數(shù)據(jù)，則至少需要64字節(jié)。若使用位圖編碼技術(shù)對(duì)數(shù)據(jù)進(jìn)行處理，那么我們僅需要1個(gè)bit即可存儲(chǔ)一個(gè)True or False的狀態(tài)信息。因此，就可以使用1個(gè)字節(jié)存儲(chǔ)下所有8條數(shù)據(jù)的狀態(tài)信息。此時(shí)，該字節(jié)的第1位的bit用以表示Key = 1的狀態(tài)信息，第2位的bit用以Key = 2的狀態(tài)信息，以此類推。

下表是在64位機(jī)器上開啟指針壓縮后， Java原生HashMap與BitSet的耗存對(duì)照表。可以明顯地看出，整體壓縮效率是非常高的。在實(shí)際業(yè)務(wù)場景下，只要整型Key分布相對(duì)密集，就可以利用位圖編碼達(dá)到不錯(cuò)的壓縮效果。

另外，位圖編碼還可以額外擴(kuò)展至一些類型較少的枚舉類型上。例如，枚舉類Season只有4種元素，則可以使用2個(gè)bit來代表一個(gè)屬性，那么則只需8bit即可存儲(chǔ)id從1-4的 4個(gè)Season枚舉。

enumSeason{ Spring,Summer,Fall,Winter;}

3.1.2 游程編碼

游程編碼(Run-length encoding，RLE)是一種無損壓縮數(shù)據(jù)的編碼方式，主要方法是使用當(dāng)前數(shù)據(jù)元素以及該元素連續(xù)出現(xiàn)的次數(shù)來取代數(shù)據(jù)中連續(xù)出現(xiàn)的部分。若數(shù)據(jù)存在大量的數(shù)據(jù)連續(xù)且重復(fù)的情況，就可以考慮使用RLE以降低內(nèi)存。

比如，一個(gè)內(nèi)部存儲(chǔ)了4個(gè)連續(xù)的a與6個(gè)連續(xù)的b的字符串經(jīng)過游程編碼后為a4b6。那么，該字符串長度就從10字節(jié)減少至4字節(jié)。

3.1.3 字典編碼

字典編碼是把整體重復(fù)性高的數(shù)據(jù)進(jìn)行去重后建立字典，把原來存放數(shù)據(jù)的地方變?yōu)橹赶驅(qū)嶓w字典引用的編碼方式。因?yàn)橐弥羔樢廊徽即?，因此適合單個(gè)的實(shí)例數(shù)據(jù)字段較多的數(shù)據(jù)緩存。

下例為原始數(shù)據(jù)為整型Key查詢長字符串Value的場景。首先，將重復(fù)的字符串實(shí)體數(shù)據(jù)提取出來，將其單獨(dú)作為一個(gè)實(shí)體字典進(jìn)行存儲(chǔ)。該字典Key為一個(gè)指針，Value則為提取出的不重復(fù)的字符串?dāng)?shù)據(jù)。然后，原始字典的Value就可以變?yōu)橐粋€(gè)指針，指向新實(shí)體字典的Key。當(dāng)需要查詢Key1內(nèi)實(shí)際數(shù)據(jù)的時(shí)候，先在原始字典中查詢到引用Ref1，再在實(shí)體字典查詢Ref1即可獲得其Value值aaaa。

3.1.4 差值編碼

差值編碼是對(duì)于非連續(xù)的數(shù)據(jù)Key通過差值計(jì)算的方式轉(zhuǎn)化為連續(xù)的Key，讓字典可以轉(zhuǎn)化為數(shù)組的編碼方式。

下例中的數(shù)據(jù)Key為日期，Value為一個(gè)整型。在日期相對(duì)連續(xù)的情況下，取所有日期的最小值為開始日期，以數(shù)據(jù)生效日期到開始日期的差值為新字典的Key。那么編碼前舊數(shù)據(jù)字典的Key為Date類型，而編碼后的新數(shù)據(jù)字典的類型則可以轉(zhuǎn)化為更小更泛用的int型。

下表是在N天連續(xù)的日期查整型的場景下，原生HashMap與編碼后整型數(shù)組的耗存對(duì)照表。即使連續(xù)的日期數(shù)量較小，也可以看出整體存在的巨大差距。在實(shí)際的應(yīng)用場景下，此類編碼方式一般用于連續(xù)日期的緩存，也可以擴(kuò)展到其他有著類似數(shù)據(jù)特征的緩存上。

以上的編碼技術(shù)可以在不同的數(shù)據(jù)場景下進(jìn)行組合使用，接下來我們將簡要的展示兩個(gè)實(shí)際酒店查詢服務(wù)緩存內(nèi)存壓縮優(yōu)化的案例。

3.2 應(yīng)用案例

3.2.1 房型基礎(chǔ)信息

查詢服務(wù)緩存了上億條房型信息數(shù)據(jù)。在請(qǐng)求處理過程中，服務(wù)可以在緩存中通過房型ID查詢到該房型的信息。因?yàn)閿?shù)據(jù)條數(shù)上億且實(shí)體內(nèi)部字段很多，因此未優(yōu)化的緩存在內(nèi)存中占存高達(dá)上百GB，是一個(gè)較大的內(nèi)存性能瓶頸。

因此，針對(duì)該緩存，我們使用了位圖編碼以及字典編碼，大幅降低了其內(nèi)存開銷。

1)使用位圖編碼對(duì)可枚舉字段進(jìn)行數(shù)據(jù)壓縮

我們將房型數(shù)據(jù)實(shí)體上包括布爾型、枚舉以及部分字符串等所有可以枚舉的字段進(jìn)行了位圖編碼，大幅降低了單個(gè)實(shí)體的占存大小。比如在下方作為例子的字段中，RoomType雖然存儲(chǔ)為一個(gè)String，但是在實(shí)際業(yè)務(wù)場景中它一共只有5種取值可能性，因此也可以作為枚舉類進(jìn)行處理為3個(gè)bit。

在原先存儲(chǔ)方式的情況下，示例的一個(gè)房型實(shí)體字段就至少需要16字節(jié)，通過位圖編碼后一個(gè)房型實(shí)體字段實(shí)際僅需要10個(gè)bit即可無損的存儲(chǔ)下所有有效信息。

2)使用字典編碼對(duì)重復(fù)實(shí)體進(jìn)行壓縮

經(jīng)過線上數(shù)據(jù)統(tǒng)計(jì)與分析，我們發(fā)現(xiàn)部分房型屬性數(shù)據(jù)的重復(fù)率達(dá)到99%。也就是說，雖然存在上億個(gè)房型，但是實(shí)際去重后的房型的部分基礎(chǔ)信息實(shí)體只有百萬級(jí)。因此，在對(duì)房型基礎(chǔ)信息實(shí)體本身進(jìn)行位圖編碼的同時(shí)，我們采用了字典編碼的方式對(duì)房型ID不同但內(nèi)部字段信息完全重復(fù)的數(shù)據(jù)實(shí)體進(jìn)行字典編碼，以壓縮這部分的消耗。

在實(shí)際處理過程中，我們會(huì)先將房型數(shù)據(jù)實(shí)體進(jìn)行序列化后轉(zhuǎn)換為MD5，在房型字典中只存儲(chǔ)MD5編碼，而實(shí)體字典中存儲(chǔ)MD5到實(shí)際房型信息實(shí)體的關(guān)系。在進(jìn)行數(shù)據(jù)查詢時(shí)，則是先通過房型ID在房型字典中查找到對(duì)應(yīng)的MD5值，然后在實(shí)體字典中通過MD5值查找到對(duì)應(yīng)的房型基礎(chǔ)信息實(shí)體。

經(jīng)過上述兩個(gè)編碼壓縮優(yōu)化后，房型實(shí)體緩存占存整體壓縮率達(dá)到2%以下，節(jié)省了數(shù)十GB的內(nèi)存空間。

3.2.2 單天房價(jià)信息

單天房價(jià)信息緩存是存儲(chǔ)每個(gè)房型每日價(jià)格的緩存，是查詢服務(wù)數(shù)據(jù)量最大同時(shí)也是最核心的數(shù)據(jù)緩存。在應(yīng)用請(qǐng)求處理過程中，會(huì)使用房型ID以及日期從該緩存中獲取房型某一天的價(jià)格數(shù)據(jù)。

下面將以單房型下存儲(chǔ)的日期信息為例，逐步展示數(shù)據(jù)壓縮優(yōu)化的全部過程。

1)使用字典編碼對(duì)每日重復(fù)的價(jià)格信息進(jìn)行編碼

首先，將所有該房型上出現(xiàn)的價(jià)格提取并存儲(chǔ)到一個(gè)價(jià)格數(shù)組上，在數(shù)據(jù)字典里則存儲(chǔ)實(shí)際價(jià)格數(shù)據(jù)在價(jià)格字典的索引。同時(shí)，因?yàn)榇嬖诳赡軟]有數(shù)據(jù)的日期，因此Null值被存儲(chǔ)在所有價(jià)格數(shù)組上的第一個(gè)偏移index上，作為默認(rèn)值。

2)使用差值編碼處理日期

因?yàn)樵诮^大部分情況下，數(shù)據(jù)字典中的日期均為連續(xù)的，且從業(yè)務(wù)場景上來說最大的日期也不會(huì)過大，因此我們采用差值編碼處理日期，將數(shù)據(jù)字典中的日期替換為與服務(wù)器啟動(dòng)日期之間相差天數(shù)的偏移量。此時(shí)，數(shù)據(jù)字典的Key則會(huì)變?yōu)橐粋€(gè)從0開始的int，那么就可以使用占存更小的數(shù)組來表示這個(gè)數(shù)據(jù)字典。該數(shù)據(jù)索引數(shù)組為一個(gè)int[]，其下標(biāo)表示日期偏移，值表示到價(jià)格字典的索引。

3)使用位圖編碼處理可枚舉的價(jià)格索引

因?yàn)閱蝹€(gè)房型下的價(jià)格數(shù)量是有限的，因此同樣可以視作是枚舉值的一種。對(duì)枚舉值，就可以使用位圖編碼對(duì)數(shù)據(jù)索引數(shù)組進(jìn)行壓縮。在下圖的數(shù)據(jù)樣例中，因?yàn)閮r(jià)格數(shù)組長度為3，即存在3種可能的價(jià)格，因此將int轉(zhuǎn)換為2個(gè)bit進(jìn)行存儲(chǔ)，則位圖的一天的偏移步長為2。

4)使用RLE編碼處理末尾

在很多房型下的到天價(jià)格數(shù)據(jù)，在距離現(xiàn)在最遠(yuǎn)的日期帶的價(jià)格通常都是重復(fù)的，因此，我們可以使用RLE的方式對(duì)末尾重復(fù)的數(shù)據(jù)進(jìn)行截尾，來進(jìn)一步壓縮數(shù)據(jù)位圖大小。

在所舉的例子中，其在內(nèi)存中單對(duì)象實(shí)例數(shù)據(jù)部分的內(nèi)存可以從最初的數(shù)百字節(jié)降低至最終的31字節(jié)。而在實(shí)際業(yè)務(wù)場景中，該單天房價(jià)數(shù)據(jù)經(jīng)過壓縮處理后實(shí)際壓縮率為60%左右。

四、總結(jié)

本文主要介紹了攜程酒店查詢服務(wù)在本地緩存數(shù)據(jù)結(jié)構(gòu)選型以及優(yōu)化方面的探索與實(shí)際應(yīng)用案例。

在常規(guī)緩存數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)選型上，我們先根據(jù)緩存場景的需求，分析比較了不同數(shù)據(jù)結(jié)構(gòu)后，選擇線程安全的Map結(jié)構(gòu)作為基礎(chǔ)研究方向。然后基于Java對(duì)象占存的原理，以原生HashMap為實(shí)際案例，詳細(xì)分析了其內(nèi)存實(shí)際占用的分布，并比對(duì)了多種常見的用于緩存的內(nèi)存結(jié)構(gòu)的優(yōu)劣勢(shì)。

在進(jìn)一步優(yōu)化的時(shí)候，針對(duì)不同類型的數(shù)據(jù)可以進(jìn)行選擇不同的編碼方式，并以兩個(gè)實(shí)際的緩存壓縮方案為例，介紹了如何組合的使用此類編碼來有效壓縮本地緩存的內(nèi)存大小。

綜上所述，雖然存儲(chǔ)在服務(wù)器內(nèi)存中的緩存成本較高，但是若合理的進(jìn)行數(shù)據(jù)選型并采用合適的優(yōu)化方法，則可以達(dá)到使用少量的內(nèi)存緩存大規(guī)模的數(shù)據(jù)，以較低的成本大幅提高應(yīng)用的響應(yīng)性能的目的。