近日，由 TiDB 社区主办，专属于寰球开发者与技术爱好者的顶级挑战赛事——TiDB Hackathon 2020 较量圆满闭幕。往年是 TiDB Hackathon 第四次举办，参赛队伍规模创历届之最，共有 45 支来自寰球各地的队伍报名，首次实现寰球联动。通过 2 天工夫的极限挑战，大赛涌现出不少令人激动的我的项目。为了让更多敌人理解这些参赛团队背地的故事，咱们将开启 TiDB Hackathon 2020 优良我的项目分享系列，本篇文章将介绍 TiGraph 团队赛前幕后的精彩故事。
新冠是当下惨重的话题，科技能够帮忙咱们去升高疫情造成的影响，比方在发现一个病例之后，惯例的措施都是依照一个地区的粒度进行隔离，如果咱们有更加弱小的图数据分析引擎，齐全能够把防疫这件事件做得更加精准和高效。
首先，咱们基于图数据库进行简略的建模：所有人都是这个图模型中的一个顶点，两个人接触之后，会生成一条分割，并新增一条对应的边。而后进行零碎的疾速实现：所有人都有微信或支付宝，咱们在这个零碎中新增一个顶点，当两个人接触间隔小一个值时，能够通过两个人的坐标或者 NFC 感应来失去这个间隔，小于某一个间隔，咱们就在零碎中新增一个边，并记录两个顶点的接触工夫。
基于这个模型，当咱们发现一个新冠病例之后，就能够利用图数据库进行剖析，疾速地（秒级）找出在指定工夫内接触过的人进行隔离，为防控疫情节俭大量的工夫和人工成本。
以上是图数据库在日常生活中的一个典型场景，图数据库是一个应用图构造进行语义查问的数据库，它应用节点、边和属性来示意和存储数据。Gartner 认为，图数据存储能够逾越数据孤岛、并无效地建模、摸索和查问数据，图剖析将在将来几年内高速增长，然而在关系型数据库（RDBMS）之上应用 SQL 查问实现相干剖析有点不切实际。
真的是不切实际吗？请 TiGraph 给你一个全新的答复！
在 TiDB Hackathon 2020 赛事中，TiGraph 我的项目在 TiDB 中实现了一套新的 Key-Value 编码来引入图模式，解决传统关系型数据库难以笼罩的图数据分析场景，并使得 TiDB 在四度人脉的计算性能晋升 8700 倍，一举夺得本届赛事的二等奖。
精妙的架构实现
在短短的 Hackathon 期间，要开发一个残缺的图数据库显然不太可能，TiGraph 我的项目尝试验证在 TiDB 中无缝集成图模式：
- 在 SQL 中扩大出一个让 DBA 一眼就能学会的图遍历语法
- 同一个事务中操作图数据和关系型数据的能力
- 将图遍历作为 SQL 子查问（反之亦然）
- 对于 N 度人脉场景的性能比照
TiGraph 的技术栈从下层到上层与 TiDB 是统一的，次要做的工作有两局部：第一局部是写入，在元数据管理方面新增了 TAG/EDGE 两个图的 Schema 类型，别离示意图的点和边，写入时如果发现写入对象的 Schema 是图的 TAG/EDGE 时，就用图数据的 KV 编码，而后就走 2PC 事务提交，这和 TiDB 的流程截然不同，没有区别。
第二局部是读链路，目前次要新增了两个执行算子，一个是 GraphTagReader 算子，用于读取图数据的点的数据。另一个是 Traverse 算子，用于依据指定的边进行图的遍历。因为图计算外面蕴含三局部，图的遍历、子图匹配和图聚合，这次 Hackathon Demo 次要是做图的遍历，前面去落地这个我的项目的时候，还须要把子图匹配和图聚合这些算子也设计进去。
震撼的性能体现
因为工夫无限，TiGraph 在 TiDB 外面仅实现了 Key-Value 的整套逻辑，没有工夫在 TiKV 中再用 Rust 从新实现一次，所以采纳 TiDB 内置用于跑测试的存储引擎 Unistore。对于数据规模的思考，一开始打算生成 100w 顶点 + 4000w 边，发现只有 TiGraph 能跑出后果。这是因为没有应用生产级别的散布存储引擎 TiKV，而是抉择用于跑单元测试的 Unistore，另外这也不是传统关系型数据库的劣势场景，所以 TiDB 跑不出数据。
于是采纳更小的数据集，在 10w 行数据 + 650w 条边的规模下，测试 N 度人脉场景下 TiDB + Unistore 与 TiGraph 的性能比照。从上图能够看到，TiGraph 能够跑完六度人脉的测试，然而 TiDB + Unistore 只能跑三度人脉，第四度人脉跑了 7 小时还没有出后果。随着人脉度的减少，TiGraph 的性能晋升越显著，二度人脉的性能晋升 190 倍，三度人脉的性能晋升 347 倍，四度人脉在无限的工夫内没有跑出最终后果，估算至多能够晋升 8700 多倍。 TiGraph 前期采纳 TiKV 存储后，在海量的图数据规模下也能弹性扩容，再配合 Coprocessor 实现图数据的计算下推，TiGraph 的查问性能还能再进一步晋升。
难点攻克：TiDB 与图数据库的交融
在同一个事务中解决图数据库和关系型数据，如果一个业务同时应用一个传统关系型数据库和图数据库，那么要在两个数据库中实现事务和强一致性，简直是根本不可能实现的工作，然而通过 TiGraph 能够杰出地实现。
首先，要设计一套与 SQL 极具兼容性、优雅且高扩大的语法，以下是目前两个十分风行的图查问语法两度人脉的示例：
在一套零碎中，引入两套查问语法会让用户学习老本更高，通过两天的探讨和碰撞，最终确定了如下示例的图遍历语法：
咱们将下面语句拆成两局部来看：
- SELECT … FROM… 语句的查问后果作为图遍历（TRAVERSE 子句）的终点
- 在 TRAVERSE 子句中指定想要遍历的 EDGE (边)，应用图遍历查问终点的二度人脉
如果咱们应用目前的 SQL 语法 (假如不做任何扩大) 写进去大略是：
通过以上比照咱们能够看出扩大后的语法是极具表达能力的，同时也十分 SQL-style，另一个益处是将图遍历的应用 TRAVERSE 子句表述后，就能够无缝和 TiDB 关系查问中的其余子句联结应用了，这样能够复用 TiDB 已有的执行算子和表达式等所有的计算能力，并且用户的学习老本也很低。比方咱们能够间接复用 WHERE/ORDER BY/LIMIT 子句（在编上加上过滤条件，将图遍历（TRAVERSE 子句）的输入后果作为前面 ORDER BY LIMIT 子句的输出）：
因为 TiDB 中的算子都依赖于强 Schema 的设计，为了复用 TiDB 中这些算子，TiGraph 中的 TAG 和 EDGE 也是强 Schema 的，这样图计算相干算子输入的 Schema 就能和关系型算子的 Schema 齐全兼容。TiDB 的下层算子并不需要晓得底层是图还是关系型数据，只有在最底层把之前的 TableScan 算子换成 GraphScan，对于下层来说，所有能力都是能够复用的。
在 SQL 层面有一篇学术论文做了相似的钻研，把 Stream 和 Batch 这两个试着用 SQL 去联合。目前，学术界还没有把 Graph 和 RDBMS 语法联合在一起的，TiGraph 我的项目实现了三个方面的翻新。
第一个方面是做出一套 SQL Style 的图遍历语法。第二个方面是事务能力，就是在同一个事务外面操作图和关系型数据的能力。依照以前的常规，用户必须要应用一个图数据库加上一个关系型数据库能力解决理论问题，然而要在两个数据库之间达成强统一基本上是不可能实现的工作，当初 TiGraph 具备这个能力，这是十分有魅力的，后续像子查问只须要在易用性和性能层面做晋升就好。
第三个方面就是在 TiKV 外面实现两种不同的编码模型，一种是给关系型的表编码的，一种是给 Graph 编码的。为了防止混合存储在一个 KV 的引擎外面产生抵触，通过加一个 g 的前缀使得整个 KV 在 Base 层面就齐全隔离，互不影响。
TiGraph 场景摸索
除了下面提到的新冠防疫场景之外，TiGraph 还将在金融反欺诈、社交网络、常识图谱等场景中发挥作用。
金融反欺诈
所谓近朱者赤近墨者黑，通过用户的关系网络来检测其与危险节点的关联度，可辨认出其危险水平并作为一个参考指标，比方某用户三度关系之内是否触黑（有时候看单个节点和单笔交易是很难发现问题的），利用 TiGraph 能够很好地进行关联度检测和剖析：
- 检测用户的多层社会关系是否合乎失常的图谱特色，如果是孤立的子图则可能是编造的关系网络，该用户存在高风险（包含黑 / 灰名单、高风险评分节点）
- 检测多层关系网络中是否蕴含高风险节点，比方二度触黑
- 通过 Personal Rank、Page Rank 等算法计算关系网络中节点的危险评分
对于有组织成规模的数字金融欺骗，TiGraph 能够从简单网络中疾速进行团伙剖析，为欺骗阻断提供及时的判断根据。
- 社交网络
大家在应用 Linkedin 的时候，发现有一个侧栏显示你的二度和三度人脉，社交平台通过剖析社交网络关系，来帮忙你扩大人脉圈子。TiGraph 能够在社交网络外面用作一个计算 N 度人脉的零碎，在此之外，还能够将这些社交网络与你的生产记录等信息进行联结，失去一些深层次的信息，进而来帮忙社交平台的举荐零碎进步转化率。TiGraph 能够突破数据之间的孤岛，建设隔离数据之间的连贯，产生 1 + 1 > 2 的成果。
- 常识图谱
常识图谱是 Google 公司在 2012 年提出来的一个概念，能够通过肯定办法把常识抽取和荡涤进去，而后在图数据库中提供查问。搜索引擎只能通知用户，查问的后果与哪些页面相干，用户须要肉眼在页面里找答案，而常识图谱能够间接把答案通知用户。举个例子，TiGraph 能间接通知你在《势力的游戏》中坦格利安家族的伊利亚丈夫的兄妹是谁，是不是很 Cool？
将来方向
将来想在两个方面进行尝试。首先，对于 TiGraph 我的项目的实现想写一篇论文，次要的方向有两个：第一个是如何在目前已有的关系型数据库（TiDB）外面去集成图模式；另外一个是具体的语法，须要去证实图计算的三个算子。
其次是 TiGraph 这个我的项目的工程落地，赛队小伙伴们心愿能进一步做深度的开发和实现工作。次要工作就是在 TiKV 外面把这一套 Key-Value 编码实现，并在 TiKV 的 Coprocessor 中实现图计算下推，从而买通整个链路，让图查问能够间接复用 TiDB 已有的执行算子和表达式，图查问和关系型查问也能够无缝联合。
TiGraph 背地的小伙伴
TiGraph 赛队的三位小伙伴都具备比拟扎实的技术功底，喜爱探讨和钻研新的技术方向，其中两位都是 TiDB 社区顶级的开发者（pingcap/tidb Contributors）：crazycs520 这个 GitHub ID 尽管有点土，然而位列 TiDB Contributions 总榜 Top 5，wjhuang2016 同学也是一位蠢才选手。
在 TiDB Hackathon 2020 期间，除了 TiGraph 我的项目之外，还诞生了很多前沿、乏味的我的项目，给 TiGraph 赛队小伙伴们留下了粗浅的印象：
- ‘ or 0=0 or ‘ 队伍的 UDF 实现十分优雅高效，也为这一部分的摸索画上了一个句话，当前大概率没有人能做出更加好的 UDF 实现了，当然这也是为什么能拿第一名的起因。
- B.A.D 的 VSC 扩大也是十分有创造性的，甚至在 Hachathon 期间曾经公布到 VSC Market 并取得两位数下载。
- GPU 减速计算关上了一个新世界的大门，对于 TPCH 中几个蕴含 JOIN Query 的性能晋升是十分不堪设想的。
- T4 组由孙晓光老师 Team 做的 TTL Table 是另一个我十分喜爱的我的项目，极其实用。
TiDB Hackathon 2020 把小伙伴们天马行空的想法变成了事实，在取得成就感的同时多了一份打动，咱们将从新登程，还有更多的惊喜值得期待！
——TiGraph 队长 龙恒