Titan如何使用HBase/Cassandra实现常数时间查找？

Question

在《图形数据库》(O'Reilly书籍)第六章中，该章节讲述了Neo4j的图形数据库存储方式：

为了理解本地图形处理为什么比基于重型索引的图形更加高效，请考虑以下问题。根据实现方式，索引查找在算法复杂度上可能是O(log n)，而直接查找相邻关系则是O(1)。对于遍历m步网络，索引方法的代价为O(m log n)，而使用无索引邻接表的实现则仅为O(m)。

因此Neo4j通过将所有节点和关系作为固定大小记录来实现常数时间查找:

使用固定大小的记录和指针式记录ID，遍历只需要在数据结构中跟踪指针即可，这可以非常高速地完成。要从一个节点到另一个节点遍历特定的关系，数据库执行几个廉价的ID计算（这些计算比在非图形本地数据库中伪造图形时必须执行的全局索引搜索要便宜得多）。

最后一句话引发了我的问题：Titan如何利用Cassandra或HBase作为存储后端实现这些性能提升或弥补它的不足呢?

- Lodewijk Bogaards

---

我会为OrientDB的同样问题投票！ - František Hartman

好问题，没错。OrientDB处理自己的存储，所以我猜他们有类似Neo4j的东西，但我很想知道。 - Lodewijk Bogaards

无论您是访问缓存对象还是磁盘上的对象，Neo4j在算法复杂度方面都是O(1)，因为它只是追踪指针而不是调用某些外部索引来遍历关系。Neubauer和Rodriguez（见上文）称之为“无索引邻接”，我认为这对所有合理的图形数据库都是至关重要的。 - Jim Webber

Answer 1

仅当数据在同一JVM中的内存时，Neo4j才能达到O（1）的性能。当数据在磁盘上时，由于在磁盘上跟踪指针（它们的磁盘表示方法很差），Neo4j变得较慢。

仅当数据在同一JVM中的内存中时，Titan才能达到O（1）的性能。当数据在磁盘上时，Titan比Neo4j更快，因为它有更好的磁盘表示方式。

请参见以下博客文章，以定量解释上述内容：http://thinkaurelius.com/2013/11/24/boutique-graph-data-with-titan/

因此，重要的是要理解人们说O（1）时，他们所处的内存层次结构的哪一部分。当您在单个JVM（单台计算机）中时，像Neo4j和Titan这样的缓存引擎可以轻松快速地工作。当无法将整个图形放入内存中时，必须依靠智能磁盘布局、分布式缓存等。

请参见以下两篇博客文章以获取更多信息：

http://thinkaurelius.com/2013/11/01/a-letter-regarding-native-graph-databases/ http://thinkaurelius.com/2013/07/22/scalable-graph-computing-der-gekrummte-graph/

- Marko A. Rodriguez

---

为了扩展，Neo4j并不支持在所有遍历中实现O(1)。假设存在一个边谓词。在Neo4j中获取顶点v的最近好友需要O(|out(v)|)的代价（即基于顶点的线性扫描）。为什么呢？因为Neo4j不会在内存中（也不会在磁盘上）对其数据进行排序。Neo4j必须迭代v的所有传出好友边缘以确定哪个边缘具有最新的时间戳。在Titan中，这（可以）是一个O(1)操作。你可以在这里了解更多信息：http://thinkaurelius.com/2012/10/25/a-solution-to-the-supernode-problem/ Titan在磁盘和内存中都实现了这项进展。 - Marko A. Rodriguez

我认为你错了。在Neo4j的最新版本（2.1.x）中，Neo4j还实现了所谓的“顶点中心索引”来解决这个问题。 - Rik Van Bruggen

Neo4j始终是算法O(1)，因为它是一个id * offset计算，可以产生一条记录。机械地说，与任何疲劳存储方法一样，有较短和较长的路径。如果命中缓存对象，则可以从数据库到磁盘再返回的路径被短路；如果命中冷缓存，则需要访问磁盘。这仍然是O(1)。没有索引或其他O(log n)或更差的搜索要执行。这是完全基于图形的栈的巨大优势。 - Jim Webber

@Marko 非常感谢您的回答。我仔细阅读了您所有的博客文章。我学到了很多，但是说实话，我仍然感到困惑。据我所知，Titan通过合并大量数据来大大减少缓存未命中的数量，但在存储级别上仍需要对数时间进行顶点查找。您说Neo4j比Titan慢，因为它采用非连续磁盘表示，但对于一个以遍历为主的图形数据库来说，这似乎是一个公平的权衡。显然，您不同意：为什么？是什么让您如此确定您不需要这种“本地”存储模型。 - Lodewijk Bogaards

@RikVanBruggen 我理解这仅适用于标签，而不适用于属性，对吗？ - Lodewijk Bogaards

虽然我还有点困惑，但我会接受这个答案，因为它确实增进了我的理解。再次感谢。 - Lodewijk Bogaards

Answer 2

OrientDB采用类似的方法管理关系，即使用直接指针（LINKS）而不是索引（无索引邻接），就像在磁盘上的内存指针一样。通过这种方式，OrientDB在内存和硬盘上实现了O(1)的遍历。

但是如果你有一个名为“City”的顶点，它与数千个“Person”顶点相连，并且你正在寻找所有年龄大于18岁的人，则OrientDB将使用索引，因为涉及到查询，所以在这种情况下复杂度是O(log N)。

- Lvca