的存储布局选型上在常规缓存数据，存场景的需求我们先按照缓，同数据布局后阐发比力了不，布局作为根本研究标的目的选择线程平安的Map。a对象占存的道理然后基于Jav，Map为现实案例以原生Hash，存现实占用的分布细致阐发了其内，缓存的内存布局的好坏势并比对了多种常见的用于。

　　希桶长度策略分析上述的哈，组在绝大部门环境下老是会将冗余出比现实数据量多一些的空间其实能够很较着的看到HashMap所存储的哈希桶实体数，、提拔读取效率以削减哈希碰撞。

　　内存都是无限的因为现实使用的，写机能的同时因而在保障读，低缓存所耗损的内存资本我们也需要思虑若何降。一般的响应请求为了包管办事，地存储万万量级的数据酒店查询办事需要在本，用的内存空间却很是无限而缓存可以或许在虚拟机上使。此因，行过滤等预处置之外除了对数据本身进，的内存开销也要尽可能的小用以存储数据的通用布局。

　　gle开源的一款当地缓存东西库Guava Cache是goo。nts体例的细粒度锁其利用多个segme，的线程平安的存储布局供给了支撑高并发场景。

　　进行实例建立的时候在HashMap，上取最接近的2的整数幂作为现实初始化容量法式会按照所指定的容量（默认为16）向。希桶数组的长度该容量也是哈。为100的HashMap好比外部建立一个指定容量，现实初始长度为128则其内部哈希桶数组的。

　　布局进行阐发前在对分歧数据，中的一个对象是以何种布局存储在内存里的我们需要从最根本的问题起头：Java？

　　么那，个Node实例的字节数为32个字节我们能够根据其内部布局如计较出一。2个Integer键值对若要利用Node存储3，一共要占用1024个字节那么所有32个节点实体。

　　希桶数组相对于通俗实体数组下表是在分歧数据规模下哈，及其额外的开销冗余的数组长度。

　　简单阐发后颠末上面的，表是一个较优的用以承载缓存数据的布局我们能够临时认为线程平安的数组和散列。

　　形态与GC标识表记标帜位等消息标识表记标帜位里存储了包含锁，而在64位系统上占存8字节其在32位系统上占存4字节。

　　指向它元数据的指针类型指针是一个对象，此因，统上占存4字节其在32位系，上占存8字节在64位系统。时同，X:UseCompressedOops若在64位机械上开启指针压缩参数-X，象头中仅占存4字节则此时类型指针在对。

　　例中鄙人，的Key为整型需要存储的数据，y能否无效的形态数据Value为该Ke。接存储若是直，Key以及4个字节用于存储布尔型的形态值则一条数据至多需要4个字节用于存储整型。么那，从1至8的8条数据当需要存储Key，要64字节则至多需。术对数据进行处置若利用位图编码技，True or False的形态消息那么我们仅需要1个bit即可存储一个。此因，下所有8条数据的形态消息就能够利用1个字节存储。时此，暗示Key = 1的形态消息该字节的第1位的bit用以，ey = 2的形态消息第2位的bit用以K，类推以此。

　　shMap内部存储布局为入手点进行阐发需要晓得此类现象的成因仍是需要从Ha。图所示如下，多个存储在哈希桶中的节点Node所形成HashMap次要由一个哈希桶数组及。

　　的例子中在所举，以从最后的数百字节降低至最终的31字节其在内存中单对象实例数据部门的内存可。营业场景中而在现实，理后现实压缩率为60%摆布该单天房价数据颠末压缩处。

　　布局以达到抱负的结果为了寻找合适的内存，通用数据查询场景下本节将细致切磋在，构的可行性与好坏势分歧类型的数据结。

　　象所定义的所有成员变量实例数据内部存储了对。量会慎密陈列这些成员变，子类建立的若对象是由，量也会包含在此中则其父类的成员变。为NULL值若成员变量，变量申请指针空间则不会给该成员。

　　的数据场景下进行组合利用以上的编码手艺能够在分歧，店查询办事缓存内存压缩优化的案例接下来我们将简要的展现两个现实酒。

　　分字符串等所有能够列举的字段进行了位图编码我们将房型数据实体上包罗布尔型、列举以及部，实体的占存大小大幅降低了单个。为例子的字段中好比鄙人方作，存储为一个StringRoomType虽然，一共只要5种取值可能性可是在现实营业场景中它，进行处置为3个bit因而也能够作为列举类。

　　亿条房型消息数据查询办事缓存了上。理过程中在请求处，型ID查询到该房型的消息办事能够在缓存中通过房。且实体内部字段良多由于数据条数上亿，存中占存高达上百GB因而未优化的缓具有内，内存机能瓶颈是一个较大的。

