从一到无穷大 #29 ByteGraph的计算,内存,存储三级分离方案是否可以通用化为多模数据库

在这里插入图片描述本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

本作品 (李兆龙 博文, 由 李兆龙 创作),由 李兆龙 确认,转载请注明版权。

文章目录

  • 引言
  • ByteGraph现有架构
    • 阿里云Lindorm
    • 腾讯YottaDB
    • 多模型化修改点
    • ByteGraph论文中的优化点概述
      • Dynamic Thread Pools
      • Adaptive Secondary Edge-Trees
      • Space Optimized Bw-tree Forest
      • Read Optimized Bw-tree / Workload-Aware Space Reclamation
      • I/O Efficient Synchronization Mechanism
  • 结束语

引言

学习友商优点始终是审视自身的最好方法。ByteGraph不愧是业界著名的图数据库团队,vldb2022的《ByteGraph: A High-Performance Distributed Graph Database in ByteDance》和 sigmod2024的《BG3: A Cost Effective and I/O Efficient Graph Database in ByteDance》可以看出其扎实的工程能力,也同时为我们展现了ByteGraph的基本架构方法和一些细节的优化手段,相关经验对同领域从业人员有不小的启发。

《ByteGraph: A High-Performance Distributed Graph Database in ByteDance》阐述了ByteGraph的计算,内存,存储三级分离方案;而《BG3: A Cost Effective and I/O Efficient Graph Database in ByteDance》则通过改进BGS的BW树实现和利用贴合业务的使用方式提升访问性能和减少IO放大,以及改进读写节点和只读节点的数据同步方法入手阐述优化方案;

本篇文章简单阐述两篇论文中的细节优化点,而后从架构入手对比现有部分时序数据库,多模数据库的架构,讨论其通用性,并探讨其扩展至多模数据库的可能性。

当然ByteGraph作为大规模工业级图数据库,自然没有必要强转为多模型数据库,这个论题事实上也是在看多模数据库如果要实现一个图模态是否需要大规模的人力消耗。

ByteGraph现有架构

在这里插入图片描述

非常经典的计算,内存,存储三级分离方案;

ByteGraph的核心设计原则为:

  1. 存算分离:不同的工作负载对不同的资源有不同的利用率
  2. 使用缓存加速查询,并提高缓存命中率
  3. 高扩展性:需要应对爆炸性的增长,毕竟抖音/tiktok这种应用可能部分视频存在短时间千万级别的点赞/评论/转发等
  4. 平衡读写放大,获取整体最佳性能

请添加图片描述

事实上当今的nosql的架构非常相似,这也是为什么多模数据库人效比如此之高的原因,各个功能模块的组织和引擎的定制优化才是各个系统之间关键的对比点。

BGE:

  1. BGS的路由
  2. 查询解析,逻辑计划构建,查询优化,执行计划构建
  3. 执行计划执行
  4. 事务

BGS:

  1. 边,点,索引存储
  2. 构建存储格式,执行持久化至持久化存储层
  3. wal

Persistent Store

  1. 持久化存储

阿里云Lindorm

其实对比阿里云Lindorm的顶层架构:
在这里插入图片描述
可以发现基本架构完全相同,但是细节实现存在差异。

LindormByteGraph
计算层/BGE多写入协议,统一sql支持,分布式计算引擎,AI引擎Gremlin协议,本地计算引擎
数据引擎层/BGS多种模态定制化存储引擎缓存+图模态定制化存储引擎
存储层/Persistent Store统一访问协议分布式文件系统,存储介质可变,保证持久性KV Store

从这里就可以看出,ByteGraph可以认为是高度优化的图数据库,但是想从当前架构转为多模型数据库需要的工作较多。

腾讯YottaDB

在这里插入图片描述
图片取自公开技术文章。

腾讯YottaDB也是一个多模型数据库,从架构图可以看到和Lindorm的架构高度类似,控制面以及共有链路抽离,各模态拥有定制化存储引擎。

当然YottaDB的架构可以从图中看出没有统一API的高可用存储层,这也意味着系统本身需要实现一致性和高可用性,并需要考虑不同的模态的降冷,迁移,分裂,合并等一系列需求。

多模型化修改点

  1. 未提及控制面的实现,一个支持多模型的分布式控制面并不容易。
  2. BGS的扩缩容基于一致性哈希,似乎并不是多租户,这无法实现多模型部署在一个集群。
  3. BGS缺乏计算能力,对于类sql的模态无法执行大规模并行计算,这点可以参考[3],时序模态大多需要执行类似TiKV的coprocessor,当然实际会更加复杂。
  4. 存储层需要统一访问API,KV模态作为持久化层局限性太大,对于列存需求的模态存储量一定会成为瓶颈。

所以另起炉灶最好,不要基于现有系统改。

ByteGraph论文中的优化点概述

