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

一、前言

攜程酒店查詢服務是酒店BU后端的核心服務，主要負責提供所有酒店動態數據計算的統一接口。在處理請求的過程中，需要使用到酒店基礎屬性信息、價格信息等多維度的數據信息。為了保證服務的響應性能，酒店查詢服務對所有在請求過程中需要使用到的相關數據進行了緩存。隨著攜程酒店業務的發展，查詢服務目前在保證數據最終一致性以及增量秒級更新延遲的情況下，在包括服務器本地內存以及Redis等多種介質上緩存了百億級的數據。

本文將主要討論酒店查詢服務技術團隊是如何在保證讀取效率的前提下，針對存儲在服務器本地的緩存數據進行存儲結構選型以及優化的過程。

二、內存結構選型

為了尋找合適的內存結構以達到理想的效果，本節將詳細探討在通用數據查詢場景下，不同類型的數據結構的可行性與優劣勢。

2.1 緩存結構的基礎需求

2.1.1 支持高性能讀取

在大部分應用場景下，之所以需要在服務器內存中存儲緩存數據，是因為請求處理過程中需要高頻次讀取各類數據。為了保證服務的響應性能，我們有的時候會選擇將數據提前存儲在本地內存，利用空間換取時間。酒店查詢服務就有這樣的需求：服務平均每次請求需要讀取數據上千次，同時對響應時間也有著嚴格的要求。因此，在這種高頻次訪問緩存的場景下，對數據的查找性能便有著極高的要求。

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

2.1.2 支持高更新頻率

在實際應用場景下，生產環境的緩存數據必然有新鮮度要求。面對海量數據，高頻度的數據更新幾乎無可避免。特別是像價格這類數據，一方面更改頻次極高，另一方面又必須保證新的增量數據可以在秒級內快速同步至緩存中。這就要求所使用的緩存數據結構必須支持高性能并發讀寫的場景。如果隨意的使用鎖機制或是線程不安全的存儲結構都會可能導致一些預期外的問題與風險：

1)并發更改風險

眾所周知，Java提供實現的最常用的散列表HashMap是非線程安全的數據結構。若直接使用該類作為緩存結構，則在并發讀寫時就可能會因為重新Hash而讀到錯誤的數據，甚至在極端情況下產生死循環的問題。

2)濫用讀寫鎖

在頻繁并發更新與讀取的場景下，錯誤的鎖機制很有可能導致在高頻次寫入時直接卡死應用處理請求時的高頻次讀取，進而產生大量請求排隊以及其他問題。

因此，高更新頻率需求所帶來的線程安全問題，導致大部分的基礎數據結構都無法適用于存儲生產緩存數據。在絕大部分情況下，都需要犧牲一部分性能選擇線程安全的數據結構。當然，對于某些特殊場景，也可根據需要來設計定制化的結構與鎖機制來達到更優的性能。

經過上面的簡單分析后，我們可以暫時認為線程安全的數組和散列表是一個較優的用以承載緩存數據的結構。

2.2 低空間開銷的結構選型

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

在對不同數據結構進行分析前，我們需要從最基礎的問題開始：Java中的一個對象是以何種結構存儲在內存里的?

2.2.1 Java對象內存結構模型

一個Java對象在內存中的存儲結構通常包括對象頭、實例數據與對齊填充。

對象頭

對象頭用于存儲對象的標記位(Mark Word)與類型指針(Class Pointer)。

標記位里存儲了包含鎖狀態與GC標記位等信息，其在32位系統上占存4字節而在64位系統上占存8字節。

類型指針是一個對象指向它元數據的指針，因此，其在32位系統上占存4字節，在64位系統上占存8字節。同時，若在64位機器上開啟指針壓縮參數-XX:UseCompressedOops，則此時類型指針在對象頭中僅占存4字節。

另外，若實體為數組，則會額外有4個字節用以存儲該數組的長度。

實例數據

實例數據內部存儲了對象所定義的所有成員變量。這些成員變量會緊密排列，若對象是由子類創建的，則其父類的成員變量也會包含在其中。若成員變量為NULL值，則不會給該成員變量申請指針空間。

對齊填充

若對象所申請的內存空間不是8的倍數，則JVM會添加合適的對齊填充使得整個對象所申請的空間為8的倍數。

綜上，若一個簡單實例對象內部存儲一個int字段以及一個byte字段，那么在開啟指針壓縮的64位機器上其占存應為24字節。其中包含對象頭的8字節標識位與4字節類型指針、內部字段int的4字節與byte的1字節以及對齊填充7字節。

2.2.2 原生HashMap結構內存開銷

基于上述的Java實例內存結構的基礎理論，我們將以HashMap為主要示例，詳細探討JDK原生HashMap內部結構以及其內存開銷。

下表是一個簡單的實驗結果。我們統計了在開啟指針壓縮的64位機器上，不同數據條數的鍵值類型均為Integer的HashMap的內存占存。作為參考，我們將其所存儲的所有Integer實例的占存視作數據占存，將剩余的占存視作結構占存。從下表的實驗結果來看，無論在何種數據規模下，HashMap內部結構的內存開銷占比都很高，占到了整體的55%以上。

