一、前言 攜程酒店查詢服務是酒店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實例内存結構的基礎理論，我們将以HashMapInteger,Integer為主要示例，詳細探讨JDK原生HashMap内部結構以及其内存開銷。

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

　　下面我們來分别具體解析一下哈希桶數組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所存儲的哈希桶實體數組在絕大部分情況下總是會将冗餘出比實際數據量多一些的空間，以減少哈希碰撞、提升讀取效率。

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

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

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

　　那麼我們可以在前面的實驗數據中再添加上Node的數據，得到完整的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等數據結構也同樣有效。

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

　　ConcurrentHashMap

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

　　SparseArray

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

　　Guava Cache

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

　　fastutil

　　FastUtil是一個高性能的集合框架，提供了以基礎類型為元素的集合來代替JDK原生的集合類型。基礎類型為元素的集合避免了大量的基礎類型的裝箱拆箱。因此，在程序進行集合的遍曆、根據索引獲取元素的值和設置元素的值的時候，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分布相對密集，就可以利用位圖編碼達到不錯的壓縮效果。

　　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為實際案例，詳細分析了其内存實際占用的分布，并比對了多種常見的用于緩存的内存結構的優劣勢。

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

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

　　參考資料

　　Java對象布局：

　　htt

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!