本文以美团酒旅在线特征系统为原型,重点从线上数据存取角度介绍一些实践中的通用技术点,以解决在线特征系统在高并发情形下面临的问题。
以上结构图为一体化特征系统的概貌,自底向上为数据流动的方向,各部分的功能如下:
以上指标数字仅是以我们系统作为参考,实际各个部门、公司的特征系统规模可能差别很大,但无论一个特征系统的规模怎样,其系统核心目标必定是考虑:高并发、高吞吐、大数据、低延迟,只不过各有不同的优先级罢了。当系统的优化方向是多目标时,我们不可能独立的用任何一种方式,在有限资源的情况下做到面面俱到。留给我们的是业务最重要的需求特性,以及对应这些特性的解决方案。
本节介绍一些在线特征系统上常用的存取技术点,以丰富我们的武器库。主要内容也并非详细的系统设计,而是一些常见问题的通用技术解决方案。但如上节所说,如何根据策略需求,利用合适的技术,制定对应的方案,才是各位架构师的核心价值所在。
特征总数据量达到TB级后,单一的存储介质已经很难支撑完整的业务需求了。高性能的在线服务内存或缓存在数据量上成了杯水车薪,分布式KV存储能提供更大的存储空间但在某些场景又不够快。开源的分布式KV存储或缓存方案很多,比如我们用到的就有Redis/Memcache,HBase,Tair等,这些开源方案有大量的贡献者在为它们的功能、性能做出不断努力,本文就不更多着墨了。
对构建一个在线特征系统而言,实际上我们需要理解的是我们的特征数据是怎样的。有的数据非常热,我们通过内存副本或者是缓存能够以极小的内存代价覆盖大量的请求。有的数据不热,但是一旦访问要求稳定而快速的响应速度,这时基于全内存的分布式存储方案就是不错的选择。对于数据量级非常大,或者增长非常快的数据,我们需要选择有磁盘兜底的存储方案——其中又要根据各类不同的读写分布,来选择存储技术。
当业务发展到一定层次后,单一的特征类型将很难覆盖所有的业务需求。所以在存储方案选型上,需要根据特征类型进行数据分层。分层之后,不同的存储引擎统一对策略服务提供特征数据,这是保持系统性能和功能兼得的最佳实践。
特征数据简单来说即特征名与特征值。以用户画像为例,一个用户有年龄、性别、爱好等特征。存储这样的特征数据通常来说有下面几种方式:
三种格式各有优劣:
特征系统中,一批特征数据通常来说是完全同构的,同时为了应对高并发下的批量请求,我们在实践中采用了元数据抽取作为存储方案,相比JSON格式,有2~10倍的空间节约(具体比例取决于特征名的长度、特征个数以及特征值的类型)。
提到数据压缩,很容易就会想到利用无损字节压缩算法。无损压缩的主要思路是将频繁出现的模式(Pattern)用较短的字节码表示。考虑到在线特征系统的读写模式是一次全量写入,多次逐条读取,因此压缩需要针对单条数据,而非全局压缩。目前主流的Java实现的短文本压缩算法有Gzip、Snappy、Deflate、LZ4等,我们做了两组实验,主要从单条平均压缩速度、单条平均解压速度、压缩率三个指标来对比以上各个算法。
数据集:我们选取了2份线上真实的特征数据集,分别取10万条特征记录。记录为纯文本格式,平均长度为300~400字符(600~800字节)。
压缩的本质是利用共性,在不影响信息量的情况下进行重新编码,以缩减空间占用。上节中的字节压缩是单行压缩,因此只能运用到同一条记录中的共性,而无法顾及全局共性。举个例子:假设某个用户维度特征所有用户的特征值是完全一样的,字节压缩逐条压缩不能节省任何的存储空间,而我们却知道实际上只有一个重复的值在反复出现。即便是单条记录内部,由于压缩算法窗口大小的限制,长Pattern也很难被顾及到。因此,对全局的特征值做一次字典统计,自动或人工的将频繁Pattern加入到字典并重新编码,能够解决短文本字节压缩的局限性。
当数据总量不大时,策略使用方可以在本地完全镜像一份特征数据,这份镜像叫内存副本。使用内存副本和使用本地的数据完全一致,使用者无需关心远端数据源的存在。内存副本需要和数据源通过某些协议进行同步更新,这类同步技术称为内存副本技术。在线特征系统的场景中,数据源可以抽象为一个KV类型的数据集,内存副本技术需要把这样一个数据集完整的同步到内存副本中。
推拉结合——时效性和一致性
一般来说,数据同步为两种类型:推(Push)和拉(Pull)。Push的技术比较简单,依赖目前常见的消息队列中间件,可以根据需求做到将一个数据变化传送到一个内存副本中。但是,即使实现了不重不漏的高可靠性消息队列通知(通常代价很大),也还面临着初始化启动时批量数据同步的问题——所以,Push只能作为一种提高内存副本时效性的手段,本质上内存副本同步还得依赖Pull协议。Pull类的同步协议有一个非常好的特性就是幂等,一次失败或成功的同步不会影响下一次进行新的同步。
Pull协议有非常多的选择,最简单的每次将所有数据全量拉走就是一种基础协议。但是在业务需求中需要追求数据同步效率,所以用一些比较高效的Pull协议就很重要。为了缩减拉取数据量,这些协议本质上来说都是希望高效的计算出尽量精确的*数据差异*(Diff),然后同步这些必要的数据变动。这里介绍两种我们曾经在工程实践中应用过的Pull型数据同步协议。
基于版本号同步——回放日志(RedoLog)和退化算法
在数据源更新时,对于每一次数据变化,基于版本号的同步算法会为这次变化分配一个唯一的递增版本号,并使用一个更新队列记录所有版本号对应的数据变化。
内存副本发起同步请求时,会携带该副本上一次完成同步时的最大版本号,这意味着所有该版本号之后的数据变化都需要被拉取过来。数据源方收到请求后,从更新队列中找到大于该版本号的所有数据变化,并将数据变化汇总,得到最终需要更新的Diff,返回给发起方。此时内存副本只需要更新这些Diff数据即可。
对于大多数的业务场景,特征数据的生成会收口到一个统一的更新服务中,所以递增版本号可以串行的生成。如果在分布式的数据更新环境中,则需要利用分布式id生成器来获取递增版本号。
另一个问题则是更新队列的长度。如果不进行任何优化,更新队列理论上是无限长的,甚至会超过数据集的大小。一个优化方法是我们限制住更新队列的最大长度,一旦长度超过限制,则执行合并(Merge)操作。Merge操作将队列中的数据进行两两合并,合并后的版本号以较大的版本号为准,合并后的更新数据集是两个数据集的并。Merge后,新的队列长度下降为原更新队列的一半。
Merge之后的更新队列,我们依然可以使用相同的算法进行同步Diff计算:在队列中找到大于上一次更新版本号的所有数据集。可以看到由于版本号的合并,算出的Diff不再是完全精准的更新数据,在队列中最早的更新数据集有可能包含部分已经同步过的数据——但这样的退化并不影响同步正确性,仅仅会造成少量的同步冗余,冗余的量取决于Diff中最早的数据集经过Merge的次数。
MerkleTree同步——数据集对比算法
基于版本号的同步使用的是类似RedoLog的思想,将业务变动的历史记录下来,并通过回放未同步的历史记录得到Diff。由于记录不断增长的RedoLog需要不小的开销,所以采用了Merge策略来退化原始日志(Log)。对于批量或者微批量的更新来说,基于版本号的同步算法能较好的工作;相反,若数据是实时更新的,将会出现大量的RedoLog,并快速的退化,影响同步的效率。
MerkleTree同步算法走的是另一条路,简单来说就是通过每次直接比较两个数据集的差异来获取Diff。首先看一个最简单的算法:每次内存副本将所有数据的Hash值发送给数据源,数据源比较整个数据集,对于Hash值不同的数据执行同步操作——这样就精确计算出了两个数据集之间的Diff。但显而易见的问题,是每次传输所有数据的Hash值可能并不比多传几个数据轻松。MerkleTree同步算法就是使用MerkleTree数据结构来优化这一比较过程。
MerkleTree简单来说是就是把所有数据集的hash值组织成一棵树,这棵树的叶子节点描述一个(或一组)数据的Hash值。而中间节点的值由其所有儿子的Hash值再次Hash得到,描述了以它为根的子树所包含的数据的整体Hash。显然,在不考虑Hash冲突的情况下,如果两颗MerkleTree根节点相同,代表这是两个完全相同的数据集。
MerkleTree同步协议由副本发起,将副本根节点值发送给数据源,若与数据源根节点hash值一致,则没有数据变动,同步完成。否则数据源将把根结点的所有儿子节点的hash发送给副本,进行递归比较。对于不同的hash值,一直持续获取直到叶子节点,就可以完全确定已经改变的数据。以二叉树为例,所有的数据同步最多经过LogN次交互完成。
当数据规模大,无法完全放入到内存中,冷热数据分明,对于数据时效性要求又不高的时候,通常各类业务都会采用客户端缓存。客户端缓存的集中实现,是特征服务延伸的一部分。通用的缓存协议和使用方式不多说,从在线特征系统的业务角度出发,这里给出几个方向的思考和经验。
接口通用化——缓存逻辑与业务分离
一个特征系统要满足各类业务需求,它的接口肯定是丰富的。从数据含义角度分有用户类、商户类、产品类等等,从数据传输协议分有Thrift、HTTP,从调用方式角度分有同步、异步,从数据组织形式角度分有单值、List、Map以及相互嵌套等等……一个良好的架构设计应该尽可能将数据处理与业务剥离开,抽象各个接口的通用部分,一次缓存实现,多处接口同时受益复用。下面以同步异步接口为例介绍客户端接口通用化。
同步接口只有一步:
异步接口分为两步:
同步和异步接口的数据处理只有顺序的差别,只需要梳理好各个步骤的执行顺序即可。引入缓存后,数据处理流程对比如下:
不同颜色的处理框表示不同的请求。异步流程需要使用方的两次请求才能获取到数据。像图中“用服务端数据更新缓存”(updatecache)、“服务端数据与缓存数据汇总”(mergedata)步骤在异步流程里是在第二次请求中完成的,区别于同步流程第一次请求就完成所有步骤。将数据流程拆分为这些子步骤,同步与异步只是这些步骤的不同顺序的组合。因此读写缓存(searchcache、updatecache)这两个步骤可以抽象出来,与其余逻辑解耦。
客户端之于服务端,犹如服务端之于数据库,其实数据存储压缩的思路是完全一样的。具体的数据压缩与存储策略在上文数据压缩章节已经做了详细介绍,这里主要想说明两点问题:
其次,客户端与服务端是两个完全独立的模块,说白了,虽然我们会编写客户端代码,但它不属于服务的一部分,而是调用方服务的一部分。客户端的数据压缩应该尽量与服务端解耦,切不可为了贪图实现方便,将两者的数据格式耦合在一起,与服务端的数据通信格式应该理解为一种独立的协议,正如服务端与数据库的通信一样,数据通信格式与数据库的存储格式没有任何关系。
内存管理——缓存与分代回收的矛盾
缓存的目标是让热数据(频繁被访问的数据)能够留在内存,以便提高缓存命中率。而JVM垃圾回收(GC)的目标是释放失去引用的对象的内存空间。两者目标看上去相似,但细微的差异让两者在高并发的情景下很难共存。缓存的淘汰会产生大量的内存垃圾,使FullGC变得非常频繁。这种矛盾其实不限于客户端,而是所有JVM堆内缓存共同面临的问题。下面我们仔细分析一个场景:
随着请求产生的数据会不断加入缓存,QPS较高的情形下,YoungGC频繁发生,会不断促使缓存所占用的内存从新生代移向老年代。缓存被填满后开始采用LeastRecentlyUsed(LRU)算法淘汰,冷数据被踢出缓存,成为垃圾内存。然而不幸的是,由于频繁的YoungGC,有很多冷数据进入了老年代,淘汰老年代的缓存,就会产生老年代的垃圾,从而引发FullGC。
伟彬,美团平台及酒旅事业群数据挖掘系统工程师,2015年毕业于大连理工大学,同年加入美团点评,专注于大数据处理技术与高并发服务。
【思考题】
文中提到高QPS下Java堆内缓存容易产生FullGC问题从而影响系统性能,其实GC是Java的一把双刃剑。“Java与C++之间有一堵由内存动态分配和垃圾收集技术所围成的‘高墙’,墙外面的人想进去,墙里的人想出来”。聊一聊你在工作中遇到的GC问题,以及如何解决的吧~