需要知道此類現象的成因還是需要從HashMap內部存儲結構為入手點進行分析。如下圖所示，HashMap主要由一個哈希桶數組及多個存儲在哈希桶中的節點Node所構成。

下面我們來分別具體解析一下哈希桶數組table和數據節點Node的內存開銷。

哈希桶數組table

哈希桶數組實際是用于存儲數據節點Node的數組。程序將根據數據Key的HashCode運算得到數據節點Node實際應存儲在哈希桶數組的哪一個下標位置。通過哈希桶打散數據后，程序可以通過Key快速的查找到實際數據節點。其在源碼中實際定義如下：

那么，在內存結構上，哈希桶就是由一個附帶數組長度的對象頭和數組元素集合組成。因此，一個長度為N的哈希桶數組的占存大小就會是：

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

為了提升讀寫性能，HashMap中哈希桶數組的實際長度并不會總是等于實際存儲的數據量。哈希桶數組的實際長度在兩個時候會產生變化：

1)初始化

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

2)擴容

HashMap為了確保其讀寫效率，當內部數據量到達一定規模時，會進行擴容操作。而其負載因子和當前哈希桶數組的長度二者相乘所得出的擴容閾值決定了擴容前在哈希表內部最大元素數量。例如，一個容量為32、負載因子為默認的0.75的HashMap的擴容閾值即為32*0.75=24。那么，當此HashMap被插入24條數據后，其內部的原先32長的哈希桶數組就會被擴容至原長度的2倍64。

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

下表是在不同數據規模下哈希桶數組相對于普通實體數組，冗余的數組長度及其額外的開銷。

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

數據節點Node

Node類繼承于 Map.Entry，是HashMap中存儲數據的基本單元。其內部除了存儲了鍵值對數據外，同時存儲了節點的哈希值以及是當其在鏈表或紅黑樹中時，其下個Node節點的引用。

那么，我們可以依據其內部結構如計算出一個Node實例的字節數為32個字節。若要使用Node存儲32個Integer鍵值對，那么所有32個節點實體一共要占用1024個字節。

那么我們可以在前面的實驗數據中再添加上Node的數據，得到完整的HashMap內存開銷各部分的占比：

所以，在原生HashMap消耗了大量的額外空間結構換取其讀寫性能。這使得原生HashMap在大數據量且內存有限的應用上，并不是一個最優的緩存結構選型。

2.2.3 包裝類型損耗

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

Integer[]

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

int[]

基礎類型的int[]則簡單的多：在創建數組時，僅需為每個元素開辟4字節來保存整型即可。

所以，理論上每個Integer都會比int額外產生16字節的內存開銷 。從實驗結果可以看出，若我們可以直接使用基礎類型來代替包裝類存儲時，可以大幅減少內存占存。此結論對其他如HashMap等數據結構也同樣有效。

2.2.4 其他結構選型

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

ConcurrentHashMap

ConcurrentHashMap是HashMap的線程安全版本，內部也是使用數組、鏈表與紅黑樹的結構來存儲元素。相較于同樣JDK中線程安全的HashTable來說，其鎖競爭更少、讀寫效率更高。

SparseArray

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

Guava Cache

Guava Cache是google開源的一款本地緩存工具庫。其使用多個segments方式的細粒度鎖，提供了支持高并發場景的線程安全的存儲結構。

fastutil

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

我們實驗了整型鍵值對不同數據規模下各個集合的內存占比，并且用HashMap的數據作為基準進行橫向比較。實驗結果具體數據如下所示。

三、數據編碼壓縮

在實際應用場景下，幾乎所有需要緩存的數據都有著比較高的重復率或是其他分布規律。在內存結構選型的基礎上，針對于不同的數據特征，我們可以采用不同的數據編碼壓縮方式對數據進行壓縮處理，進一步降低緩存的內存開銷。

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

3.1 常用編碼技術

3.1.1 位圖編碼

位圖(BitMap)是一種常見的編碼格式，JDK中提供的默認實現為BitSet類。它是用Bit位來存儲數據的某種狀態，通常指示是非有無。在最常見的情況下，當需要存儲大量連續ID是否為True時，用到此類結構就可以大量減少內存的開銷。

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

下表是在64位機器上開啟指針壓縮后， Java原生HashMap與BitSet的耗存對照表?？梢悦黠@地看出，整體壓縮效率是非常高的。在實際業務場景下，只要整型Key分布相對密集，就可以利用位圖編碼達到不錯的壓縮效果。

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

enumSeason{ Spring,Summer,Fall,Winter;}

3.1.2 游程編碼

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

比如，一個內部存儲了4個連續的a與6個連續的b的字符串經過游程編碼后為a4b6。那么，該字符串長度就從10字節減少至4字節。

3.1.3 字典編碼

字典編碼是把整體重復性高的數據進行去重后建立字典，把原來存放數據的地方變為指向實體字典引用的編碼方式。因為引用指針依然占存，因此適合單個的實例數據字段較多的數據緩存。

