Yishi，携程高级后端开发工程师；Zhenqing，携程资深后端开发专家。1.前言携程的酒店查询服务是酒店BU后台的核心服务，主要负责为所有酒店的动态数据计算提供统一的接口。在处理请求的过程中，需要用到酒店基本属性信息、价格信息等多维数据信息。为了保证服务的响应性能，酒店查询服务缓存了请求过程中需要用到的所有相关数据。随着携程酒店业务的发展，查询服务目前在包括服务器本地内存和Redis在内的各种介质上缓存百亿级数据，同时保证数据的最终一致性和增量秒级更新延迟。本文将主要探讨酒店查询服务技术团队如何在保证读取效率的前提下，对服务器本地存储的缓存数据进行存储结构的选择和优化。2.内存结构选择为了找到合适的内存结构来达到预期的效果，本节将详细讨论不同类型数据结构在一般数据查询场景下的可行性、优缺点。2.1缓存结构的基本要求2.1.1支持高性能读取在大多数应用场景中，缓存数据之所以需要存储在服务器内存中，是因为在请求处理过程中需要频繁读取各类数据。为了保证服务的响应性能，我们有时会选择将数据提前存储在本地内存中，用空间换取时间。酒店查询服务有这样一个需求：该服务平均每个请求需要读取数千次数据，并且对响应时间有严格的要求。所以在这种高频访问缓存的场景下，对数据的查找性能有着极高的要求。在常见的数据结构中，数组和哈希表都可以提供O(1)的查询速度，这是不考虑其他因素时性能最高的选择。搜索复杂度为O(log2N)的树次之，其搜索速度与数据大小有关。一般只能用于数据量较小的场景。2.1.2支持高更新频率在实际应用场景中，生产环境中的缓存数据必须有新鲜度要求。面对海量数据，高频的数据更新几乎是不可避免的。尤其是价格这样的数据，一方面变化频率极高，另一方面又要保证新的增量数据能够在秒级内快速同步到缓存中。这就要求使用的缓存数据结构必须支持高性能的并发读写场景。随意使用锁机制或线程不安全的存储结构可能会导致一些意想不到的问题和风险：1）并发变更风险众所周知，Java提供的最常用的哈希表HashMap是一种非线程安全的数据结构。如果直接使用该类作为缓存结构，在并发读写时可能会因为re-hash而读取到错误的数据，极端情况下甚至会造成死循环问题。2）滥用读写锁在频繁并发更新和读取的场景下，错误的锁机制很可能导致应用在处理请求时高频读直接卡在高频写时，从而产生大量请求排队等问题的数量。因此，高更新频率要求带来的线程安全问题使得大多数基础数据结构不适合存储生产缓存数据。大多数情况下，需要牺牲部分性能来选择线程安全的数据结构。当然，对于一些特殊的场景，也可以根据需要设计定制化的结构和锁定机制，以达到更好的性能。经过上面的简单分析，我们可以暂时认为线程安全的数组和哈希表是承载缓存数据更好的结构。2.2空间开销低的结构选择由于实际应用内存是有限的，我们需要思考如何在保证读写性能的情况下减少缓存消耗的内存资源。酒店查询服务为了保证服务正常响应请求，需要在本地存储上千万条数据，但是缓存在虚拟机上可以使用的内存空间非常有限。因此，除了对数据本身进行过滤等预处理外，用于存储数据的通用结构的内存开销应尽可能小。在分析不同的数据结构之前，我们需要先从一个最基本的问题说起：Java中的对象以什么样的结构存储在内存中？2.2.1Java对象内存结构模型Java对象在内存中的存储结构通常包括对象头、实例数据和对齐填充。对象头对象头用来存放对象的标志位（MarkWord）和类型指针（ClassPointer）。标志位存储锁状态和GC标志位等信息，在32位系统上占用4个字节，在64位系统上占用8个字节。类型指针是一个对象指向它的元数据的指针，所以它在32位系统上占用4个字节，在64位系统上占用8个字节。同时，如果在64位机器上启用了指针压缩参数-XX:UseCompressedOops，此时类型指针在对象头中只占用4个字节。另外，如果实体是数组，还会多出4个字节来存放数组的长度。实例数据实例数据在内部存储了对象定义的所有成员变量。这些成员变量会紧密排列，如果对象是由子类创建的，那么其父类的成员变量也会被包含进来。如果成员变量为NULL值，则不会为该成??员变量申请指针空间。Alignmentpadding如果对象申请的内存空间不是8的倍数，JVM会添加适当的alignmentpadding，使得整个对象申请的空间都是8的倍数。综上所述，如果一个简单的实例对象内部存储了一个int字段和一个byte字段，那么在启用指针压缩的64位机器上，它的存储应该是24字节。包括对象头的8字节标识位和4字节类型指针，4字节的内部域int和1字节的byte，7字节的对齐填充。2.2.2原生HashMap结构内存开销基于上述Java实例内存结构的基本理论，我们将以HashMap为主要实例详细讨论JDK原生HashMap的内部结构及其内存开销。下表是一个简单实验的结果。我们统计了64位机器上开启指针压缩的情况下，键值类型为Integer的HashMap对于不同数量的数据项的内存占用情况。作为参考，我们将其存储的所有Integer实例的内存作为数据内存，剩余内存作为结构内存。从下表的实验结果来看，无论数据大小如何，HashMap内部结构的内存开销占比都很高，占总量的55%以上。要知道造成这种现象的原因，还是要从HashMap内部的存储结构来分析。如下图所示，HashMap主要由一个哈希桶数组和存储在哈希桶中的多个节点Node组成。下面详细分析哈希桶数组表和数据节点Node的内存开销。哈希桶数组表哈希桶数组实际上是一个用来存放数据节点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个长度的哈希桶数组就会扩充到原来长度的64倍。结合上面的哈希桶长度策略，可以很明显的看出，HashMap中存储的哈希桶实体数组在大多数情况下总是会比实际数据量有更多的空间，以减少哈希Hi碰撞，提高读取效率。下表展示了哈希桶数组在不同数据大小下与普通实体数组相比的冗余数组长度和额外开销。那么根据以上理论，我们可以计算出不同数据量的HashMap中哈希桶数组的内存开销和占比。数据节点NodeNode类继承自Map.Entry，是HashMap中存储数据的基本单位。除了存储键值对数据外，在链表或红黑树中时，还存储节点的哈希值和下一个Node节点的引用。那么，根据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其他结构选择为了在保证读写性能的同时尽可能的压缩内存开销，我们调研了一些第三方开源的集合框架，尽可能的在内存和性能之间取得平衡。ConcurrentHashMapConcurrentHashMap是HashMap的线程安全版本，内部使用数组、链表、红黑树结构来存储元素。与同JDK中线程安全的HashTable相比，锁竞争更少，读写效率更高。SparseArraySparseArray是一个稀疏数组，是Android提出的一个类，用来代替HashMap来存储整型对象的键值对。它内部主要使用数组作为存储方式，比HashMap更高效、更轻量。GuavaCacheGuavaCache是??Google开源的本地缓存工具库。它使用多段形式的细粒度锁，提供支持高并发场景的线程安全存储结构。fastutilFastUtil是一个高性能的集合框架，它提供以基本类型作为元素的集合，而不是JDK的原生集合类型。基本类型是元素的集合，避免了基本类型的大量装箱和拆箱。因此，当程序遍历集合，根据索引获取元素的值，设置元素的值时，fastutil可以提供更快的访问速度和更低的内存消耗。我们实验了不同数据大小下每个整数键值对集合的内存比例，并以HashMap数据为基准进行横向比较。实验结果的具体数据如下所示。3.数据编码与压缩在实际应用场景中，几乎所有需要缓存的数据都有比较高的重复率或其他分布规则。基于内存结构的选择，我们可以根据不同的数据特??性，采用不同的数据编码和压缩方式对数据进行压缩，进一步降低缓存的内存开销。下面，我们将介绍几种常用且有效的数据编码和压缩方法。3.1常用编码技术3.1.1位图编码位图（BitMap）是一种常用的编码格式，JDK默认提供的实现是BitSet类。是某种状态，用Bit来存储数据，通常表示它是否为真。在最常见的情况下，当需要存储大量连续的ID是否为True时，使用这样的结构可以大大减少内存开销。下面的例子中，要存储的数据的Key是一个整数，Value是表示Key是否有效的状态数据。如果直接存储，一条数据至少需要4个字节来存储整数Key，4个字节来存储布尔状态值。那么，当需要存储从Key1到Key8的8条数据时，至少需要64个字节。如果使用位图编码技术来处理数据，那么我们只需要1位来存储一个True或False状态信息。因此，1个字节可以用来存储所有8个数据的状态信息。此时字节的第1位用于表示Key=1的状态信息，第2位用于表示Key=2的状态信息，以此类推。下表是64位机器上启用指针压缩后Java原生HashMap与BitSet的内存对比表。可以明显看出整体的压缩效率非常高。在实际业务场景中，只要整型键分布比较密集，就可以采用位图编码来达到很好的压缩效果。此外，位图编码还可以扩展到一些类型较少的枚举类型。比如枚举类Season只有4个元素，可以用2bits表示一个属性，那么只需要8bits就可以存储4个id为1-4的Season枚举。enumSeason{Spring,Summer,Fall,Winter;}3.1.2游程编码游程编码（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差分编码差分编码就是将不连续的数据Keys通过差分计算转化为连续的Keys，从而实现字典转化为数组。下面例子中的数据Key是一个日期，Value是一个整数。当日期比较连续时，取所有日期中的最小者作为起始日期，将数据生效日期与起始日期的差值作为新字典的key。那么编码前的旧数据字典的key是Date类型，编码后的新数据字典的类型可以转化为更小更通用的int类型。下表是在N天连续日期整型查询场景下，原始HashMap与编码整型数组的内存消耗对比表。即使连续日期的数量很少，总体上也可以看出很大的差距。在实际应用场景中，这种编码一般用于连续日期的缓存，也可以扩展到其他具有类似数据特性的缓存。上述编码技术可以在不同的数据场景中组合使用。下面简单展示两个实际酒店查询服务缓存内存压缩优化的案例。3.2应用案例3.2.1基础房型信息查询服务，缓存亿级房型信息数据。在请求处理过程中，服务可以通过房型ID查询缓存中的房型信息。由于实体有数亿条数据条目，内部字段较多，未优化的缓存占用内存数百GB，是较大的内存性能瓶颈。因此，对于这个缓存，我们使用了位图编码和字典编码，大大降低了它的内存开销。1）使用位图编码压缩可枚举字段。我们对房间数据实体上的所有可枚举字段进行位图编码，包括布尔、枚举、部分字符串，大大减少了单个实体的占用。节省尺寸。例如，在下面这个字段中，RoomType存储为一个String，但是在实际业务场景中它只有5个可能的取值，所以也可以把它看成一个3位的枚举类。在原始存储方式的情况下，示例中的房间类型实体字段至少需要16个字节。经过位图编码后，一个房间类型的实体字段实际上只需要10位就可以无损地存储所有有效信息。2)使用字典编码来压缩重复的实体。经过线上数据统计分析，我们发现部分房型属性数据的重复率达到了99%。也就是说，虽然有上亿种房型，但实际去重后的房型的一些基本信息实体只有百万级。因此，我们在对基本房型信息实体本身进行位图编码的同时，使用字典编码对房型ID不同但内部字段信息完全重复的数据实体进行编码，以压缩这部分的消耗。在实际处理过程中，我们会先将房型数据实体序列化，然后进行MD5转换。房型字典中只存储MD5码，实体字典中存储MD5与实际房型信息实体的关系。在进行数据查询时，先通过房型ID在房型字典中查找对应的MD5值，再通过实体字典中的MD5值查找对应的房型基本信息实体。经过以上两次编码压缩优化，房间型实体缓存的整体压缩率在2%以下，节省了数十GB的内存空间。3.2.2单日房价信息单日房价信息缓存是存储各房型每日价格的缓存。是查询业务数据量最大的数据缓存，也是核心数据。在申请请求处理过程中，会根据房型ID和日期从缓存中获取该房型某一天的价格数据。下面将以单房型存储的日期信息为例，逐步展示数据压缩优化的全过程。1）使用字典编码对每天重复出现的价格信息进行编码首先将房型上出现的所有价格提取并存储到一个价格数组中，在数据字典中存储实际价格数据在价格字典中的索引。同时，因为有些日期可能没有数据，所以在所有价格数组的第一个偏移量索引处存储了Null值作为默认值。2）使用差分编码处理日期因为大多数情况下，数据字典中的日期是连续的，最大的日期在业务场景上不会太大，所以我们使用差分编码来处理日期。将数据字典中的日期替换为服务器启动日期的天数偏移量。这时候数据字典的Key就会变成一个从0开始的int，所以数据字典可以用一个占地面积更小的数组来表示。数据索引数组是一个int[]，下标表示日期偏移量，值表示到价格字典的索引。3）使用位图编码对可枚举价格指数进行处理。因为单个房型下的价格数量是有限的，所以也可以看成是一种枚举值。对于枚举值，可以使用位图编码来压缩数据索引数组。在下图的数据样本中，因为价格数组的长度为3，即有3种可能的价格，所以将int转换为2位存储，位图的偏移步长为2。4）使用RLE编码处理多种房型下的日终价格数据。最远日期范围内的价格通常会重复。因此，我们可以使用RLE将末尾重复的数据截断，进一步压缩Databitmap的大小。在给出的例子中，单个对象实例的数据部分在内存中的内存可以从最初的数百字节减少到最后的31字节。在实际业务场景中，单日房价数据经过压缩处理后的实际压缩率约为60%。4.总结本文主要介绍携程酒店查询服务在本地缓存数据结构选择和优化方面的探索和实际应用案例。在常规缓存数据存储结构的选择上，我们首先根据缓存场景的需求，分析比较不同的数据结构，然后选择线程安全的Map结构作为基础研究方向。然后，基于Java对象内存原理，以原生的HashMap为实际案例，详细分析了其实际内存占用的分布情况，比较了各种常用内存结构用于缓存的优缺点。在进一步优化中，可以针对不同类型的数据选择不同的编码方式，并以两种实际的缓存压缩方案为例，介绍如何结合使用这些编码方式来有效压缩本地缓存的内存大小。综上所述，虽然缓存存储在服务器内存中的成本很高，但如果合理选择数据类型并采用适当的优化方法，是可以用少量内存来高速缓存大量数据的。更低的花费。目的是大大提高应用程序的响应能力。
