关系图谱图引擎设计

1-小红书图引擎设计

关系图谱关注的业务问题

以小红书为例子.下图来自小红书

用户和笔记之间的关系有: 发布-publish, 点赞-like , 收藏-fav 和对应的反向关系, 被点赞，被收藏;

这个业务的主要压力来自读, 之前小红书存储在 Mysql 中, 百万的 qps 下 cpu 会达到 55% ;

Mysql 的成本太高, 而开源界也没有太成熟的方案. 目前主流公司的技术选择如下:

Facebook : Tao , 其本质是一个图缓存 + Mysql
Pinterest : Zen ，其本质是一个图缓存 + HBase
字节跳动: ByteGraph, 其本质是一个图缓存 + KV(ABase 或者 ByteKV)
LinkedIn : Voldemort, 其本质是一个 KV

图缓存构建，其本质是 Edge 和 Point

把关系抽为一个 KV, Key 是 (FromId, AssocType, ToId) 的三元组, value 是一个属性的 JSON, 比如说用户A 关注用户B.

小红书使用构建的图缓存. 下图来自小红书博客

首先看三级的嵌套 HashTable:
- 第一层的 key 是 from_id 对应的是一个 REDtaoGraph 对象, 这个对象中记录了所有的 type 也就是关系的出边信息
- 第二层的 key 是 type_id, 这里的某个特定 type 下的信息，包括这个行为下所有出边的计数，索引和元数据, time_index 是其中所有 to_id 的 跳表索引, 方便用创建时间查找.
- 第三层的 key 是 to_id, 就包含了最终的信息，其中记录的信息包括: 创建时间，更新时间，版本，json数据，还有一个 time_idex , 这一层同时控制缓存的容量，防止 OOM, 限制 1000个边信息.

一个简单的伪代码表达如下:

class ToIdInfo {  
    long createTime;
    long updateTime;
    int version;
    String jsonData;
}
 
class REDtaoQueue {
    // REDtaoQueue类的定义：每个队列应该至少有一个元数据请求
    // 具体内容根据业务实际需求添加
}
 
class AssocType {
    // 容量受限的跳表和哈希Map
    LimitedSizeSkipListMap<Long, ToIdInfo> timeIndex; // 存储最新的1000个边信息
    HashMap<String, ToIdInfo> toIdInfoMap; // 嵌套的第三层HashMap
    REDtaoQueue queue; // 每个AssocType包含一个队列实例，用于读写请求
}
 
class REDtaoGraph {
    HashMap<String, AssocType> type;
}
 
public class Main {
    HashMap<String, REDtaoGraph> fromIdMap = new HashMap<>();
 
    void processRequest(REDtaoQueue request) {
        String fromId = request.getFromId();
        String typeId = request.getTypeId();
 
        // 从第一级HashMap中获取REDtaoGraph
        REDtaoGraph graph = fromIdMap.get(fromId);
        if (graph == null) {
            graph = new REDtaoGraph();
            fromIdMap.put(fromId, graph);
        }
 
        AssocType assocType = graph.type.get(typeId);
        if (assocType == null) {
            // 缓存不存在，则创建只包含一个REDtaoQueue的对象
            assocType = new AssocType();
            assocType.queue = request;
            graph.type.put(typeId, assocType);
        }
        else {
            // 缓存存在，插入新请求到队列 and 更新队列元数据
            assocType.queue = request;
        }
 
        // 异步执行队列中的请求
        // handleRequests(assocType.queue);
    }
}

简单理解

可能使用 JVM 堆的缓存
主要是考虑到性能的成果

2-Open Source Solution

开源的各种解决方案

我们基本可以理解其他的系统也是类似的思路.

把 Mysql 或者 HBase 系统作为底层的存储引擎，然后上层部署一个图缓存的思路.

我们这里是实现打算使用 janusgraph 来做, 他是一个专业的, 开源的 图引擎数据库. 这个选择有趣的点在于:

