关于索引:得物推荐引擎-DGraph

6次阅读

共计 4591 个字符，预计需要花费 12 分钟才能阅读完成。

随着得物业务规模的一直减少，举荐业务也越来越简单，对举荐零碎也提出了更高的要求。咱们于 2022 年下半年启动了 DGraph 的研发，DGraph 是一个 C ++ 我的项目，指标是打造一个高效易用的举荐引擎。举荐场景的特点是表多、数据更新频繁、单次查问会波及多张表。理解这些特点，对于举荐引擎的设计十分重要。通过浏览本文，心愿能对大家理解举荐引擎有肯定帮忙。为什么叫 DGraph？因为举荐场景次要是用 x2i(KVV)表举荐为主，而 x2i 数据是图 (Graph) 的边，所以咱们给得物的举荐引擎取名 DGraph。

DGraph 能够划分为索引层 & 服务层。索引层实现了索引的增删改查。服务层则蕴含 Graph 算子框架、对外服务、Query 解析、输入编码、排序框架等偏业务的模块。

图 1

在 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

数据一致性

相比订单、交易等对于数据一致性要求十分严格的场景。在搜推场景，数据不须要严格的一致性，只须要最终一致性。若一个集群有 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

举荐存储引擎最开始只提供了简略的数据查问 & 数据补全性能，因为扩招回须要，前期又引入了算子框架，初步提供了根本的多算子交融调度能力(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

DGraph 是得物在举荐业务上一次十分胜利的摸索，并在算法指标、稳定性、机器老本等多方面获得了收益。搜推场景是互联网中算力开销特地大的场景之一，数据更新频繁，日常业务迭代简单，因而对系统的挑战十分高。在 DGraph 的研发过程中，咱们投入了十分多的精力在零碎的稳定性 & 易用性下面，积攒了很多些教训，简略总结下：1）平台侧须要做好数据的校验，数据的增删的改是搜推场景最容易引发事变的源头。2）提供灵便的 API，类 SQL 或者 DAG 都能够，在 C ++ 外部做业务开发是十分危险的。3）索引必须是二进制构造并且采纳 mmap 形式加载，这样即便产生解体的状况，零碎能够在短时间疾速复原，日常调试重启等操作也会很快。

* 文 / 寻风

本文属得物技术原创，更多精彩文章请看：得物技术官网
未经得物技术许可严禁转载，否则依法追究法律责任！

正文完