lemongraph, 基于日志的事务性图形引擎

分享于 

14分钟阅读

GitHub

  繁體 雙語
Log-based transactional graph engine
  • 源代码名称:lemongraph
  • 源代码网址:http://www.github.com/NationalSecurityAgency/lemongraph
  • lemongraph源代码文档
  • lemongraph源代码下载
  • Git URL:
    git://www.github.com/NationalSecurityAgency/lemongraph.git
    Git Clone代码到本地:
    git clone http://www.github.com/NationalSecurityAgency/lemongraph
    Subversion代码到本地:
    $ svn co --depth empty http://www.github.com/NationalSecurityAgency/lemongraph
    Checked out revision 1.
    $ cd repo
    $ svn up trunk
    
    LemonGraph

    LemonGraph是一个基于日志的事务图形 (nodes/edges/properties) 数据库引擎,它由单个文件支持。 主要的用例是支持流式种子集扩展。 图形库的核心是用C 编写的,而 python ( 2.x ) 层添加了友好绑定插件。一个查询语言插件和一个REST服务插件(。 LemonGraph在( 而且继承了很多) Symas LMDB上运行- 一个事务性密钥/值存储,它开发了一个用于代替BerkeleyDB的。

    基准测试

    在物理硬件( 3ghz X5670,大量内存) 上使用 PyPy 4.0,在单个事务下:

    秒存储( mb ) 速度( 每秒) 运算( 秒)
    4.596222k节点插入 1百万节点
    11204153k属性上面,在每个 node 上设置一个属性
    410185625k边缘上面加上 10的随机边缘
    特性

    Symas LMDB提供事务。多进程MVCC能力(。单个编写器,多个非阻塞读取器)。嵌套写事务和快速非阻塞二进制快照。 我们还将继承一些警告:

    • max数据库mapSize必须手动维护,但在 64位 平台上,它的计算代价很低
    • 事务只能从创建它们的线程中使用
    • 数据库文件在进程中只能打开一次
    • 另请参阅

    顶部的图形库支持:

    • 节点- 按类型和值在图形中显示 uniqued
    • 定向边- uniqued按源 node,目标 node,类型和值
    • 附加到图形。节点。边或者属性的属性键/值对- uniqued按键和父对象
    • 删除 nodes/edges/properties
    • 历史视图- 在日志位置X 检查图
    • 自动mapSize增长,只要txn的单个更新保持在 1 gb以下
    python

    python 包装提供友好的界面:

    • 事务是使用 with 块管理
    • graph/node/edge 属性以及域键/值对可以使用标准的python 字典样式操作进行操作
    • 自定义序列化程序对象可以用于简化复杂数据结构( 例如。 json或者 msgpack )
    • 可以使用自定义图查询语言执行即席或者流式查询。
    安装

    python-设置

    注意,REST服务不能运行在 CentOS python 上,因为我们依靠新的memoryview 魔术。

    • CPython上的CentOS 6/7:
      • yum install -y gcc gcc-c++ make libffi-devel zlib-devel python-devel python-setuptools
      • easy_install 'cffi>=1.0'
    • CPython在 Ubuntu 15.04上- 16.04:
      • apt-get install libffi-dev zlib1g-dev python-dev python-cffi
    • CPython ( 已经编译) - 只需 Bootstrap setuptools并安装 cffi:
      • curl https://bootstrap.pypa.io/ez_setup.py | python -
      • easy_install 'cffi>=1.0'
    • Pypy - 只是 Bootstrap setuptools - cffi被捆绑:
      • curl https://bootstrap.pypa.io/ez_setup.py | pypy -

    LemonGraph安装

    • python setup.py install ( 或者你知道,pypy )

    或者在没有正确安装的情况下运行,你必须手动安装依赖项:

      • easy_install lazy pysigset msgpack-python python-dateutil ujson
    • Pypy:
      • easy_install lazy pysigset msgpack-python python-dateutil
    python-示例
    import LemonGraphimport osimport sysimport tempfile
    fd, path = tempfile.mkstemp()
    os.close(fd)# open graph objectg = LemonGraph.Graph(path)# enter a write transactionwith g.transaction(write=True) as txn:
     # create a couple of nodes node1 = txn.node(type='foo', value='bar')
     node2 = txn.node(type='foo', value='baz')
     # create an edge between them edge1 = txn.edge(src=node1, tgt=node2, type='foo', value='foobar')
     # set some properties node1['prop1'] ='propval1' node2['prop2'] ='propval2' node2['prop3'] ='propval3' edge1['prop4'] ='propval4'# set a graph property txn['thing1'] ='thing2'# print out nodes and edgesfor n in txn.nodes():
     print n
     for e in txn.edges():
     print e
     b4_delete = txn.lastID
     # delete a propertydel node1['prop1']
     # delete a node - cascades to edges and properties node2.delete()
     printwith g.transaction(write=False) as txn:
     # run an ad-hoc query before deleteprint"ad-hoc query: nodes before deletions"for chain in txn.query('n()', stop=b4_delete):
     print chain
     print# run an ad-hoc queryprint"ad-hoc query: nodes after deletions"for chain in txn.query('n()'):
     print chain
     print# run streaming queriesprint"streaming query: nodes/edges"for q, chain in txn.mquery(['n(prop3)','e()','n()->n()'], start=1):
     print q, "=>", chain
     print# dump the internal graph log to stdoutprint"dump:" txn.dump()# delete graph artifacts from diskg.delete()
    命令行工具

    交互式查询( 潜在活动) 图形:

    • python -mLemonGraph.dbtool path/to/foo.db

    快照一个( 潜在活动) 数据库:

    • python -mLemonGraph.snapshot path/to/foo.db> copy.db
    REST服务

    运行REST服务( 使用 -h 列出选项):

    • python -mLemonGraph.server <options>

    rest服务维护基本图信息的索引缓存。 每毫秒,它将检查并刷新更新的图形到磁盘。

    为了提高吞吐量,使用 -s,以牺牲 OS/hardware/power-related 失败时可能发生的数据丢失。

    默认情况下,它将运行:

    • 一个负责 [re] 生成和杀死子线程的主进程
    • 一个同步进程,负责同步图表到磁盘
    • N ( -w ) 工作进程处理http请求
    查询语言

    这里查询语言旨在查询图形中任意长的node-edge-node链,并支持两种查询样式:

    • 针对完整图的特殊模式
    • 通过在一系列图日志位置上同时计算流模式中的一个或者多个模式,只返回新匹配的模式

    注意,在流模式中,节点和边一旦匹配所需的过滤器就会被捕获。 以后添加的任何附加属性将不会出现在结果中。

    查询 Pattern 必须至少指定一个 node 或者边,但许多may链接在一起:

    • n()-e()-n()

    结果返回为所请求节点和/或者边的链( 列表)。

    可以添加箭头头执行定向查询,并且可以推断节点或者边。 结果集中不包含推断的组件。 手动忽略非推断的零部件,请在 node 或者边缘标记中添加'at'符号。 这两个查询是相同的:

    • n()->n()
    • n()->@e()->n()

    默认情况下,节点和边在返回的链中必须是唯一的。 若要取消在查询 Pattern 中给定的slot,请双击 node/edge标记:

    • n()->N()->n()

    要筛选( 并可能加速) 查询,可以在查询中的节点和边的括号内提供属性筛选器列表:

    • n(type="foo")

    属性筛选器必须至少指定一个键,还必须指定具有值 [s]的运算符。

    简单键( 完全由'字'字符,不能以字母/数字开头) 可以被指定为 barewords,否则被引用。 对象的嵌套关键点被支持- 用未加引号的点分隔关键零部件。

    运算符:

    Bare:

    • 没有运算符或者值,并简单地测试键存在

    比较运算符:

    • 将标准 <><=>= 和翻译直接转换为 python

    所有剩余操作符:

    • 可以通过将''预置为运算符来求反 !
    • 可以匹配一个值或者由方括号括起来的值列表

    相等( = ),值可以是:

    • 数字- 浮点,整数,十六进制,八进制
    • 字符串- 用引号括起来
    • 布尔- 不区分大小写的bareword'true'或者 false'
    • 空- 区分大小写的bareword'无'或者'"'

    正则表达式( ~ ) ( 以perl样式表示法表示的python 风格):

    • 使用 python 模块的re 进行评估
    • 以Perl格式格式化,因此我们可以轻松添加标记: /pattern/flags
    • 标志可以是以下任意组合:
      • i - 大小写不敏感
      • m - 多行
      • s - 点匹配换行符
      • x - 详细

    值类型( : ):

    • boolean - true/false
    • number - 任意数字类型
    • array - 列表
    • object/哈希

    示例查询:

    • n() - 选择所有节点
    • e() - 选择所有边
    • n()-e()-n() - 选择所有 node/edge/node 链
    • n()-n() - 选择带/出边缘的node-to-node链
    • n()->n()<-n() - 定向查询
    • n(type="foo")
    • e(lon:[string,number], lat:[string,number])
    • n(depth<=1, value~/unicorn/i)

    别名和附加过滤器:

    一个或者多个附加筛选器可以附加到查询 Pattern。 每个过滤器的内容都可以与目标 node [s]/edge [s] 有效地合并。

    索引是基于以下内容的:

    • n(type="foo")-n(), 1(value!="bar"), 2(blah)

    支持Bareword别名- 别名可以引用一个或者多个节点,也可以通过别名附加其他过滤器:

    • n:blah()-n:blah(), blah(edge_count<5)

    在内部,别名是折叠的,但是如果查询中的别名或者它的他筛选器包含大写字符。

    很好

    • n:blah() ( 忽略别名)
    • n(), blah() ( 忽略过滤器)
    • n:blah(), blah() ( 过滤器被应用到别名 node )
    • n:blah(), blah() ( 过滤器被应用到别名 node )

    错误:

    • n:blah() ( 缺少过滤器)
    • n(), blah() ( 缺少别名)
    实现细节

    LMDB是一个MVCC事务键/值存储( n。btree ),它支持子表的概念。 我们使用几个表格来完成我们的目标:

    这些文件一起提供了用于字节序列的磁盘哈希表- 这些表中的记录永远不会被删除或者更新:

    • 小数点 scalar - 将递增数字标识映射到字节序列
    • scalar_idx - 将 crc32(byte_sequence) 映射到的标量 id

    实际图形数据存储在日志中- 不会删除记录,但是在删除或者属性值更新时更新数字字段:

    • 日志 - 将递增数字logID映射到图形更新事件: 新建 node,边或者属性,或者删除。 使用上面的哈希表将 Types/keys/values 转换为数字 id。

    跟踪写入日志的写入事务的统计信息:

    • txnlog - 映射递增txnID和日志偏移/范围至总 node/边缘计数

    为了提供快速操作,图数据被索引为( 我们保留了增加更多权利的权利。) - 记录从不删除或者更新的几种方式:

    • node_idx - 存储 typeID/valueID/logID 元组
    • edge_idx - 存储 typeID/valueID/srcID/tgtID/logID 元组
    • prop_idx - 存储 parentID/keyID/logID 元组
    • srcnode_idx - 存储 nodeID/typeID/edgeID 元组- 引用的node 是指定类型的引用边的源
    • tgtnode_idx - 存储 nodeID/typeID/edgeID 元组- 引用的node 是指定类型的引用边缘的目标

    我们还提供了一个非日志/键=> 值存储接口。 域是使用上述存储的映射到IDs的映射,键和值也可以是。 映射键和/或者值会导致总体存储较少,但是任何映射的映射都不会真正消失。 对于非映射键,最大键长度限制为 500字节。 与其他表不同,可以对该表执行删除操作:

    • 可选的kv映射域 & optionally映射的关键元组映射为可以选择的id映射值

    BASE  log  transaction  交易  
    相关文章