IOGP: An Incremental Online Graph Partitioning for Large-Scale Distributed Graph Databases

摘要

Large-scale graphs databases are designed to serve continuous updates from the clients, and, at the same time, answer complex queries towards current graph in an on-line manner. This is different from another important set of tools, namely graph processing engines, which focus on performing complex analysis on graphs, like Pregel and GraphX. In fact, the boundary between graph databases and graph processing engines is a bit fuzzy. Most graph databases are capable of delivering graph computations through defining complex graph traversal, and, on the other hand, many graph computation engines also allow graphs to be updated and evolved like a database. In this study, we differentiate them according to the workloads they are optimized for. We consider graph databases are optimized for OLTP (online transaction processing) workloads like INSERT, UPDATE, GET, and TRVEL queries. Those operations should be performed in an interactive manner and expected to finish fast. On the other hand, graph processing engines are designed for OLAP (on-line analysis processing) workloads like running PageRank on the whole graph or finding the structure of social graph. Those differences lead to significantly different preferences in performance optimizations and also affect the choices of graph partitioning fundamentally.