Dynamic Thread Pools

BGS中创建两个线程池,分别处理轻型请求和重型请求,因为请求具有突发特性,扩容来不及,所以基于排队任务的平均数量调整不同池子的线程,已保证服务质量,一方不会挤兑另外一方。

这样的做法还是比较常见的。

[8]中也用类似的手段分离从对象存储获取数据和本地计算的分离,不过其作用是为了最大化整体吞吐量;

在我们的时序数据库实现中我们用不同的池子来分离写请求,小查询和大查询,保证三者之间不会出现挤兑至无法服务的情况。

Adaptive Secondary Edge-Trees

Edge-Tree是 BGS 上构建索引的基本数据结构,以方便在邻接表中使用排序键进行搜索。但是,如果搜索关键字与排序关键字不匹配,则仍需要对整个Edge-Tree进行扫描,这将导致 CPU 占用率高和缓存丢失的可能性大。

因此, BGS 提供了一个Secondary Edge-Tree ,根据另一个边属性对邻接列表进行排序。二级边缘树建立后,指向新边缘树的指针会被添加到 Edge Storage 中,形成邻接列表的森林(图 6(b))。

在这里插入图片描述

如果邻接表的大小较小或访问频率较低,构建新的 Edge-Tree 并不能提高缓存命中率,反而会占用更多空间。所以使用基于阈值估算的方法评估是否构建Secondary Edge-Tree,算法有兴趣可以查询原文[1]。

Space Optimized Bw-tree Forest

请添加图片描述

基于几个关键的业务特征:

  1. 超高并发场景会导致 Bw 树写入大量冲突,造成写入重试和等待,大大降低了并发写吞吐量。
  2. 不同用户节点之间的读写完全独立,互不干扰
  3. 简单地将每个用户对应的所有边划分到不同的 Bw 树中,可以有效解决大量并发写入冲突的问题。但是这种方法会造成额外的空间浪费。

首先将所有用户的 ID 作为键存储在哈希表中,哈希表的值指向用户的 Bw 树。每个新用户的同类操作都集中记录在一棵初始 Bw 树中。当用户高度活跃时,该用户喜欢的视频会迅速增加,这很可能会导致 Bw-tree (INIT) 中出现高频率的写入冲突。用户的 Bw 树上的边越多,其被访问的频率就越高。允许为每个工作负载配置一个阈值。一旦用户的边数超过了这个阈值,他们的数据就会被分割并放入一棵独立的 Bw 树中。

很不错的优化方式,对于树状结构并发(写出冲突影响性能)还是有很大的提升的,同样的思路可以应用在不少冲突可能会影响性能的地方。

Read Optimized Bw-tree / Workload-Aware Space Reclamation

这两个方案都是在 Bw 树上优化IO,但是我没有 Bw 树的工程经验,也不好评价,但是文章本身写的很细致,有兴趣的同学可以深入学习下[2]。

I/O Efficient Synchronization Mechanism

在这里插入图片描述
在[1]中提到ByteGraph初始版本主副本之间同步是最终一致性。(这个架构其实我有一个疑问,Slaves允许写,只不过不持久化到KVs,并把写转发给主,假如从成功,主失败,不就很长一段时间内不一致了吗。当然仍旧是最终一致性,因为持久化只有一个KVS)

请添加图片描述

简单看下这个神奇的同步步骤:

  1. 当 RW 节点在接收到 Put(5,V5) 请求时,会触发 RW 内存中 Bw-tree 节点的拆分,产生脏页。通过WAL记录整个 Bw树的拆分过程,其中LSN范围为 30 到 32。
  2. WAL 在 RW 更新后立即写入共享存储空间。
  3. RO 节点立即读入 WAL,缓存在内存中。用户触发 Get(2) 和 Get(3) 操作。这些操作会导致 RO 缓存中的页面 P 和 Q 出现缓存缺失操作。
  4. wal的回放使用 lazy replay mechanism,使用日志 LSN 30 将 RO 中的缓存页面 O 更新为与 RW 的 O’ 相同的状态,会导致 RO 缓存中的页面 P 和 Q 出现缓存缺失操作。
  5. RO 节点会查找共享存储中的旧映射以获取页面 P。
  6. 对 P 重放相关日志(LSN 32)。当存储中的旧映射不包含 WAL 中记录的页面(页面 Q)时,表明该页面是新生成的。RO 节点会直接在 6 处的内存中创建它。此时,RO 节点内存中的数据与 RW 节点中的最新数据完全一致。
  7. RW 内存中的 Bw 树拆分产生的三个脏页面由后台线程池异步刷新到共享存储中。
  8. 脏数据刷新到附加数据区后,更新映射表来更新共享存储上的数据版本,并在 WAL 中同步写入日志,表明共享存储中的数据已完成截至 LSN 34 的所有修改。
  9. 一旦 RO 读取了该日志项,它就可以丢弃懒重放日志中 LSN 编号小于 34 的所有记录。

