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>。引荐引擎绝大部分表都是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方法加载，这样即便产生崩溃的状况，体系能够在短时间快速恢复，日常调试重启等操作也会很快。
*文/寻风
本文属得物技能原创，更多精彩文章请看：得物技能官网
未经得物技能答应严禁转载，否则依法追究法律责任！
