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

目前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对应的每条边,效率会高很多。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

基本就两个问题:

  1. 大小端
  2. 有无符号

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

1 个赞

建议:

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

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

已经按照comment修改。

1 个赞

浙ICP备20010487号