这一套机制实现难度不小,本质上wal并不是数据,而是有逻辑的更新流,实际的数据流是写入KVS的。

这个想法让我思绪良多,虽然内存时序数据库的并不是一个稀奇事[4][5][6],但是现有大规模应用的时序数据库据我所知没有专门的缓存模块,BG3中的多副本同步机制保证缓存副本间一致性(强一致性的缓存系统!)对于部分业务的时序数据来说是个杀器,就是这个WAL太不通用了,属于模态相关的特殊优化。

其实不止时序,KV模态也大有裨益,类似DAX[7]的系统可以加速SSD系统的用户查询。

结束语

ByteGraph是一个优秀的大规模图数据库系统,没有必要改为多模型数据库,虽然看起来多模型数据库可以快速实现一个图数据库,但是很难做到很多的特化优化,比如这个强大的wal同步机制,但是剩下的优化确实可以一个不落全部实现,就是存储层需要高度抽象以支持KV。

参考:

  1. ByteGraph: A High-Performance Distributed Graph Database in ByteDance vldb2022
  2. BG3: A Cost Effective and I/O Efficient Graph Database in ByteDance sigmod2024
  3. 从一到无穷大 #13 How does Lindorm TSDB solve the high cardinality problem?
  4. 从一到无穷大 #12 Planet-Scale In-Memory Time Series Database, Is it really Monarch?
  5. 从一到无穷大 #15 Gorilla,论黄金26H与时序数据库缓存系统的可行性
  6. 从一到无穷大 #16 ByteSeries,思考内存时序数据库的必要性
  7. Don‘t Put a Cache in Front of Database
  8. 从一到无穷大 #22 基于对象存储执行OLAP分析的学术or工程经验,我们可以从中学习到什么?

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/363191.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

项目实训-vue(十一)

项目实训-vue&#xff08;十一&#xff09; 文章目录 项目实训-vue&#xff08;十一&#xff09;1.概述2.页顶导航栏3.导航信息4.总结 1.概述 本篇博客将记录我在图片上传页面中的工作。 2.页顶导航栏 <divstyle"display: flex;justify-content: space-between;alig…

真正的IDEA在线版有多好用

前言 在上一篇文章使用过TitanIDE的VS Code在线版以后&#xff0c;尝到了不少甜头&#xff0c;紧接着又去使用了他的在线版IntelliJ IDEA&#xff0c;同样非常惊艳&#xff0c;不需要任何时间去适应这款云原生开发工具,事不宜迟&#xff0c;马上开整 这才是真正的VS Code在线版…

自制全网最便宜的雷达感应灯光画,成本只需5元

自制全网最便宜的雷达感应灯光画&#xff0c;成本5元 ​ 成本组成&#xff1a;带热释电的人体感应灯&#xff08;0.5元&#xff09;雷达感应模块&#xff08;3.5元&#xff09;首饰盒&#xff08;0.45元&#xff09;微喷油画布&#xff08;1元&#xff09;5.45元 ​ 说一下做灯…

未来科技中的RTK接收机应用探索

RTK实时差分定位技术&#xff08;RTK&#xff0c;Real-Time Kinematic&#xff09;&#xff0c;作为高精度定位技术的一种重要手段&#xff0c;已经在地理测绘、测量工程、航空航天等领域取得了广泛应用。随着科技的不断发展&#xff0c;RTK导航接收机的应用领域也日益拓宽。首…

Java鲜花下单预约系统源码小程序源码

让美好触手可及 &#x1f338;一、开启鲜花新篇章 在繁忙的都市生活中&#xff0c;我们总是渴望那一抹清新与美好。鲜花&#xff0c;作为大自然的馈赠&#xff0c;总能给我们带来无尽的惊喜与愉悦。但你是否曾因为工作繁忙、时间紧张而错过了亲自挑选鲜花的机会&#xff1f;今…

G882磁力仪拖鱼位置是如何计算的?

根据参考文献&#xff0c;磁力仪拖鱼位置计算有两种方法&#xff1a; 1、直线法 直线计算法是假设不考虑海流、船摆等动态因素的影响&#xff0c;拖鱼与拖点始终和航向相同&#xff0c;即整个拖拽系统与船舶是刚性连接。 2、曲线法 实际海洋磁力测量中&#xff0c;在海风、海…

从单一到多元:EasyCVR流媒体视频汇聚技术推动安防监控智能升级

随着科技的飞速发展&#xff0c;视频已成为我们日常生活和工作中的重要组成部分。尤其在远程办公、在线教育、虚拟会议等领域&#xff0c;视频的应用愈发广泛。为了满足日益增长的视频需求&#xff0c;流媒体视频汇聚融合技术应运而生&#xff0c;它不仅改变了传统视频的观看和…