他支持 ACID 事务和最终一致性
支持水平扩展
他的存储引擎是可插拔的, 目前官方支持了如下几种
1. Cassandra
2. HBase
3. Google Cloud 的 BigTable
4. Oracle 的 berkeleydb
5. ScyllaDB
6. …

他有一些成功的实践，例如 EBay 和 Redhat 都把他用在了生产环境.

至于底层的引擎选择: 使用 scylladb 是个不错的选择.

IBM 曾经对比过这三个技术直接作为底层的引擎. 参考 ScyllaDB as the JanusGraph storage backend vs. Apache Cassandra and HBase .
- 插入节点的时候看吞吐量. Scylla 35% > HBase ; Scylla 3倍 > Cassandra
- 插入 Edge 的时候看吞吐量 . Scylla 160% > HBase ; Scylla 400% > Cassandra
- 查询的基准测试, Scylladb 72% > Cassandra ; Scylla 150% > HBase

还有一些更有趣的实验，例如:

Zeotap : 200 亿 ID 级别的引擎, 基于 ScyllaDB 和 JanusGraph

3-Implementation By Kv

这个是使用 kv 引擎 ScyllaDB 的实现, 不支持特别复杂的图搜索

CREATE TABLE relations  
(  
    from_id   text,  
    relation text,  
    to_id   text,  
    create_at bigint,  
    PRIMARY KEY (from_id, relation, to_id)  
);  
  
CREATE MATERIALIZED VIEW relations_by_create_at AS  
SELECT from_id, relation, create_at, to_id  
FROM relations  
WHERE from_id IS NOT NULL  
  AND relation IS NOT NULL  
  AND create_at IS NOT NULL  
  AND to_id IS NOT NULL  
PRIMARY KEY (from_id, relation, create_at, to_id)  
WITH CLUSTERING ORDER BY (create_at DESC);  
  
  
  
-- 准备数据  
INSERT into relations(from_id, relation, to_id, create_at) VALUES ('u:1', 'create', 'n:1', 10);  
INSERT into relations(from_id, relation, to_id, create_at) VALUES ('u:1', 'create', 'n:2', 11);  
INSERT into relations(from_id, relation, to_id, create_at) VALUES ('u:1', 'create', 'n:3', 13);

下面是一个查询的 demo

  
  
-- 查询用户的 u:1 所有关系  
SELECT * FROM relations where from_id = 'u:1' ;  
  
-- 查询 某个用户 u:1 创建的所有 笔记  
SELECT * FROM relations where from_id = 'u:1' and relation ='create';  
  
-- 查询某个用户 u:1 是否创建了笔记 n:1
SELECT * FROM relations where from_id = 'u:1' and relation = 'create' and to_id = 'n:1';  
  
-- 查询  某个用户 u:1 最近创建的 1 个 note
SELECT * FROM relations_by_create_at where from_id = 'u:1' AND relation='create' AND create_at> 10 AND create_at < 14 ORDER BY  create_at DESC limit 1;

评估:

直接基于 scylladb 的性能应该非常的顶 ;
缺点: 不支持复杂的图查询，因为没有图索引 ;
如果有热点数据，可以考虑把 PRIMARY KEY ((from_id, relation), to_id) 来优化数据倾斜问题, 可能会好一些 ;
可以考虑利用再创建一个视图 (to_id, relation, from_id) 就直接支持了逆向关系的查询，例如被关注，被收藏 ;

对应的代码已经完整的实现在 github

4-Implementation By Graph

评估:

针对上面的简单查询性能损失不明显，针对图特有的复杂查询损失明显，吞吐量大概降低1倍左右
图的边天生就有入度和出度的方向概念，所以不存逆向关系的问题
由于选型的图引擎不仅仅本身做了一个 Cache, 还支持联合 Es 做混合模式的索引，所以功能上远比上面的强大

下面是一个简单的实现: 其实 gremlin 的语法风格应该就是 Groovy, 所以基本上命令行就是 代码实现

准备 schema

