Network_algo设计及优化杂记


问题来源

  • 原有的数据库太大,无法全部放在内存中跑起来算法。

  • 图专用数据库(Neo4j)、RDBMS,提供的功能太全导致速度太慢,同时Client-Server模型通讯成本高昂,所以选择嵌入式数据库。

  • 引用图深度浅,数目多,所以选用Key-Value作为存储

  • 数据结构难以与算法分离

目标

通用的单机图论算法框架。

  • 通用性
  • 高性能

概述

使用步骤

安装

git clone --recursive https://github.com/htfy96/network_algo.git
sudo add-apt-repository ppa:ubuntu-toolchain-r/test -y
sudo apt-get -qq update
sudo apt-get install -y libmysqlclient-dev cmake libsqlite3-dev libleveldb-dev libprotobuf-dev protobuf-compiler libsnappy-dev
sudo apt-get install gcc-5 g++-5 -y //GCC 5+必需
export CXX="g++-5" CC="gcc-5" //编译时必需

cd network_algo
mkdir build && cd build
cmake ..
make -j2
sudo make install

定义图的节点、边

保存成graphproto.proto,然后protoc graphproto.proto --cpp_out=你自身代码所在的目录,会生成graphproto.pb.hgraphproto.pb.cc

protocprotobuf-compiler包内的程序)

写代码

编译:

g++-5 -std=c++11 your_prog.cpp graphproto.cc -lleveldb -lsnappy -lprotobuf -lnetalgo -o your_prog

  • 必须使用g++ 5.0及以上版本编译,否则会报错,可以用gcc -v来查看gcc的版本
  • graphproto.ccgraphproto.proto编译出来的东西
  • -lleveldb -lsnappyLevelDb这个数据库的运行库,只有在使用LeveldbGraph类的时候才会用到
  • -lprotobuf是为了支持graphproto.pb.h所需要的库,必需
  • -lnetalgo是这个算法库的东西

架构

构想是将整个库分成3层:

  • 算法层 通过graphsql向协议层发送消息,并通过协议层返回的迭代器来获取数据。与GraphType是什么没有任何关系。本层可以由用户自己写,库自身也会提供一些算法。

double calcSomething(GraphType& graph) { auto querySentence = “match (a)–(b)–(c) return a,c”_graphsql; //发送的消息,利用协议层提供的_graphsql后缀解析完成 auto start = graph.query(querySentence); //向graph发送查询请求,返回迭代器 for (auto it = start; it!=graph.end(); ++it) cout << it->getNode(“a”).id() << it->getNode(“c”).id() << endl; //通过迭代器来获取实际信息 }

  • 协议层 本层全部由库提供。 主要包括_graphsql这个后缀(将查询字符串转化为GraphSqlSentence)和各个Graph实现都要继承的GraphInterface基类,约束了各个实现所需要的接口(如set_node方法)。同时还给数据库层提供了一些协助函数(如compareProperty(data, propertyName, opCode, value))。
  • 数据库层 封装了一个图存储的数据结构,需要满足协议层GraphInterface基类的接口。 本库将提供LeveldbGraph这个结构,用户也可以参考其实现自己的数据结构。

具体实现

_graphsql

实现了一个字符串到GraphSqlSentence类的解释器。

  • const char* / const string缓存它们的parse结果。

auto sentence = “match (a)–(b) return a,b”_graphsql; //在这100000次循环中只有第一次会真正解析一遍这个字符串,其余时候都会缓存下来 auto mutableSentence = graphSqlParse(string(“match (a)–(b id="”) + string(1, ‘a’+(i%26)) +"") return a")); //这种情况每次都必须要解析一遍 }

### GraphInterface

图的接口。

<pre><code class="language-cpp">template&lt;typename NodeType, EdgeType&gt;

class GraphInterface { //… public: virtual ResultType query(const GraphSqlSentence&) = 0; virtual void setNode(const NodeType&) = 0; virtual void setEdge(const EdgeType&) = 0; virtual void setNodesBundle(const NodesBundle&) = 0; virtual void setEdgesBundle(const EdgesBundle&) = 0;

virtual void removeNode(const NodeIdType&) = 0;
virtual void removeEdge(const EdgeIdType&) = 0;

virtual void destroy() = 0;

};

LeveldbGraph

基于LevelDb的高性能图数据库。维护<NodeId:@outEdges => set<EdgeIdT>>, <NodeId:@inEdges => set<EdgeIdT>>, <NodeId:@nodeData => Node>, <EdgeId:@edgeData => Edge>这四组键值对来实现存储。

  • 利用Protobufcereal库,分别对NodeEdge(它们都由protoc编译生成), set<EdgeIdT>进行高效的序列化及反序列化

  • 实现了TypedLastUsedMap,并用其缓存inEdgesoutEdges,在大量密集读取的时候可以实现接近内存速度。

  • query的匹配算法:

    match (a)<-[b id="xxx"]-(c)-[e]->(d id="yyy") return a,b,c,d,e

    首先,b边和d点可以直接确定,以它们为中心把链切割成2段:

    1. (a)<-[b id="xxx"],已知b边后可直接知道bto()就是a点的id(),直接获取
    2. [b id="xxx"]-(c)-[e]->(d id="yyy"),此链两端点已知,双向匹配:
      1. b.from() == c.id()
      2. 获取d.inEdges(),得到d所有入边的EdgeId
      3. 获取c.outEdges(),得到c所有出边的EdgeId
      4. 23得到的edgeId取交集,所得唯一结果就是e.id()