快速的未来即将在您的城市举行活动。
加入我们在 Redis 发布活动
分享
TLDR：我们一直在开发一个图形数据库，它将查询转换为线性代数问题，结果是一个架构，可以在亚秒时间内对数百万个元素执行许多标准操作。
在开始开发近两年后，我们今天发布了 RedisGraph v1.0，这标志着一个重大里程碑。RedisGraph 是一种图形数据库架构，作为 Redis 模块 实现，使用 GraphBLAS 稀疏矩阵进行内部数据表示，并使用线性代数进行查询执行。它完全用 C 语言实现，并在 Linux 和 OS X 发行版上进行了测试。我们使用 Cypher 作为我们的查询语言，并期待与图形数据库社区一起努力实现 GQL！
在本博文中，我们将简要概述 RedisGraph 如何使用矩阵表示来解决传统的图形问题，分享一些性能基准，并讨论一些使我们的架构尽可能高效和通用的下一步措施。
矩阵是图形数据的经典编码格式，从直观的邻接矩阵开始：一个正方形表格，每个轴上都有所有节点，以及每个连接对的值。如果天真地实现，这种方法对于对现实世界问题进行建模的图形来说扩展性很差，这些图形往往非常稀疏。矩阵的空间和时间复杂度由其维度决定 (O(n²) 对于方阵而言)，这使得邻接表等替代方法对于大多数具有扩展要求的实际应用更具吸引力。
对于 RedisGraph，我们采用了 GraphBLAS 库，以获得矩阵表示的优势，同时针对稀疏数据集进行优化。（特别感谢 Tim Davis，他与我们密切合作，以尽可能有效地整合他的工作！）
GraphBLAS 以压缩稀疏列 (CSC) 形式对矩阵进行编码，其成本由包含的非零元素数量决定。总的来说，矩阵的空间复杂度为
(列数 + 1) + (2 * 非零元素数)
对于密集图，这仍然受限于 O(n2)，但对于完整的对角线（单位矩阵）仅为 3n + 1。
这种编码在空间上非常高效，并且还允许我们将图矩阵视为数学操作数。结果，数据库操作可以作为代数表达式执行，而无需首先将数据从某种形式（例如一系列邻接表）中转换出来。
GraphBLAS 接口允许我们的大多数库调用成为直接的数学运算，例如矩阵乘法和转置。这些调用是延迟评估的，并在幕后进行优化。
例如，让我们看一个包含 6 个节点的简单图，其中 4 个节点标记为 Person，2 个节点标记为 Country
我们将运行的 Cypher 查询为
MATCH (:person {name: ‘Jeff’})-[:friend]->(:person)-[:visited]->(:country)
这将找出我的朋友访问过哪些国家。该查询将有一个过滤操作，只选择具有匹配 `name` 属性的 `person` 节点，并且我们需要遍历两个邻接矩阵， `friend` 和 `visited`。
由于 CSC 编码中值的最小影响，我们的邻接矩阵始终代表所有节点 ID。这与使用人员作为行和国家作为列来表示诸如 `visited` 之类的矩阵形成对比。这两种情况下都显示了相同的关系，但 CSC 方法允许所有矩阵具有相同的维度，行/列索引描述了相同的实体。因此，我们可以将这些矩阵中的任何一个组合在代数表达式中，而无需先将它们转换为可比较的形式。
我们对此查询的起点将是 `friend` 邻接矩阵
我的节点 ID 为 0，因此此矩阵第一行的条目表示我朋友的 ID。目前，过滤器是在节点级别应用的，但我们目前正在开发的一种优化是在此阶段将它们应用于矩阵。这将导致一个修改后的邻接矩阵，其中只表示我的朋友
现在，我们取 `visited` 矩阵，它具有相同的维度并描述了按相同顺序排列的所有节点
通过将过滤后的 `friend` 矩阵乘以 `visited`，我们获得了将我的节点（作为行）连接到我的朋友访问过的国家（作为列）的矩阵
（出于空间优化的目的，我们实际上在此处使用布尔矩阵，因此实际上两个条目都将为 1。）
在真实数据集和更复杂的问题上测试数据库的性能产生了可喜的结果。
以下所有值都是使用 维基百科顶级类别 数据集在 2016 年款 MacBook Pro（2 GHz i5，16gb RAM）上构建的。生成的图形包含 1,791,489 个节点和 28,511,807 条边。
以下是我们取得的性能结果
一些说明
我们对 RedisGraph 的开发仍然非常活跃，我们面前最重大的任务是
这实际上是一个愿望清单！本着 Redis 的精神，RedisGraph 是一个开源项目，欢迎贡献者。如果您有任何意见，或者您有兴趣参与，请随时通过 GitHub 联系我们。