　　据统计与阐发颠末线上数，数据的反复率达到99%我们发觉部门房型属性。是说也就，上亿个房型虽然具有，分根本消息实体只要百万级可是现实去重后的房型的部。此因，本身进行位图编码的同时在对房型根本消息实体，内部字段消息完全反复的数据实体进行字典编码我们采用了字典编码的体例对房型ID分歧但，部门的耗损以压缩这。

　　么那，布局上在内存，度的对象头和数组元素调集构成哈希桶就是由一个附带数组长。此因，数组的占存大小就会是一个长度为N的哈希桶：

　　优化的时候在进一步，进行选择分歧的编码体例针对分歧类型的数据能够，缓存压缩方案为例并以两个现实的，来无效压缩当地缓存的内存大小引见了若何组合的利用此类编码。

　　团队是若何在包管读取效率的前提下本文将次要会商酒店查询办事手艺，进行存储布局选型以及优化的过程针对存储在办事器当地的缓存数据。

　　上面的理论那么根据，Map中哈希桶数组的内存开销及其占比我们就能够推算出分歧数据量的Hash。

　　体例的环境下在原先存储，段就至多需要16字节示例的一个房型实体字，10个bit即可无损的存储下所有无效消息通过位图编码后一个房型实体字段现实仅需要。

　　ger是包装类因为Inte，节长的Integer的援用因而数组中存储的现实是4字。ger实例本身来说而对于一个Inte，文所述参考前，的现实数据外除了4字节，节来保留其对象头其还需要12字。开销就会是4 + 12 + 4 = 20字节所以在调集中要保留一个Integer的现实。

　　上综，int字段以及一个byte字段若一个简单实例对象内部存储一个，位机械上其占存应为24字节那么在开启指针压缩的64。段int的4字节与byte的1字节以及对齐填充7字节此中包含对象头的8字节标识位与4字节类型指针、内部字。

　　gth encoding游程编码（Run-len，压缩数据的编码体例RLE）是一种无损，续呈现的次数来代替数据中持续呈现的部门次要方式是利用当前数据元素以及该元素连。据持续且反复的环境若数据具有大量的数，RLE以降低内存就能够考虑利用。

　　部门环境下由于在绝大，日期均为持续的数据字典中的，最大的日期也不会过大且从营业场景上来说，值编码处置日期因而我们采用差，器启动日期之间相差天数的偏移量将数据字典中的日期替代为与办事。时此，为一个从0起头的int数据字典的Key则会变，的数组来暗示这个数据字典那么就能够利用占存更小。为一个int[]该数据索引数组，示日期偏移其下标表，格字典的索引值暗示到价。

　　a的泛型机制因为Jav，储的类型只能声明为包装类绝大部门的数据布局的存。此因，整型等根本类型即便需要存储是，的包装类型来存储在内存中也将其不得不转换为对应。额外的装拆箱的机能损耗这不只会有存取时发生，也会发生更大的内存开销存储包装类相较根本类型。最为常见的整型为例以现实使用场景中，和int[] 这两种数组的内存大小差别我们将简单比力一下Integer[] 。

　　编码压缩优化后颠末上述两个，体压缩率达到2%以下房型实体缓存占存整，B的内存空间节流了数十G。

　　周知众所，ashMap长短线程平安的数据布局Java供给实现的最常用的散列表H。类作为缓存布局若间接利用该，从头Hash而读到错误的数据则在并发读写时就可能会由于，产存亡轮回的问题以至在极端环境下。

　　+ 4 （实体援用）*N （实体数量）字节 + 对齐字节8（对象头标识位）+ 4（类型指针）+ 4（数组长度 。即，16 + 4 *32 = 144字节长度为32的哈希桶数组则现实占存即为。

　　据布局选型以及优化方面的摸索与现实使用案例本文次要引见了携程酒店查询办事在当地缓存数。

　　先首，提取并存储到一个价钱数组大将所有该房型上呈现的价钱，价钱数据在价钱字典的索引在数据字典里则存储现实。时同，没无数据的日期由于具有可能，数组上的第一个偏移index上因而Null值被存储在所有价钱，默认值作为。

　　过差值计较的体例转化为持续的Key差值编码是对于非持续的数据Key通，为数组的编码体例让字典能够转化。

