How Graph Databases Store Data on Disk

Question

I have seen these papers:

• TurboGraph
• GraphChi
• BiShard Parallel Processor
• G-Store
• NXgraph
• GridGraph

...and a few others. I am new to databases (other than having used them for web apps without understanding their internals), so I don't have much of a foundation on how to use the disk for storage.

I would like to know in general what these papers are doing for storing the graph on the file system. In taking a brief glance at them, they mention loading relevant subgraphs into memory from disk for efficient updates/querying. Some of them store the edges in one set of files (calling them "shards") and the vertices in another set of files (calling them "intervals"). Some have multiple different IDs, such as the "record ID (RID)" and "vertex ID" in TurboGraph (Figure 1 below).

However, I haven't yet seen a full overview of how all the pieces fit together. Wondering if one could explain that.

Specifically:

1. How the data might be structured into files for a graph database (at a high level).
2. What must happen when querying/updating in terms of loading stuff into memory at a high level.

It is unclear to me so far what needs to be loaded into memory, and what specifically the IDs are for. I'm not sure if each page (>= 1MB typically) is loaded into memory and parsed somehow, or scanned by line-by-line, or something similar (basically not sure how the file is parsed/scanned, and if it is parsed into some sort of in-memory data structure or if you can do the graph traversal stuff directly on the file bytes). And I'm not sure what the IDs are for. In RDBMSs the ID is sometimes an incremented integer per table without other meaning. In these papers it seems the ID has more to do with the position of a vertex in a page plus some sort of offsets and such. Also, some papers store a large single line (it seems) for a vertex with all its edges (an adjacency list), but I wonder about if you have thousands or millions of edges per vertex what to do. If one could point out the relevant features to look for then doing further research would help bring this into more clarity.

Thank you so much for your time, I hope that makes sense.

---

Figure 1.

Answer 1

I believe every implementation of a graph will vary on how they go about writing and reading from the disk.

On page 2, section 2.2 of Dgraph: Synchronously Replicated, Transactional and Distrubuted Graph Database by Manish Jain, Data Storage discussion is introduced with:

Dgraph data is stored in an embeddable key-value database called Badger for data input-output on disk. Badger is an LSM-tree based design, but differs from others in how it can optionally store values separately from keys to generate a much smaller LSM tree, which results in both lower write and read amplification.

---

You asked:

1. How the data might be structured into files for a graph database

The data is stored into posting lists by subject-predicate groups. Any node that contains a list of edges would store that list in a single posting list until it reaches a certain threshold in size and needs to be split across two or ore lists. This could be understood that any one to one relationship edge or predicate is saved in its own list and one-to-many relationship edge or predicates are grouped together and saves the linking uid or object value into a list. The main take away is that Badger stores values separate from keys to generate a smaller tree which increases read and write performance.

2. What must happen when querying/updating in terms of loading stuff into memory at a high level.

Manish just released a blog post about memory management and can explain that aspect better than myself.