计算机网络——数据链路层(数据链路层概述及基本问题)

链路、数据链路和帧的概念 数据链路层在物理层提供服务的基础上向网络层提供服务&#xff0c;其主要作用是加强物理层传输原始比特流的功能&#xff0c;将物理层提供的可能出错的物理连接改造为逻辑上无差错的数据链路&#xff0c;使之对网络层表现为一条无差错的链路。 链路(…

Windows部署MinIO,搭建本地对象存储服务

一、前言 二、MinIO介绍 三、Windows部署MinIO服务 1、准备工作 2、下载MinIO服务 3、启动MinIO服务 4、设置用户名密码 5、创建.bat文件启动服务 四、MinIO基本操作 1、存储桶管理 2、对象管理 3、数据查看 一、前言 基于外网的项目&#xff0c;可以使用阿里云等…

【MySQL】InnoDB的存储结构

InnoDB的存储结构&#xff1a;每个表都会生成一个表空间文件&#xff0c;这个文件里面最小结构就是行&#xff0c;存储的真正的数据&#xff0c;一个页来管理若干行&#xff0c;一个区来管理若干页&#xff0c;一个区组来管理若干区。段并不是真正的物理存储结构&#xff0c;它…

Kotlin设计模式:代理模式详解

Kotlin设计模式&#xff1a;代理模式详解 在软件开发中&#xff0c;设计模式是解决常见问题的一种优雅方法。本文将介绍Kotlin中的代理模式&#xff08;Proxy Pattern&#xff09;&#xff0c;其应用场景&#xff0c;以及如何通过实例代码实现这一模式。 代理模式的目的 代理…

YOLOV8图像分割预测后输出mask图

训练一个yolov8模型后&#xff0c;用官方的预测脚本一般是&#xff1a; results model.predict(img_path, saveTrue, save_diroutput_folder) 运行此代码会直接在run里面生成一个文件夹&#xff0c;保存预测图像。如果要获取分割后的mask点&#xff0c;或mask的轮廓点&#…

【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 螺旋矩阵填数(100分) - 三语言AC题解(Python/Java/Cpp)

&#x1f36d; 大家好这里是清隆学长 &#xff0c;一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 &#x1f4bb; ACM银牌&#x1f948;| 多次AK大厂笔试 &#xff5c; 编程一对一辅导 &#x1f44f; 感谢大家的订阅➕ 和 喜欢&#x1f497; &#x1f…

C#——里氏转换详情

里氏转换 里氏转换就是派生类的对象赋值给父类对象&#xff0c;反之则不行 实例 : 先创键一个类然后继承 调用

一种502 bad gateway nginx/1.18.0的解决办法

背景:上线的服务突然挂掉了 step1&#xff0c;去后端日志查看&#xff0c;发现并无异常&#xff0c;就是请求无法被接收 step2&#xff0c;查看了nginx的错误日志&#xff0c;发现该文件为空 step3&#xff0c;查看了niginx的运行日志&#xff0c;发现了以下问题 [error] 38#…

第4章,在 PyCharm 中创建、打开、关闭项目的操作

在 PyCharm 中创建、打开、关闭项目的操作 在PyCharm中创建、打开和关闭项目的操作步骤。以下是每个操作的步骤说明&#xff0c;以及在PyCharm界面中可能对应的区域&#xff1a; 1、创建新项目 1&#xff09;启动PyCharm&#xff1a; 打开PyCharm IDE。 2&#xff09;创建新…

第4章 客户端-客户端管理

1. 客户端API 1.1client list client list命令能列出与Redis服务端相连的所有客户端连接信息。 127.0.0.1:6379> client list id254487 addr10.2.xx.234:60240 fd1311 name age8888581 idle8888581 flagsN db0 sub0 psub0 multi-1 qbuf0 qbuf-free0 obl0 oll0 omem0 events…

C# 类中访问修饰符的优先级

参考链接 : C# 指南 - .NET 托管语言 | Microsoft Learn 访问修饰符 - C# | Microsoft Learn

Redis 内存碎片是什么?如何清理?

Redis 内存碎片相关的问题在得物、美团、阿里、字节、携程等公司的后端面试中都曾出现过&#xff0c;还是建议认真准备一下。即使不是准备面试&#xff0c;日常开发也是能够用到的&#xff01; 什么是内存碎片? 你可以将内存碎片简单地理解为那些不可用的空闲内存。 举个例子&…

计网实训——不相同网段的PC相互通信

目录 提前准备APP路由器指令 实验一1、实验需求&#xff08;1&#xff09;实现同网段的PC相互通信。&#xff08;2&#xff09;实现不相同网段的PC相互通信。&#xff08;3&#xff09;分析相同和不同网段PC通信时MAC地址的变化。 2、实验拓扑3、实验步骤及实验截图&#xff08…