建议将Edge的key中Rank和dstId互换位置

问答 讨论
1

目前EdgeKey的格式如下：

std::string NebulaKeyUtils::edgeKey(size_t vIdLen,
                                    PartitionID partId,
                                    const VertexID& srcId,
                                    EdgeType type,
                                    EdgeRanking rank,
                                    const VertexID& dstId,
                                    EdgeVerPlaceHolder ev) {
    CHECK_GE(vIdLen, srcId.size());
    CHECK_GE(vIdLen, dstId.size());
    int32_t item = (partId << kPartitionOffset) | static_cast<uint32_t>(NebulaKeyType::kEdge);

    std::string key;
    key.reserve(kEdgeLen + (vIdLen << 1));
    key.append(reinterpret_cast<const char*>(&item), sizeof(PartitionID))
       .append(srcId.data(), srcId.size())
       .append(vIdLen - srcId.size(), '\0')
       .append(reinterpret_cast<const char*>(&type), sizeof(EdgeType))
       .append(reinterpret_cast<const char*>(&rank), sizeof(EdgeRanking))
       .append(dstId.data(), dstId.size())
       .append(vIdLen - dstId.size(), '\0')
       .append(1, ev);
    return key;
}

我现在想做where edge._dst > “1000000” 的下推，如果将dstId放在Rank的前面，可以通过prefix直接seek到dstId == "1000000"对应的位置，往后iterator，不用遍历srcId对应的每条边，效率会高很多。

2

这里 edge key 的组成部分位置是有考量的，之所以是现在的这种排列方式，是考虑到大部分场景是知道起点和边向外拓展，而不关心边的终点，这种情况如果按照你的设计，那么就需要扫出所有同类型但 rank 不同的 key。

怎么排列 key 的布局没有最优，只能是考虑大部分场景的一个折中选择。

3

我们现在遇到的问题是比如有一个超级顶点，有1亿条边，现有的任何方式都没有办法将这1亿条边全部都iterator出来。我现在有一个想法是 循环调用go 语句，每次调用修改fromDst。这样就需要按照(edge_type, srcId, dstId) 最为起点。
go from “1” over follow where follow._dst > fromDst | limit 100000

而(edge_type, srcId，rank)作为起点的场景应该基本没有吧。

4

我理解，你是想通过 GO 语句来分批找出“大点”的所有邻居吗？第一轮先找 ID 属于 [0, 10W] 的邻居，第二轮找 ID 属于 [10W, 20W] 的邻居…以此类推？

目前如果只是针对边的 _dst 做过滤，是可以下推，就如你所言，是需要便利所有的边。

对 <srcid, edge_type, rank> 作为 prefix 的使用场景，GO 语句就是，每一步都是由起点+边向外找终点。

5

是的，其实还是有很多场景需要遍历超级顶点的所有边。按照我的思路就是希望可以[0, 10W] , [10w, 20w]… 这样每次取10w条边遍历，为了提高效率应该希望每次可以通过(follow._dst > fromDst)语句的filter seek到起始点。这样每次10W条边的获取都可以做到秒级。

而现在的问题是边的key是(srcid, edge_type, rank, dstid)。中间多了一个rank变量会导致我没有办法seek到起始点，而需要遍历所有的边，这样在获取[9990w, 1亿]这10W条边的时候必然会很慢。

6

不知都你用的 nebula 版本是哪个？

你如果是想通过改代码来优化的话，我们这边给的一个建议，你看可以参考看看是否可行：

  1. 你每次用 GO 迭代的时候，再加上 edge 的 rank 过滤，同时把这个过滤也下推到 storage 层
  2. 在 storage 层你可以做个优化就是如果碰到 dst 和 rank 都存在的过滤条件，可以修改 storage prefix 为 <src, edge_type, rank, dst> ，用此 key 去 seek，这样就不会再去 iterate 所有的边了。

另外提醒一点是：通过 limit 出来的结果你需要在应用层再用个“最大堆”等方式选出一个最大的 dst，因为返回的结果集是无序的。

7

现在在master上修改的，准备等2.0发布了再merge代码。

我已经在考虑自己将edge key修改一下了，就是这样做之后会与社区版本不兼容，比较为难。

8

是的，如果那样改的话，底层存储格式也会变化，会有兼容性问题

10

我看了下 [Encode rank to make key string in order. by guojun85 · Pull Request #351 · vesoft-inc/nebula-storage · GitHub] 这个改动，如果我没理解错，现在是准备把dst存到rank里？

其实这个超级大点是在上半年计划里的，只不过还没开始弄，我个人是倾向于通过分页机制。这个只需要每次storage返回下下次开始的起始点，然后调用rangeWithPrefix这个接口就行。只不过要改的比较多，但更通用点。

11

是的，之前我建议是rank和dstId互换位置，现在觉得只要rank变成有序的也是一样的，用 (srcid, edge_type, rank, dstid) 作为起始点，就可以直接用rangeWithPrefix seek到对应的位置，而不用iterator所有的数据。如果rank没有顺序，没法作为起始点。

12

能否在年前确定这个修改是否要做，我觉得必须要string有序才能做分页。key的格式肯定是要修改的，不然确实没法处理。

13

rank和dstId互换基本不可能。
几个问题：

  1. 用的是int id对吧？
  2. 如果只是要求做where edge._dst > “1000000”下推，好像改不改rank的大小端都可以做吧，还是说你目前数据里用到了rank这个字段？
14

是的，数据里面用到了rank字段，这个优化就没法实现了。

15

从这个角度考虑的话，我是支持大小端更改的，不过倾向于把rank当无符号整形用。

另外一个问题是 我看例子里举的是where edge._dst > “1000000”, 是用的默认长度小于8的string id还是int id？ 或者把rank放到value里不行吗？

16

dstid用的是 string。rank放到value里面是说不要用key里面的rank吗？我觉得既然提供了这个功能，就必须考虑用户用到了key里面的rank的情况。尽量做到通用不是吗？

17

嗯 按大端存是有好处 而且这是修改的最好机会了。如果在半个月改动key格式之前，是肯定不可能的。 不过我不能完全拍定方案，还需要讨论下。

基本就两个问题：

  1. 大小端
  2. 有无符号

另外我之前考虑过rank和dst互换的问题，主要也是因为key格式改动之后，去掉了版本号，这个需求反而不是很强烈了。

1 个赞
18

建议：

  1. 大端表示，使得string有序；
  2. 有符号，但是可以在graphd里面限制 rank > 0，这样改动会小很多。
19

基本确定改rank编码方式了。就按PR里的方式，大端，有符号。麻烦看下PR里的comments。

20

已经按照comment修改。

1 个赞