1 前言
随着得物业务规模的一直减少,举荐业务也越来越简单,对举荐零碎也提出了更高的要求。咱们于2022年下半年启动了DGraph的研发,DGraph是一个C++我的项目,指标是打造一个高效易用的举荐引擎。举荐场景的特点是表多、数据更新频繁、单次查问会波及多张表。理解这些特点,对于举荐引擎的设计十分重要。通过浏览本文,心愿能对大家理解举荐引擎有肯定帮忙。为什么叫DGraph?因为举荐场景次要是用x2i(KVV)表举荐为主,而x2i数据是图(Graph)的边,所以咱们给得物的举荐引擎取名DGraph。
2 注释
2.1 整体架构
DGraph能够划分为索引层&服务层。索引层实现了索引的增删改查。服务层则蕴含Graph算子框架、对外服务、Query解析、输入编码、排序框架等偏业务的模块。
图1
2.2 索引框架
在DGraph外面参考图1,索引的治理被形象成5个模块:Reader 索引查问、Writer 索引写入、Compaction 增量全量合并、LifeCycle 索引生命周期治理、Schema 索引配置信息。
不同类型的索引只须要实现下面的5个类即可,不同类型的索引只须要关注索引自身的实现形式,而不须要关怀索引的治理问题,通过这种模式,索引治理模块实现了索引的形象治理,如果业务须要,能够疾速在DGraph面退出一种新的索引。
DGraph数据的治理都是按表(table)进行的(图2),简单的索引会应用到DGraph的内存分配器D-Allocator,比方KVV/KV的增量局部 & 倒排索引 & 向量索引等。在DGraph所有数据更新都是DUMP(耗时)->索引构建(耗时)->引擎更新(图3),索引平台会依据DGraph引擎的内存状况主动抉择在线更新还是分批重启更新。这种形式让DGraph引擎的索引更新速度&服务的稳定性失去了很大的晋升。
图2
图3
2.3 索引
数据一致性
相比订单、交易等对于数据一致性要求十分严格的场景。在搜推场景,数据不须要严格的一致性,只须要最终一致性。若一个集群有N个引擎,通过增量向集群写入一条数据,每个引擎是独立更新这条数据的,因为是独立的,所以有些机器会更新快一点,有些机器会更新慢一点,这个时间尺度在毫秒级左近,实践上在某一时刻,不同引擎上的数据是不统一的,但这对业务影响不大,因为最终这些数据会保持一致。
最终一致性这个个性十分重要,因为实现严格的一致性很简单,2PC&3PC等操作在分布式场景下,代价很高。所以事件就变得简略了很多,引擎的读写模型只须要满足最终一致性即可。这能够让咱们的零碎,更偏差于提供更高的读性能。这个前提也是DGraph目前很多设计的根因。
读写模型
举荐场景须要反对在线服务更新数据,因而引擎有读也有写,所以它也存在读写问题。另外引擎还须要对索引的空间进行治理,相似于JAVA零碎外面JVM的内存管理工作,不过引擎做的简略很多。读写问题常见的解决方案是数据加锁。数据库和大部分业务代码外面都能够这么做,这些场景加锁是解决读写问题最靠谱的抉择。然而在举荐引擎外面,对于读取的性能要求十分高,外围数据的拜访如果引入锁,会让引擎的查问性能受到很大的限度。
举荐引擎是一个读多写少的场景,因而咱们在技术路线上抉择的是无锁数据结构RCU。RCU在很多软件系统外面有利用,比方Linux 内核外面的kfifo。大部分RCU的实现都是基于硬件提供的CAS机制,反对无锁下的单写单读、单写多读、多写单读等。DGraph抉择的是单写多读+提早开释类型的无锁机制。效率上比基于CAS机制的RCU构造好一点,因为CAS尽管无锁,然而CAS会锁CPU缓存总线,这在肯定水平上会影响CPU的吞吐率。
如果简略形容DGraph的索引构造,能够了解为实现了RcuDoc(正排)、RcuRoaringBitMap(倒排)、RcuList、RcuArray、RcuList、RcuHashMap等。用举荐场景可推池来举一个例子,可推池表的存储构造能够形象成RcuHashMap<Key, RcuDoc> table。这里用RcuList来举例子,能够用来了解DGraph的RCU机制。其中MEMORY_BARRIER是为了禁止编译器对代码重排,避免乱序执行。
图4
图5
图5是删除的例子,简略讲一下,在RcuList外面,删除一个元素的时候,比方Node19,因为删除期间可能有其余线程在拜访数据,所以对List的操作和惯例的操作有些不同,首先将Node11的Next节点指向Node29,保障前面进来的线程不会拜访Node19,而后把Node19的Next指向Null,因为这个时候可能还有线程在拜访Node19,因而咱们不能立刻把Node19删除,而是把Node19放入删除队列,提早15秒之后再删除,另外删除的动作不是被动的,而是由下一个须要申请内存的操作触发,因而删除是延时且Lazy的。
数据长久化
在DGraph外面咱们构建了一个内存分配器D-Allocator(每个索引只能申请一个/可选),用于存储增量或者倒排索引等简单数据结构。采纳了相似TcMalloc按大小分类的管理模式。D-Allocator利用Linux零碎的mmap办法每次从固定的空间申请128M ~ 1GB大小,而后再按块划分&组织。由零碎的文件同步机制保证数据的长久化。目前64位x86 CPU理论寻址空间只有48位,而在Linux下无效的地址区间是 0x00000000 00000000 ~ 0x00007FFF FFFFFFFF 和 0xFFFF8000 00000000 ~ 0xFFFFFFFF FFFFFFFF 两个地址区间。而每个地址区间都有128TB的地址空间能够应用,所以总共是256TB的可用空间。在Linux下,堆的增长方向是从下往上,栈的增长方向是从上往下,为了尽可能保证系统运行的安全性,咱们把0x0000 1000 0000 0000 到 0x0000 6fff ffff ffff调配给索引空间,一共96TB,每个内存分配器能够最大应用100GB空间。为了方便管理,咱们引入了表keyID,用于固定地址寻址,表地址 = 0x0000 1000 0000 0000 + keyId * 100GB, 引擎治理平台会对立治理每个集群的keyId,偶数位调配给表,奇数位保留作为表切换时应用。keyId 0 - 600 调配给集群独享表,keyId 600-960调配给全局表。因而单个集群能够最多加载300个独享表+最多180共享表(备注:不是所有表都须要D-Allocator,目前没有增量的KVV/KV表不受这个规定限度)。
图6
KV/KVV索引
KV -> Map<Key, Object> 、 KVV -> Map<Key, List<Object>>。举荐引擎绝大部分表都是KVV索引,数据更新特点是,定期批量更新 & 大部分表没有实时增量。针对这些业务个性,DGraph设计了内存紧凑型KV\KVV索引(图7)。这里简略讲一下DenseHashMap的实现,传统的HashMap是ArrayList+List或者ArrayList+红黑树的构造。DGraph的DenseHashMap,采纳的ArrayList(Hash)+ArrayList(有序)形式,在ArrayList(Hash)任意桶区域,存储的是以后桶的首个KVPair信息,以及以后桶Hash抵触的个数,抵触数据地址偏移量,存储在另外一个ArrayList(有序)地址空间上(Hash抵触后能够在这块区域用二分查找疾速定位数据)。这种构造有十分好的缓存命中率,因为它在内存空间是间断的。然而它也是有毛病的,不能批改,全量写入也非常复杂。首先咱们要把数据加载到一个一般的HashMap,而后计算每个Hash桶下面元素的个数,晓得了桶的数量和每个桶上面的元素个数,遍历HashMap,把数据固化成DenseHash。KV/KVV的增量局部则是由RcuHashMap + RcuDoc基于D-Allocator(图6)实现。
图7
Invert索引
基于开源RoaringBitmap实现的RCU版本(基于D-Allocator实现)。RoaringBitmap 将一个文档ID(uint32)分为高位和低位,高16位的ID用来建一级索引,低16位的ID用来构建二级索引(原文称之为Container),在二级索引中,因为2^16=65536,一个short占用空间16bit,65536刚好能够存储4096个short,因而当分段内文档数量少于等于4096是,用short数组存储文档,当分段内的文档数量大于4096时则转为Bitmap存储,最多能够存储65536个文档。这种设计对于稠密倒排&密集倒排在存储空间利用率&计算性能上都体现优异。
图8
Embedding索引
基于开源的Kmeans聚类。Kmeans聚类后,引擎会以每个核心向量(centroids)为基点,构建倒排,倒排的数据结构也是RoaringBitmap,同一个聚簇的向量都回插入同一个RoaringBitmap外面。这样的益处是,能够在向量检索中蕴含一般文本索引,比方你能够在向量召回的根底上限度商品的tile必须要蕴含椰子、男鞋、红色等文本信息。
图9
2.4 算子调度框架
举荐存储引擎最开始只提供了简略的数据查问&数据补全性能,因为扩招回须要,前期又引入了算子框架,初步提供了根本的多算子交融调度能力(Merge/LeftJoin/Query),能够将屡次引擎查问合并为单次查问,升高召回RT, 晋升召回能力。老的框架有很多问题:1)只提供了JAVA API接入,API可解释性比拟差,用户接入上存在肯定艰难。2)算子调度框架效率偏低,采纳OMP+阶段策略调度,对服务器硬件资源利用率偏低,局部场景集群CPU超过20%后99线95线即开始好转。3)Graph运行时两头数据采纳行式存储,在空间利用率和运算开销上效率低,导致局部业务在迁徙算子框架后RT反而比之前高。4)短少调试 & 性能剖析伎俩。
DGraph前期针对这些问题咱们做了很多改良:1)引入了Graph存储,用于能够通过传入GraphID拜访一个图,配合引擎治理平台的DAG展现&构图能力,升高图的应用门槛。2)开发了全新的调度框架:节点驱动+线程粘性调度。3)算子两头后果存取等计算开销比拟大的环节,通过引入了列存储,虚构列等无效的升高了运行时开销。上线后在均匀RT和99线RT都获得了不错的后果。
图10
3 后记
DGraph是得物在举荐业务上一次十分胜利的摸索,并在算法指标、稳定性、机器老本等多方面获得了收益。搜推场景是互联网中算力开销特地大的场景之一,数据更新频繁,日常业务迭代简单,因而对系统的挑战十分高。在DGraph的研发过程中,咱们投入了十分多的精力在零碎的稳定性 & 易用性下面,积攒了很多些教训,简略总结下:1)平台侧须要做好数据的校验,数据的增删的改是搜推场景最容易引发事变的源头。2)提供灵便的API,类SQL或者DAG都能够,在C++外部做业务开发是十分危险的。3)索引必须是二进制构造并且采纳mmap形式加载,这样即便产生解体的状况,零碎能够在短时间疾速复原,日常调试重启等操作也会很快。
*文/寻风
本文属得物技术原创,更多精彩文章请看:得物技术官网
未经得物技术许可严禁转载,否则依法追究法律责任!