成熟的缓存技术有哪几种携程百亿级缓存系统探索之路

携程酒店查询服务是酒店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<Integer,Integer>为主要示例，详细探讨JDK原生HashMap内部结构以及其内存开销。

下表是一个简单的实验结果。我们统计了在开启指针压缩的64位机器上，不同数据条数的键值类型均为Integer的HashMap的内存占存。作为参考，我们将其所存储的所有Integer实例的占存视作数据占存，将剩余的占存视作结构占存。从下表的实验结果来看，无论在何种数据规模下，HashMap内部结构的内存开销占比都很高，占到了整体的55%以上。