Correctly Implement `PickRandomVertex` Efficiently
- 主要語言
- Go
- 星號
- 3
- 分支
- 2
- PR 合併指標
- 30 天內沒有已合併 PR
描述
The current implementation of `PickRandomVertex` is not really correct. It only picks the "random" vertex from the first 100 keys of the `*badger.Iterator` which according to the badger documentation:
> Iteration happens in byte-wise lexicographical sorting order.
So its not really random.
What we ideally want is to pick a random vertex from all the vertices present in the graph. However, for this implementation, I am okay if the random vertex is picked only from all the source vertices ie all the keys in the badgerdb. Iterating over all the keys in badger using `*badger.Iterator` is very inefficient for large graphs. The [Stream](https://dgraph.io/docs/badger/get-started/#stream) framework of badger allows concurrent traversal of the whole graph. An Incorrect implementation using the stream framework is implemented in `PickRandomVertexIncorrectEfficient()`
Your task is to come up with a correct implementation of PickRandomVertex. You are not restricted to use the Stream framework but I haven't found any other ways to do it. If you do, knock yourself out.
Ref: https://github.com/dgraph-io/badger/issues/1120
**Note**: Please comment here/DM me on discord the proposed design before implementing it
貢獻指南
研究方向
Start with PickRandomVertex and compare it with PickRandomVertexIncorrectEfficient. Read Badger's Iterator and Stream documentation, then propose the design requested in the issue before implementing it. Done means selecting a vertex uniformly from the source keys without limiting selection to the first 100 lexicographically ordered keys and without an inefficient full traversal.
由索引模型根據 Issue 內容生成。
評估
- 技術堆疊
- go
- 領域
- databases
- Issue 類型
- 缺陷
- 難度
- 5/5
- 預估耗時
- 一週以上
- 活躍度
- 停滯
- 描述清晰度
- 基本清楚
- 新手友好度
- 25/100