巨大图结构

Question

我正在开发一个应用程序，需要在内存中表示一个庞大的图结构（1000000到6000000个节点和每个节点100或600条边）。边缘表示将包含关系的一些属性。

我尝试使用内存映射表示、数组、字典和字符串来表示这种内存结构，但由于内存限制，这些方法总是崩溃。

我想知道如何表示这个结构，或者类似的东西。顺便说一下，我正在使用Python。

- Harph

---

你说只有600个边-为什么不直接存储这些边？ - Cam

你的意思是每个节点100-600条边吗？ - tster

您需要使用数据库作为数据集，即使每个数据只有一个指针，也很庞大，更不用说作为Python对象了。您希望如何查询和遍历图形将决定您使用哪种类型的数据库。 - Nick Bastin

你的系统有多少内存？ - Brian Minton

Answer 1

1. 如果每个节点有100-600条边，那么您将需要处理36亿条边。
2. 为什么必须全部存储在内存中？
3. 您能展示一下您目前正在使用的数据结构吗？
4. 我们被允许使用多少内存（您所遇到的内存限制是什么）？

如果您需要将数据存储在内存中的唯一原因是因为需要快速读写它，请使用数据库。 数据库读写速度非常快，通常可以完全不用去磁盘进行读取。

- tster

---

+1：这不是一个答案，但在我们继续之前，所有这些问题都必须得到回答。 - Claudiu

好的...每个节点之间有100到600条边。我必须将其保存在内存（RAM）中，因为它必须不断地被访问。此外，它将不断更新，改变关系的权重，添加和删除节点和边。所有这些都必须具有良好的性能（响应时间）。 - Harph

我尝试了许多不同的数据结构来表示邻接矩阵，如字典、列表和对象组合。我还尝试将其映射到一个文件中，使用 xt4 分区，但当我需要随机写入时，它需要很长时间，并且会花费大量内存因为块写入。现在我正在我的自己的机器上进行测试，有 4 GB 的内存。当我实施它时，我将使用一台具有一定内存（我希望少于1 TB）的服务器。 - Harph

如果你担心的是读写性能，那么请使用数据库。 - tster

好的，你说的是哪种或者哪个数据库？ - Harph

Answer 2

根据您的硬件资源，使用全内存处理这么大的图形可能行不通。从图形特定的数据库角度来看，有两个可能的选择：

• Neo4j - 宣称可以轻松处理数十亿个节点，并且已经开发了很长时间。
• FlockDB - 这是Twitter最新发布的分布式图形数据库。

由于您正在使用Python，您是否看过Networkx？如果您感兴趣，加载这么大的图形时，您到底做了多少工作？

- Binary Nerd

---

谢谢你的回答...我已经尝试了networkx，但它不符合我的要求（使用了大量内存）。Neo4j太贵了。我会尝试使用flockDB。 - Harph

我已经了解了FlockDB...它看起来很酷，但是我在安装它时遇到了很多问题。我认为FlockDB还处于alpha版本。它没有良好的文档/支持。 - Harph

Neo4j确实有一个开源版本，可能会非常有用。https://neo4j.com/open-source-project/ - Brian Minton

Answer 3

我怀疑你需要大量的内存才能使用记忆结构：

假设你正在讨论每个节点有600个有向边，其中一个节点是4字节（整数键），而一个有向边仅是目标节点键（每个4字节）。

那么每个节点的原始数据是4 + 600 * 4 = 2404字节 x 6,000,000 = 超过14.4GB

这还没有包括任何其他开销或节点（或边缘）中的任何其他数据。

- Cade Roux

---

然而，拥有16GB或更多内存的系统相当普遍。我有一台二手的惠普服务器，只花了不到500美元就买到了16GB的内存。我在工作中使用的服务器有512GB或1TB的内存。我甚至在以前的工作中使用过多个TB的内存的服务器。例如，这是一台旧的戴尔服务器，支持高达6TB的内存：http://www.dell.com/en-us/work/shop/productdetails/poweredge-r920 - Brian Minton

@BrianMinton，这个观点现在和7年前一样有效。一旦你添加了分配系统来管理那么多的数据，将这样的结构存储在内存中仍然非常重要，而不是简单地将其持久化到适当的数据库结构中。 - Cade Roux

Answer 4

您的节点数量非常少，相对于节点数量而言边缘很少 - 这表明大多数节点并不是严格必要的。因此，为什么不使用稀疏结构，只有在使用时才插入节点？这应该很容易用字典实现；只需在使用边缘时再插入节点即可。

可以使用邻接表在节点上存储边缘。

当然，这仅适用于您确实指的是总共100-600个节点。如果您指的是每个节点，则完全是另一回事了。

- Michael Madsen

Answer 5

scipy.sparse.csgraph 包可能能够处理这个问题 -- 平均每个节点有100条边，500万个节点就有大约5亿对边，每对边占用8字节（两个整数ID），总共需要4GB内存。我认为 csgraph 使用了压缩技术，所以它所需的内存比这还要少；这可以在你的笔记本电脑上运行。

虽然 csgraph 没有 networkx 那么多的功能，但它使用的内存要少得多。

- amwinter

Answer 6

假设您的意思是每个节点600，您可以尝试这样做：

import os.path
import cPickle
class LazyGraph:
    def __init__(self,folder):
        self.folder = folder

    def get_node(self,id):
        f = open(os.path.join(self.folder,str(id)),'rb')
        node = cPickle.load(f)
        f.close() # just being paranoid
        return node

    def set_node(self,id,node):
        f = open(os.path.join(self.folder,str(id)),'wb')
        cPickle.dump(node,f,-1) # use highest protocol
        f.close() # just being paranoid

使用数组（或numpy数组）来保存实际的节点ID，因为它们更快。

请注意，这将非常非常慢。

您可以使用线程预取节点（假设您知道处理它们的顺序），但这不会很有趣。

- wisty

Answer 7

听起来你需要一个数据库和一个可以迭代结果的迭代器。这样你就不必一次性将所有内容都存储在内存中，但仍然可以随时访问它。

- exupero

---

他肯定需要一种不是内存的数据存储方式，但什么是“结果的迭代器”？图形算法通常不会满足于简单的迭代器。 - Nick Bastin

我可能是指“生成器”，例如(grape[stem] for grape in bunch)或使用yield的函数。 - exupero

Answer 8

如果你最终决定使用数据库，我建议看看neo4j和它的Python绑定。这是一个能够处理大型图形的图形数据库。这是今年PyCon的演示。

- miles82