golang源码分析：cayley(6)

golang算法架构leetcode技术php 2023-06-06

532

接着分析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 }

源码

文章转载自golang算法架构leetcode技术php，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

golang源码分析：cayley(6)

评论