bytegraph.docx
10墨值下载
字节跳动的分布式图数据库：
一、
ByteGraph2.0
1
、架构
底层存储依赖于一个分布式
存储，也是一个计算与存储分离的架构。一个
集
群由三层组成：执行层（
）、内存
层（
）、基于一个持久化
存储的存储层。
执行层注意处理计算密集型操作，比如排序和聚合，
关注原生
数据管理和日志
管理。每一层都可以独立扩展。持久化存储层存储
产生的所有
对儿（图数据、
和元数据）。
存储层可以使用
、
等，在
中作为一个黑盒存在。
使用
查询语言；提供了
和
优化器，为了增加
率，使用一致性
算法将图进行逻辑分片，每个分片映射到一个
实例。因此，
同一个分片上的点进行了分组并通过
打包发送给关联的其他
实例进行进一步处理。
BGE
通过监控心跳，维护一个全局
BGS
实例的视图，并且分布式事务使用
2PC
协议。
可以在多个机器上部署各自的
，相当于一个缓存层，
!"
每个节点一个
##
，通过
算法分片到一个
中，该
##
包括点的邻接表（边树）
$
）查询解析和重写：将
解析成语法树并将其改写成执行计划，并支持查询计
划缓存
）优化器基于规则和代价的优化：
RBO
主要基于
Gremlin
开源实现中自带优化规则、
针对字节应用的算子下推、自定义的算子优化；
CBO
本之上对每个点的出入度做统
计，把代价用方程量化表示
%
）执行器基于
&
：理解
数据分
##
逻辑，找到相应数据并下
推部分算子，保证网络开销不会天大，最后合并查询结果
2
、数据存储
也采用属性图模式管理图。图
%
中的例子，有两个点类型（
'
、
）和
(
个
边类型（
)
、
、
、
*+
）；点和边的类型不同，
schema
也不同，比如点
（
',-.
，
,.
）。
$
）内存中分别以
/&
和
&
缓存点和边
）每个点和它的属性构成
对儿，
是唯一
0
和点类型，
1
是点属性链表，将
他们一起存储在
中
%
）图
%
中
'&2
的
是
32-'4
。访问点属性：
使用
56
请求
存储，并将该
对儿放到
/&
中；一旦点的任何属性被更改，都会通过
56
立即刷到
磁盘
(
）边以邻接表形式组织，边的
：
3
起点
10-
起点
1--4
，汇聚成一个
，再把
&
组织成
-
有自己独立的
72)
，多个
&
形成
一个森林，访问不同的邻接表时不需要做并发管理。图
(
所示，
有
%
种类
型点：
&8
、
9&8
、
&8
，每个都以
对儿存储。和
类似，
仅
&8
存储物理边数据。
:
）每种类型额节点都有一个上下边界大小用来平衡读写放大问题
;
）最开始，
有
层：
&
和
&
。
&
索引的
&
超
过了上界后，会创建
&
作为中间层索引
&
（和
<
的中间节点
功能类似），同样如果
&
大象超过它的上界，
&
会分裂成
个
；若两个
&
小于下届大象，会合并成一个。根据经验，将上下边界
设置成
$"""= """
，
%
层
的容量是八十亿，足够存储一个真实
的邻
接表
>
）每个边实例由目标点的
ID
、类型和边属性链表组成
?
）
中指定一个排序键进行排序，由边属性的
决定。默认无排序键时，
以
'5
插入的时间戳
6
排序，也可以根据真实负载进行配置或者动态调整
@
）通过
72)
功能异步更新
：更新先以
72)
持久化到磁盘，然后内存进行更
新，标记为
&
。
周期性将
&
刷盘
$"
）图
(
中，
维护一个全局
&)
表示包含
&
的
，将脏
插入该链表的条件：（
$
）最近一个
后
72)
量超过了阈值；或者
（
）
)'
链表中选择一个最少用的
，以腾出更多可用空间（和
0
的
A&
管 理 类 似 ） 。 一 个
的
72)
通 过 一 个 单 调 递 增 的
0
进 行
/
，
&
将最后持久化操作的
0
作为检查点。
3
、
edge-tree
是什么
一个
paron
（即一个
edge-tree
）的定义：一个起点
<&
一种特定边类型扇出的一跳所有邻
居。在
中将一个
##
按照排序键（可以显式设置或系统默认维护，即下图的
$
等）组成
Btree
，每个
都有独立的
72)
，独立维护自增
。如下图所示，
就是一个
：
$
）某一个起点的同一个边
的所有终点是一个存储单元，即一个
）一级存储形式：点的出度
3&
一个阈值时
（
$
）起点
0&<&
起点
&<&
边
&<&
方向作为
（
）同一个起点，相同
且相同方向的所有边组成一个
1
%
）多级存储形式（
）：点的出度超过阈值时，如上图
（
$
）所有边均匀切分成
，并分配对应
，所有
组成
数据
（
）
9
整 体 作 为
存 储 ，
表 示 ： （ 点 ， 边 类 型 ）
4
of 7
10墨值下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
最新上传
下载排行榜
1
2
9-数据库人的进阶之路：从PG分区、SQL优化到拥抱AI未来（罗敏）.pptx
3
1-PG版本兼容性案例（彭冲）.pptx
4
2-TDSQL PG在复杂查询场景中的挑战与实践-opensource.pdf
5
6-PostgreSQL 哈希索引原理浅析（文一）.pdf
6
3-AI时代的变革者-面向机器的接口语言(MOQL)_吕海波.pptx
7
8-基于PG向量和RAG技术的开源知识库问答系统MaxKB.pptx
8
4-IvorySQL V4：双解析器架构下的兼容性创新实践.pptx
9
7-拉起PG好伙伴DifySupaOdoo.pdf
10
《云原生安全攻防启示录》李帅臻.pdf
相关文档
评论