　　数据布局中在常见的，供O(1)的查询速度数组和散列表都能提，下最高机能的选择是不考虑其他要素。og2N)的树则其次查找复杂度为O(l，数据规模相关其查找速度和，模很小的场景下选用一般只能在数据规。

　　理过程中在现实处，进行序列化后转换为MD5我们会先将房型数据实体，存储MD5编码在房型字典中只，到现实房型消息实体的关系而实体字典中存储MD5。据查询时在进行数，字典中查找到对应的MD5值则是先通过房型ID在房型，查找到对应的房型根本消息实体然后在实体字典中通过MD5值。

　　据中再添加上Node的数据那么我们能够在前面的尝试数，p内存开销各部门的占比获得完整的HashMa：

　　店BU后端的焦点办事携程酒店查询办事是酒，动态数据计较的同一接口次要担任供给所有酒店。求的过程中在处置请，、价钱消息等多维度的数据消息需要利用到酒店根本属性消息。务的响应机能为了包管服，需要利用到的相关数据进行了缓存酒店查询办事对所有在请求过程中。店营业的成长跟着携程酒，性以及增量秒级更新延迟的环境下查询办事目前在包管数据最终分歧，s等多种介质上缓存了百亿级的数据在包罗办事器当地内存以及Redi。

　　了确保其读写效率HashMap为，达到必然规模时当内部数据量，扩容操作会进行。出的扩容阈值决定了扩容前在哈希表内部最大元素数量而其负载因子和当前哈希桶数组的长度二者相乘所得。如例，ashMap的扩容阈值即为32*0.75=24一个容量为32、负载因子为默认的0.75的H。么那，被插入24条数据后当此HashMap，组就会被扩容至原长度的2倍64其内部的原先32长的哈希桶数。

　　此因，该缓存针对，编码以及字典编码我们利用了位图，其内存开销大幅降低了。

　　d）与类型指针（Class Pointer）对象头用于存储对象的标识表记标帜位（Mark Wor。

　　读写机能为了提拔，长度并不会老是等于现实存储的数据量HashMap中哈希桶数组的现实。在两个时候会发生变化哈希桶数组的现实长度：

　　用场景下在现实应，比力高的反复率或是其他分布纪律几乎所有需要缓存的数据都有着。选型的根本上在内存布局，的数据特征针对于分歧，压缩体例对数据进行压缩处置我们能够采用分歧的数据编码，存的内存开销进一步降低缓。

　　查询长字符串Value的场景下例为原始数据为整型Key。先首，实体数据提取出来将反复的字符串，实体字典进行存储将其零丁作为一个。y为一个指针该字典Ke，的不反复的字符串数据Value则为提取出。后然，e就能够变为一个指针原始字典的Valu，字典的Key指向新实体。1内现实数据的时候当需要查询Key，询到援用Ref1先在原始字典中查，可获得其Value值aaaa再在实体字典查询Ref1即。

　　简单的多：在建立数组时根本类型的int[]则，4字节来保留整型即可仅需为每个元素斥地。

　　ray即稀少数组SparseAr，Map的用来存储整型类型对象键值对的类是Android供给的建议替代Hash。数组作为存储体例其内部次要利用了，ap要高效轻量比HashM。

　　日期查整型的场景下下表是在N天持续的，码后整型数组的耗存对照表原生HashMap与编。日期数量较小即便持续的，具有的庞大差距也能够看出全体。使用场景下在现实的，用于持续日期的缓存此类编码体例一般，雷同数据特征的缓存上也能够扩展到其他有着。

　　的到天价钱数据在良多房型下，带的价钱凡是都是反复的在距离此刻最远的日期，此因，对末尾反复的数据进行截尾我们能够利用RLE的体例，数据位图大小来进一步压缩。

　　是一种常见的编码格局位图（BitMap），实现为BitSet类JDK中供给的默认。存储数据的某种形态它是用Bit位来，长短有无凡是指示。的环境下在最常见，ID能否为True时当需要存储大量持续，大量削减内存的开销用到此类布局就能够。

　　价钱数量是无限的由于单个房型下的，作是列举值的一种因而同样能够视。举值对枚，数据索引数组进行压缩就能够利用位图编码对。数据样例中鄙人图的，组长度为3由于价钱数，可能的价钱即具有3种，2个bit进行存储因而将int转换为，的偏移步长为2则位图的一天。

　　table和数据节点Node的内存开销下面我们来别离具体解析一下哈希桶数组。

　　据规模下各个调集的内存占比我们尝试了整型键值对分歧数，数据作为基准进行横向比力而且用HashMap的。数据如下所示尝试成果具体。

　　一个高机能的调集框架FastUtil是，合来取代JDK原生的调集类型供给了以根本类型为元素的集。了大量的根本类型的装箱拆箱根本类型为元素的调集避免。此因，获取元素的值和设置元素的值的时候在法式进行调集的遍历、按照索引，的存取速度以及更低的内存耗损fastutil能够供给更快。

　　Map.EntryNode类承继于 ，存储数据的根基单位是HashMap中。了键值对数据外其内部除了存储，及是当其在链表或红黑树中时同时存储了节点的哈希值以，e节点的援用其下个Nod。

　　单的尝试成果下表是一个简。针压缩的64位机械上我们统计了在开启指，eger的HashMap的内存占存分歧数据条数的键值类型均为Int。参考作为，ger实例的占存视作数据占存我们将其所存储的所有Inte，视作布局占存将残剩的占存。验成果来看从下表的实，数据规模下无论在何种，构的内存开销占比都很高HashMap内部结，的55%以上占到了全体。

　　外另，一些类型较少的列举类型上位图编码还能够额外扩展至。如例，on只要4种元素列举类Seas，it来代表一个属性则能够利用2个b，从1-4的 4个Season列举那么则只需8bit即可存储id。

　　使用场景下在大部门，内存中存储缓存数据之所以需要在办事器，需要高频次读取各类数据是由于请求处置过程中。务的响应机能为了包管服，数据提前存储在当地内存我们有的时候会选择将，换取时间操纵空间。务平均每次请求需要读取数据上千次酒店查询办事就有如许的需求：服，也有着严酷的要求同时对响应时间。此因，问缓存的场景下在这种高频次访，便有着极高的要求对数据的查找机能。

　　的数据进行去重后成立字典字典编码是把全体反复性高，指向实体字典援用的编码体例把本来存放数据的处所变为。针仍然占存由于援用指，据字段较多的数据缓存因而适合单个的实例数。

　　以所，nt额外发生16字节的内存开销 理论上每个Integer城市比i。果能够看出从尝试结，类型来取代包装类存储时若我们能够间接利用根本，少内存占存能够大幅减。ap等数据布局也同样无效此结论对其他如HashM。

　　储数据节点Node的数组哈希桶数组现实是用于存。节点Node现实应存储在哈希桶数组的哪一个下标位置法式将按照数据Key的HashCode运算获得数据。打散数据后通过哈希桶，速的查找到现实数据节点法式能够通过Key快。现实定义如下其在源码中：

　　如比，的b的字符串颠末游程编码后为a4b6一个内部存储了4个持续的a与6个持续。么那，0字减省少至4字节该字符串长度就从1。

　　此因，带来的线程平安问题高更新频次需求所，无法合用于存储出产缓存数据导致大部门的根本数据布局都。分环境下在绝大部，选择线程平安的数据布局都需要牺牲一部门机能。然当，特殊场景对于某些，布局与锁机制来达到更优的机能也可按照需要来设想定制化的。

　　p是HashMap的线程平安版本ConcurrentHashMa，与红黑树的布局来存储元素内部也是利用数组、链表。全的HashTable来说相较于同样JDK中线程安，、读写效率更高其锁合作更少。

　　器上开启指针压缩后下表是在64位机，与BitSet的耗存对照表Java原生HashMap。显地看出能够明，率长短常高的全体压缩效。务场景下在现实业，y分布相对稠密只需整型Ke，达到不错的压缩结果就能够操纵位图编码。

　　用场景下在现实应，据必然有新颖度要求出产情况的缓存数。量数据面临海，新几乎无可避免高频度的数据更。格这类数据出格是像价，改频次极高一方面更，据能够在秒级内快速同步至缓存中另一方面又必需包管新的增量数。必需支撑高机能并发读写的场景这就要求所利用的缓存数据布局。储布局城市可能导致一些预期外的问题与风险若是随便的利用锁机制或是线程不平安的存：

　　况下尽可能压缩内存开销为了在包管读写机能的情，来测验考试在内存和机能上尽可能取得均衡我们调研了一些第三方的开源调集框架。

　　存空间不是8的倍数若对象所申请的内，得整个对象所申请的空间为8的倍数则JVM会添加合适的对齐填充使。

　　所述综上，存中的缓存成本较高虽然存储在办事器内，型并采用合适的优化方式可是若合理的进行数据选，内存缓存大规模的数据则能够达到利用少量的，使用的响应机能的目标以较低的成本大幅提高。

　　Key为日期下例中的数据，为一个整型Value。持续的环境下在日期相对，小值为起头日期取所有日期的最，期的差值为新字典的Key以数据生效日期到起头日。的Key为Date类型那么编码前旧数据字典，能够转化为更小更泛用的int型而编码后的新数据字典的类型则。

　　每个房型每日价钱的缓存单天房价消息缓存是存储，时也是最焦点的数据缓存是查询办事数据量最大同。处置过程中在使用请求，存中获取房型某一天的价钱数据会利用房型ID以及日期从该缓。

　　以所，量的额外空间布局换取其读写机能在原生HashMap耗损了大。大数据量且内存无限的使用上这使得原生HashMap在，的缓存布局选型并不是一个最优。

　　与读取的场景下在屡次并发更新，时间接卡死使用途理请求时的高频次读取错误的锁机制很有可能导致在高频次写入，列队以及其他问题进而发生大量请求。

　　例内存布局的根本理论基于上述的Java实，Map为次要示例我们将以Hash，Map内部布局以及其内存开销细致切磋JDK原生Hash。