int main() { return 0; }

Network_algo设计及优化杂记

Feb 19, 2016 by htfy96

问题来源

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

  • 图专用数据库（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.h和graphproto.pb.cc。

（protoc是protobuf-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.cc是graphproto.proto编译出来的东西
  • -lleveldb -lsnappy是LevelDb这个数据库的运行库，只有在使用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>这四组键值对来实现存储。

  • 利用Protobuf和cereal库，分别对Node和Edge（它们都由protoc编译生成）， set<EdgeIdT>进行高效的序列化及反序列化

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

  • 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边后可直接知道b的to()就是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. 把2，3得到的edgeId取交集，所得唯一结果就是e.id()