golang 源碼分析：cayley-6-
接着分析 memstore 中索引的具體實現，它的 B + 樹不是自己實現的，而是引用了一個第三方包，首先我們看下 gen.go，它裏面其實是運行來 Makefile 命令
package memstore
//go:generate make specify
Makefile 文件中下載了實現了 B + 樹的包 https://github.com/cznic/b，然後通過正則對其中的 interface 替換成了 int64.
git clone https://github.com/cznic/b
cd b && git checkout $(pinned)
@sed -e 's|interface{}[^{]*/\*K\*/|int64|g' -e 's|interface{}[^{]*/\*V\*/|\*primitive|g' b/btree.go >keys.go把 b + 樹代碼複製到 keys.go 文件裏
// Keys and their associated values are interface{} typed, similar to all of
// the containers in the standard library.
$ make generic
//
// This command will write to stdout a version of the btree.go file where
// every key type occurrence is replaced by the word 'key' (written in all
// CAPS) and every value type occurrence is replaced by the word 'value'
// (written in all CAPS). Then you have to replace these tokens with your
// desired type(s), using any technique you're comfortable with.quadstore.go 中對索引定義如下：
type QuadDirectionIndex struct {
index [4]map[int64]*Tree
}四元祖對應了 4 個 b + 樹
func NewQuadDirectionIndex() QuadDirectionIndex {
return QuadDirectionIndex{[...]map[int64]*Tree{
quad.Subject - 1: make(map[int64]*Tree),
quad.Predicate - 1: make(map[int64]*Tree),
quad.Object - 1: make(map[int64]*Tree),
quad.Label - 1: make(map[int64]*Tree),
}}
}func (qdi QuadDirectionIndex) Tree(d quad.Direction, id int64) *Tree {
tree, ok := qdi.index[d-1][id]
if !ok {
tree = TreeNew(cmp)
qdi.index[d-1][id] = tree func (qdi QuadDirectionIndex) Get(d quad.Direction, id int64) (*Tree, bool) {type primitive struct {
ID int64
Quad internalQuad
Value quad.Value
refs int
}type internalQuad struct {
S, P, O, L int64
}func (q *internalQuad) SetDir(d quad.Direction, n int64) {func (q internalQuad) Dir(d quad.Direction) int64 {具體 quadstore 定義如下：
type QuadStore struct {
last int64
// TODO: string -> quad.Value once Raw -> typed resolution is unnecessary
vals map[string]int64
quads map[internalQuad]int64
prim map[int64]*primitive
all []*primitive // might not be sorted by id
reading bool // someone else might be reading "all" slice - next insert/delete should clone it
index QuadDirectionIndex
horizon int64 // used only to assign ids to tx
// vip_index map[string]map[int64]map[string]map[int64]*b.Tree
}func New(quads ...quad.Quad) *QuadStore {
qs := newQuadStore()
for _, q := range quads {
qs.AddQuad(q)func newQuadStore() *QuadStore {
return &QuadStore{
vals: make(map[string]int64),
quads: make(map[internalQuad]int64),
prim: make(map[int64]*primitive),
index: NewQuadDirectionIndex(),func (qs *QuadStore) addPrimitive(p *primitive) int64 {
qs.last++
id := qs.last
p.ID = id
p.refs = 1
qs.appendPrimitive(p)func (qs *QuadStore) appendPrimitive(p *primitive) {const internalBNodePrefix = "memnode"func (qs *QuadStore) resolveVal(v quad.Value, add bool) (int64, bool) {func (qs *QuadStore) resolveQuad(q quad.Quad, add bool) (internalQuad, bool) {func (qs *QuadStore) lookupVal(id int64) quad.Value {
return quad.BNode(internalBNodePrefix + strconv.FormatInt(id, 10))func (qs *QuadStore) lookupQuadDirs(p internalQuad) quad.Quad {func (qs *QuadStore) indexesForQuad(q internalQuad) []*Tree {func (qs *QuadStore) AddQuad(q quad.Quad) (int64, bool) {writer 定義瞭如何寫入
type quadWriter struct {
qs *QuadStore
}func (qs *QuadStore) deleteQuadNodes(q internalQuad) {
for dir := quad.Subject; dir <= quad.Label; dir++ {增量修改
func (qs *QuadStore) ApplyDeltas(deltas []graph.Delta, ignoreOpts graph.IgnoreOpts) error {func (qs *QuadStore) quad(v graph.Ref) (q internalQuad, ok bool) {
switch v := v.(type) {
case bnode:
p := qs.prim[int64(v)]func (qs *QuadStore) QuadIterator(d quad.Direction, value graph.Ref) graph.Iterator {
id, ok := asID(value)func (qs *QuadStore) QuadIteratorSize(ctx context.Context, d quad.Direction, v graph.Ref) (graph.Size, error) {
id, ok := asID(v)類似 mysql 的分析器，也會統計四元祖的一些信息
func (qs *QuadStore) Stats(ctx context.Context, exact bool) (graph.Stats, error) {
return graph.Stats{
Nodes: graph.Size{iterator.go 裏定義了迭代器，是 cayley 圖數據庫的核心
var _ graph.Iterator = &Iterator{}type Iterator struct {
it *iterator2
graph.Iterator
}func NewIterator(tree *Tree, qs *QuadStore, d quad.Direction, value int64) *Iterator {
it := &Iterator{
it: newIterator(tree, qs, d, value),
}
it.Iterator = graph.NewLegacy(it.it, it)var _ graph.IteratorShapeCompat = &iterator2{}type iterator2 struct {
qs *QuadStore
tree *Tree
d quad.Direction
value int64
}func newIterator(tree *Tree, qs *QuadStore, d quad.Direction, value int64) *iterator2 {func (it *iterator2) Iterate() graph.Scanner {
// TODO(dennwc): it doesn't check the direction and value, while Contains does; is it expected?
return newIteratorNext(it.tree, it.qs, it.d)
}LookUp 函數里面會調用 contains 接口，這個接口會加載滿足條件的四元祖
func (it *iterator2) Lookup() graph.Index {
return newIteratorContains(it.tree, it.qs, it.d, it.value)
}func (it *iterator2) AsLegacy() graph.Iterator {
it2 := &Iterator{it: it}
it2.Iterator = graph.NewLegacy(it, it2)func (it *iterator2) Stats(ctx context.Context) (graph.IteratorCosts, error) {
return graph.IteratorCosts{type iteratorNext struct {
nodes bool
qs *QuadStore
tree *Tree
d quad.Direction
iter *Enumerator
cur *primitive
err error
}func newIteratorNext(tree *Tree, qs *QuadStore, d quad.Direction) *iteratorNext {
return &iteratorNext{next 會查找下一組節點：
func (it *iteratorNext) Next(ctx context.Context) bool {
if it.iter == nil {
it.iter, it.err = it.tree.SeekFirst()
for {
_, p, err := it.iter.Next()type iteratorContains struct {
nodes bool
qs *QuadStore
tree *Tree
cur *primitive
d quad.Direction
value int64
}func newIteratorContains(tree *Tree, qs *QuadStore, d quad.Direction, value int64) *iteratorContains {func (it *iteratorContains) Contains(ctx context.Context, v graph.Ref) bool {all_iterator.go
var _ graph.IteratorFuture = (*AllIterator)(nil)type AllIterator struct {
it *allIterator
graph.Iterator
}func newAllIterator(qs *QuadStore, nodes bool, maxid int64) *AllIterator {
it := &AllIterator{
it: newAllIterator2(qs, nodes, maxid),
}
it.Iterator = graph.NewLegacy(it.it, it)func (it *AllIterator) AsShape() graph.IteratorShape {var _ graph.IteratorShape = (*allIterator)(nil)type allIterator struct {
qs *QuadStore
all []*primitive
maxid int64 // id of last observed insert (prim id)
nodes bool
}func newAllIterator2(qs *QuadStore, nodes bool, maxid int64) *allIterator {func (it *allIterator) Iterate() graph.Scanner {
return newAllIteratorNext(it.qs, it.nodes, it.maxid, it.all)func (it *allIterator) Lookup() graph.Index {func (it *allIterator) AsLegacy() graph.Iterator {還有子迭代器
func (it *allIterator) SubIterators() []graph.IteratorShape { return nil }func (it *allIterator) Optimize(ctx context.Context) (graph.IteratorShape, bool) {func (it *allIterator) String() string {func (it *allIterator) Stats(ctx context.Context) (graph.IteratorCosts, error) {func (p *primitive) filter(isNode bool, maxid int64) bool {type allIteratorNext struct {
qs *QuadStore
all []*primitive
maxid int64 // id of last observed insert (prim id)
nodes bool
i int // index into qs.all
cur *primitive
done bool
}func newAllIteratorNext(qs *QuadStore, nodes bool, maxid int64, all []*primitive) *allIteratorNext {func (it *allIteratorNext) ok(p *primitive) bool {
return p.filter(it.nodes, it.maxid)func (it *allIteratorNext) Next(ctx context.Context) bool {
for ; it.i < len(all); it.i++ {
p := all[it.i]
if p.ID > it.maxid {
break
}
if it.ok(p) {
it.cur = p
return true
}
}func (it *allIteratorNext) Result() graph.Ref {type allIteratorContains struct {
qs *QuadStore
maxid int64 // id of last observed insert (prim id)
nodes bool
cur *primitive
done bool
}func newAllIteratorContains(qs *QuadStore, nodes bool, maxid int64) *allIteratorContains {func (it *allIteratorContains) ok(p *primitive) bool {func (it *allIteratorContains) Contains(ctx context.Context, v graph.Ref) bool {func (it *allIteratorContains) Result() graph.Ref {func (it *allIteratorContains) NextPath(ctx context.Context) bool { return false }本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/pqi-YMR83WA9MndI9wClow