graph = JanusGraphFactory.open('conf/janusgraph-inmemory.properties')
mgmt = graph.openManagement()
mgmt.printSchema()
 
// 1. 边
// 关注边
 
follow = mgmt.makeEdgeLabel('follow').multiplicity(MULTI).make()
 
// 收藏边
fav = mgmt.makeEdgeLabel('fav').multiplicity(MULTI).make()
// 点赞边
like=mgmt.makeEdgeLabel('like').multiplicity(MULTI).make()
 
// 2. 点
userLabel = mgmt.makeVertexLabel('user').make()
noteLabel = mgmt.makeVertexLabel('note').make()
 
// 3. 属性
 
// 创建时间
createAt = mgmt.makePropertyKey('createAt').dataType(Long.class).cardinality(Cardinality.SINGLE).make()
// userId
userId = mgmt.makePropertyKey('userId').dataType(String.class).cardinality(Cardinality.SINGLE).make()
 
// noteId
noteId = mgmt.makePropertyKey('noteId').dataType(String.class).cardinality(Cardinality.SINGLE).make()
 
// 4. 定义约束, userId 的唯一性 和 noteId 的唯一性
mgmt.buildIndex('byUserIdUnique', Vertex.class).addKey(userId).unique().indexOnly(userLabel).buildCompositeIndex()
mgmt.buildIndex('byNoteIdUnique', Vertex.class).addKey(noteId).unique().indexOnly(noteLabel).buildCompositeIndex()
 
mgmt.commit()

添加数据

// 1. 增加用户
u1 = graph.addVertex(T.label, 'user', 'userId', 'u1')
u2 = graph.addVertex(T.label, 'user', 'userId', 'u2')
u3 = graph.addVertex(T.label, 'user', 'userId', 'u3')
u4 = graph.addVertex(T.label, 'user', 'userId', 'u4')
 
 
g = graph.traversal()  // 获取一个新的图遍历对象
users = g.V().hasLabel('user').valueMap('userId').toList()  // 获取所有 "user" 顶点的 "userId" 属性
 
 
// 2. 用户关注用户
u1.addEdge('follow', u2)
u1.addEdge('follow', u3)
u2.addEdge('follow', u4)
 
g = graph.traversal()  // 获取一个新的图遍历对象
g.V().has('user', 'userId', 'u1').out('follow').values('userId').toList()
 
 
// 3. 增加笔记
n1 = graph.addVertex(T.label, 'note', 'noteId', 'n1');
n2 = graph.addVertex(T.label, 'note', 'noteId', 'n2');
n3 = graph.addVertex(T.label, 'note', 'noteId', 'n3');
n4 = graph.addVertex(T.label, 'note', 'noteId', 'n4');
 
 
// 4. 增加收藏关系
//
u1.addEdge('fav', n1);
u2.addEdge('fav', n1);
u2.addEdge('fav', n2);
u2.addEdge('fav', n3);
u3.addEdge('fav', n3);
u3.addEdge('fav', n4);
graph.tx().commit();

简单的2个查询.

// 1. 深度查询
// 思路: 从 u1 出发，找到 u1 关注的人和  二度关注的人 然后 union 起来
 
g.V().has('user', 'userId', 'u1').union(out('follow'), out('follow').out('follow')).dedup().values('userId').toList()
 
 
// 2. 基于 用户的关注关系 给 u1 推荐笔记
// 思路:
// 1. 找到用户关注的人
// 2. 查询这些人收藏的笔记
g.V().has('user', 'userId', 'u1').out('follow').out('fav').toList()

Refer

小红书 REDtao: 小红书万亿的社交网络关系
字节 ByteGraph: 字节跳动的万亿级图引擎设计
Zen : Pinterest Graph Storage Service 基于 HBase

🪴 Quartz 4.0

Explorer

关系图谱图引擎设计

1-小红书图引擎设计

2-Open Source Solution

3-Implementation By Kv

4-Implementation By Graph

Refer

Graph View

Table of Contents

Backlinks