golang源码分析：cayley(6)

2023-08-09 15:07:19 浏览数 (2)

接着分析memstore中索引的具体实现，它的B 树不是自己实现的，而是引用了一个第三方包，首先我们看下gen.go，它里面其实是运行来Makefile命令

代码语言：javascript复制
package memstore
//go:generate make specify

Makefile文件中下载了实现了B 树的包https://github.com/cznic/b，然后通过正则对其中的interface替换成了int64.

代码语言：javascript复制
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文件里

代码语言：javascript复制
// 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中对索引定义如下：

代码语言：javascript复制
type QuadDirectionIndex struct {
  index [4]map[int64]*Tree
}

四元祖对应了4个b 树

代码语言：javascript复制
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),
  }}
}
代码语言：javascript复制
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
代码语言：javascript复制
    func (qdi QuadDirectionIndex) Get(d quad.Direction, id int64) (*Tree, bool) {
代码语言：javascript复制
type primitive struct {
  ID    int64
  Quad  internalQuad
  Value quad.Value
  refs  int
}
代码语言：javascript复制
type internalQuad struct {
  S, P, O, L int64
}
代码语言：javascript复制
func (q *internalQuad) SetDir(d quad.Direction, n int64) {
代码语言：javascript复制
func (q internalQuad) Dir(d quad.Direction) int64 {

具体quadstore定义如下：

代码语言：javascript复制
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
}
代码语言：javascript复制
func New(quads ...quad.Quad) *QuadStore {
  qs := newQuadStore()
  for _, q := range quads {
    qs.AddQuad(q)
代码语言：javascript复制
func newQuadStore() *QuadStore {
  return &QuadStore{
    vals:  make(map[string]int64),
    quads: make(map[internalQuad]int64),
    prim:  make(map[int64]*primitive),
    index: NewQuadDirectionIndex(),
代码语言：javascript复制
func (qs *QuadStore) addPrimitive(p *primitive) int64 {
  qs.last  
  id := qs.last
  p.ID = id
  p.refs = 1
  qs.appendPrimitive(p)
代码语言：javascript复制
func (qs *QuadStore) appendPrimitive(p *primitive) {
代码语言：javascript复制
const internalBNodePrefix = "memnode"
代码语言：javascript复制
func (qs *QuadStore) resolveVal(v quad.Value, add bool) (int64, bool) {
代码语言：javascript复制
func (qs *QuadStore) resolveQuad(q quad.Quad, add bool) (internalQuad, bool) {
代码语言：javascript复制
func (qs *QuadStore) lookupVal(id int64) quad.Value {
      return quad.BNode(internalBNodePrefix   strconv.FormatInt(id, 10))
代码语言：javascript复制
func (qs *QuadStore) lookupQuadDirs(p internalQuad) quad.Quad {
代码语言：javascript复制
func (qs *QuadStore) indexesForQuad(q internalQuad) []*Tree {
代码语言：javascript复制
func (qs *QuadStore) AddQuad(q quad.Quad) (int64, bool) {

writer定义了如何写入

代码语言：javascript复制
type quadWriter struct {
  qs *QuadStore
}
代码语言：javascript复制
func (qs *QuadStore) deleteQuadNodes(q internalQuad) {
  for dir := quad.Subject; dir <= quad.Label; dir   {

增量修改

代码语言：javascript复制
func (qs *QuadStore) ApplyDeltas(deltas []graph.Delta, ignoreOpts graph.IgnoreOpts) error {
代码语言：javascript复制
func (qs *QuadStore) quad(v graph.Ref) (q internalQuad, ok bool) {
  switch v := v.(type) {
  case bnode:
    p := qs.prim[int64(v)]
代码语言：javascript复制
func (qs *QuadStore) QuadIterator(d quad.Direction, value graph.Ref) graph.Iterator {
  id, ok := asID(value)
代码语言：javascript复制
func (qs *QuadStore) QuadIteratorSize(ctx context.Context, d quad.Direction, v graph.Ref) (graph.Size, error) {
  id, ok := asID(v)

类似mysql的分析器，也会统计四元祖的一些信息

代码语言：javascript复制
func (qs *QuadStore) Stats(ctx context.Context, exact bool) (graph.Stats, error) {
  return graph.Stats{
    Nodes: graph.Size{

iterator.go里定义了迭代器，是cayley图数据库的核心

代码语言：javascript复制
var _ graph.Iterator = &Iterator{}
代码语言：javascript复制
type Iterator struct {
  it *iterator2
  graph.Iterator
}
代码语言：javascript复制
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)
代码语言：javascript复制
var _ graph.IteratorShapeCompat = &iterator2{}
代码语言：javascript复制
type iterator2 struct {
  qs    *QuadStore
  tree  *Tree
  d     quad.Direction
  value int64
}
代码语言：javascript复制
func newIterator(tree *Tree, qs *QuadStore, d quad.Direction, value int64) *iterator2 {
代码语言：javascript复制
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接口，这个接口会加载满足条件的四元祖

代码语言：javascript复制
func (it *iterator2) Lookup() graph.Index {
  return newIteratorContains(it.tree, it.qs, it.d, it.value)
}
代码语言：javascript复制
func (it *iterator2) AsLegacy() graph.Iterator {
  it2 := &Iterator{it: it}
  it2.Iterator = graph.NewLegacy(it, it2)
代码语言：javascript复制
func (it *iterator2) Stats(ctx context.Context) (graph.IteratorCosts, error) {
  return graph.IteratorCosts{
代码语言：javascript复制
type iteratorNext struct {
  nodes bool
  qs    *QuadStore
  tree  *Tree
  d     quad.Direction


  iter *Enumerator
  cur  *primitive
  err  error
}
代码语言：javascript复制
func newIteratorNext(tree *Tree, qs *QuadStore, d quad.Direction) *iteratorNext {
  return &iteratorNext{

next会查找下一组节点：

代码语言：javascript复制
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()
代码语言：javascript复制
type iteratorContains struct {
  nodes bool
  qs    *QuadStore
  tree  *Tree


  cur *primitive


  d     quad.Direction
  value int64
}
代码语言：javascript复制
func newIteratorContains(tree *Tree, qs *QuadStore, d quad.Direction, value int64) *iteratorContains {
代码语言：javascript复制
func (it *iteratorContains) Contains(ctx context.Context, v graph.Ref) bool {

all_iterator.go

代码语言：javascript复制
var _ graph.IteratorFuture = (*AllIterator)(nil)
代码语言：javascript复制
type AllIterator struct {
  it *allIterator
  graph.Iterator
}
代码语言：javascript复制
func newAllIterator(qs *QuadStore, nodes bool, maxid int64) *AllIterator {
        it := &AllIterator{
    it: newAllIterator2(qs, nodes, maxid),
  }
      it.Iterator = graph.NewLegacy(it.it, it)
代码语言：javascript复制
func (it *AllIterator) AsShape() graph.IteratorShape {
代码语言：javascript复制
var _ graph.IteratorShape = (*allIterator)(nil)
代码语言：javascript复制
type allIterator struct {
  qs    *QuadStore
  all   []*primitive
  maxid int64 // id of last observed insert (prim id)
  nodes bool
}
代码语言：javascript复制
func newAllIterator2(qs *QuadStore, nodes bool, maxid int64) *allIterator {
代码语言：javascript复制
func (it *allIterator) Iterate() graph.Scanner {
      return newAllIteratorNext(it.qs, it.nodes, it.maxid, it.all)
代码语言：javascript复制
func (it *allIterator) Lookup() graph.Index {
代码语言：javascript复制
func (it *allIterator) AsLegacy() graph.Iterator {

还有子迭代器

代码语言：javascript复制
func (it *allIterator) SubIterators() []graph.IteratorShape { return nil }
代码语言：javascript复制
func (it *allIterator) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
代码语言：javascript复制
func (it *allIterator) String() string {
代码语言：javascript复制
func (it *allIterator) Stats(ctx context.Context) (graph.IteratorCosts, error) {
代码语言：javascript复制
func (p *primitive) filter(isNode bool, maxid int64) bool {
代码语言：javascript复制
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
}
代码语言：javascript复制
func newAllIteratorNext(qs *QuadStore, nodes bool, maxid int64, all []*primitive) *allIteratorNext {
代码语言：javascript复制
func (it *allIteratorNext) ok(p *primitive) bool {
  return p.filter(it.nodes, it.maxid)
代码语言：javascript复制
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
    }
  }
代码语言：javascript复制
func (it *allIteratorNext) Result() graph.Ref {
代码语言：javascript复制
type allIteratorContains struct {
  qs    *QuadStore
  maxid int64 // id of last observed insert (prim id)
  nodes bool


  cur  *primitive
  done bool
}
代码语言：javascript复制
func newAllIteratorContains(qs *QuadStore, nodes bool, maxid int64) *allIteratorContains {
代码语言：javascript复制
func (it *allIteratorContains) ok(p *primitive) bool {
代码语言：javascript复制
func (it *allIteratorContains) Contains(ctx context.Context, v graph.Ref) bool {
代码语言：javascript复制
func (it *allIteratorContains) Result() graph.Ref {
代码语言：javascript复制
func (it *allIteratorContains) NextPath(ctx context.Context) bool { return false }
func graph tree 接口 源码分析

0 人点赞