存储图数据的数据库 FlockDB

     <p>FlockDB是一个存储图数据的数据库，但是它并没有优化遍历图的操作。它优化的操作包括：超大规模<span>邻接矩阵查询，</span>快速读写和可分页查询。</p>    <ul>     <li>a high rate of add/update/remove operations</li>     <li>potientially complex set arithmetic queries</li>     <li>paging through query result sets containing millions of entries</li>     <li>ability to "archive" and later restore archived edges</li>     <li>horizontal scaling including replication</li>     <li>online data migration</li>    </ul>    <p></p>    <p>FlockDB将图存储为一个边的集合，每条边用两个代表顶点的64位整数表示。对于一个社会化网络图，这些顶点ID即用户ID，但是对于“收藏” 推文这 样的边，其目标顶点(destination id)则是一条推文的ID。每一条边都被一个64位的位置信息标识，用于排序。(推ter在“关注”类的边上用了时间戳标识，所以你的关注者列表时 按时间排序的，最新的在最前面。）<br /> <br /> 当一条边被“删除”，这条记录并没有从MySQL中真正删除，而是标记为“删除”状态，这会影响到主键值(一个由源ID-source id，状态-position，位置-position构成的组合键)。类似的，用户账户被删除时，他们所有的边都会改为存档(archive)状态，允 许之后被恢复(但是根据服务协议，我们只会保留一段时间)。我们只保留了一个组合主键和一个辅助索引来完成所有的查询。这种表结构优化使得MySQL大放 异彩，并提供给我们可预测的性能。</p>    <p>一条复杂的查询例如“我关注的人里面哪些关注了奥巴马总统”能分解成一些单用户查询(谁在关注奥巴马总统)，并很快响应。数据根据节点分块，所以这些查询能分别在各自的数据块，通过一个索引过的范围查询得到结果。类似的，遍历一个长结果集是用位置作为游标，而不是用<code>LIMIT/OFFSET</code>，所有页的数据均被索引，访问一样快。</p>    <p>基于进入系统的时间，写操作具有幂等性(不管操作多少次结果都不变的性质，比如取绝对值的函数就具有幂等性)和交换性(操作顺序不影响结果，比如加法就具 有交换性)。因为能交换操作顺序而不影响最终结果，所以我们才能在网络或者硬件临时故障的时候记录下所有操作或者恢复几分钟甚至几小时之前丢失的数据。这 种性质在初次部署是尤其有用。</p>    <p>可交换的写操作简化了新数据块的创建流程。一个新数据块能在即时处理写请求的同时，在后台慢慢从旧数据块导入数据。导入完成时，该数据块即处于“激活”状态，并准备处理读操作。</p>    <p>应用服务器(昵称flapps)用Scala编写，无状态，可水平伸缩。flapps与数据库独立，随着查询负载增加，我们可以增加更多的flapps。Flapps暴露了很少的thrift API给客户端，我们写的Ruby客户端包含更丰富的接口。<br /> <br /> <br /> 我们使用Gizzard库来处理数据分块层。该层将一段源ID映射到物理数据库，对于同一个物理地址的表，通过建立树来处理。写操作在本地登记后即返回，这样数据库崩溃或者出现性能问题能有效跟网站相应时间解耦。</p>    <p>图的每一条边都被存储了两次：一次正向存储(根据源ID做索引和分块)，一次反向存储(根据目的ID做索引和分块)。这样类似于“谁在关注我”这样的查询可以跟查询“我在关注谁”一样高效，并且所有结果数据都分布在同一块。</p>    <p>结果是我们拥有了一个可以按需扩展的一般服务器集群。在这个冬天，我们不知不觉已经增加了50%的数据库容量。现在我这个数据库里存储了<span style="font-weight:bold;">130亿</span>条边，峰值可承受负载达到每秒<span style="font-weight:bold;">2万次写</span>和<span style="font-weight:bold;">10万次读</span>。</p>    <p>介绍内容来自 http://article.yeeyan.org/view/yangxiao/136627<br /> <br /> </p>    <p><strong>项目主页：</strong><a href="http://www.open-open.com/lib/view/home/1322728059718" target="_blank">http://www.open-open.com/lib/view/home/1322728059718</a></p>