下例為原始數據為整型Key查詢長字符串Value的場景。首先，將重復的字符串實體數據提取出來，將其單獨作為一個實體字典進行存儲。該字典Key為一個指針，Value則為提取出的不重復的字符串數據。然后，原始字典的Value就可以變為一個指針，指向新實體字典的Key。當需要查詢Key1內實際數據的時候，先在原始字典中查詢到引用Ref1，再在實體字典查詢Ref1即可獲得其Value值aaaa。

3.1.4 差值編碼

差值編碼是對于非連續的數據Key通過差值計算的方式轉化為連續的Key，讓字典可以轉化為數組的編碼方式。

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

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

以上的編碼技術可以在不同的數據場景下進行組合使用，接下來我們將簡要的展示兩個實際酒店查詢服務緩存內存壓縮優化的案例。

3.2 應用案例

3.2.1 房型基礎信息

查詢服務緩存了上億條房型信息數據。在請求處理過程中，服務可以在緩存中通過房型ID查詢到該房型的信息。因為數據條數上億且實體內部字段很多，因此未優化的緩存在內存中占存高達上百GB，是一個較大的內存性能瓶頸。

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

1)使用位圖編碼對可枚舉字段進行數據壓縮

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

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

2)使用字典編碼對重復實體進行壓縮

經過線上數據統計與分析，我們發現部分房型屬性數據的重復率達到99%。也就是說，雖然存在上億個房型，但是實際去重后的房型的部分基礎信息實體只有百萬級。因此，在對房型基礎信息實體本身進行位圖編碼的同時，我們采用了字典編碼的方式對房型ID不同但內部字段信息完全重復的數據實體進行字典編碼，以壓縮這部分的消耗。

在實際處理過程中，我們會先將房型數據實體進行序列化后轉換為MD5，在房型字典中只存儲MD5編碼，而實體字典中存儲MD5到實際房型信息實體的關系。在進行數據查詢時，則是先通過房型ID在房型字典中查找到對應的MD5值，然后在實體字典中通過MD5值查找到對應的房型基礎信息實體。

經過上述兩個編碼壓縮優化后，房型實體緩存占存整體壓縮率達到2%以下，節省了數十GB的內存空間。

3.2.2 單天房價信息

單天房價信息緩存是存儲每個房型每日價格的緩存，是查詢服務數據量最大同時也是最核心的數據緩存。在應用請求處理過程中，會使用房型ID以及日期從該緩存中獲取房型某一天的價格數據。

下面將以單房型下存儲的日期信息為例，逐步展示數據壓縮優化的全部過程。

1)使用字典編碼對每日重復的價格信息進行編碼

首先，將所有該房型上出現的價格提取并存儲到一個價格數組上，在數據字典里則存儲實際價格數據在價格字典的索引。同時，因為存在可能沒有數據的日期，因此Null值被存儲在所有價格數組上的第一個偏移index上，作為默認值。

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

因為在絕大部分情況下，數據字典中的日期均為連續的，且從業務場景上來說最大的日期也不會過大，因此我們采用差值編碼處理日期，將數據字典中的日期替換為與服務器啟動日期之間相差天數的偏移量。此時，數據字典的Key則會變為一個從0開始的int，那么就可以使用占存更小的數組來表示這個數據字典。該數據索引數組為一個int[]，其下標表示日期偏移，值表示到價格字典的索引。

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

因為單個房型下的價格數量是有限的，因此同樣可以視作是枚舉值的一種。對枚舉值，就可以使用位圖編碼對數據索引數組進行壓縮。在下圖的數據樣例中，因為價格數組長度為3，即存在3種可能的價格，因此將int轉換為2個bit進行存儲，則位圖的一天的偏移步長為2。

4)使用RLE編碼處理末尾

在很多房型下的到天價格數據，在距離現在最遠的日期帶的價格通常都是重復的，因此，我們可以使用RLE的方式對末尾重復的數據進行截尾，來進一步壓縮數據位圖大小。

在所舉的例子中，其在內存中單對象實例數據部分的內存可以從最初的數百字節降低至最終的31字節。而在實際業務場景中，該單天房價數據經過壓縮處理后實際壓縮率為60%左右。

四、總結

本文主要介紹了攜程酒店查詢服務在本地緩存數據結構選型以及優化方面的探索與實際應用案例。

在常規緩存數據的存儲結構選型上，我們先根據緩存場景的需求，分析比較了不同數據結構后，選擇線程安全的Map結構作為基礎研究方向。然后基于Java對象占存的原理，以原生HashMap為實際案例，詳細分析了其內存實際占用的分布，并比對了多種常見的用于緩存的內存結構的優劣勢。

在進一步優化的時候，針對不同類型的數據可以進行選擇不同的編碼方式，并以兩個實際的緩存壓縮方案為例，介紹了如何組合的使用此類編碼來有效壓縮本地緩存的內存大小。

綜上所述，雖然存儲在服務器內存中的緩存成本較高，但是若合理的進行數據選型并采用合適的優化方法，則可以達到使用少量的內存緩存大規模的數據，以較低的成本大幅提高應用的響應性能的目的。