下面我们分析下不同存储后端是如何注册的，最后具体分析下，内存存储的具体实现方式。
获取内部存储注册完成后的实例函数定义如下graph/registry.go
代码语言：javascript复制func NewQuadStore(name string, dbpath string, opts Options) (QuadStore, error) {
r, registered := storeRegistry[name]
return r.NewFunc(dbpath, opts)实例是存储在全局变量里
代码语言：javascript复制var storeRegistry = make(map[string]QuadStoreRegistration)type QuadStoreRegistration struct {
NewFunc NewStoreFunc
UpgradeFunc UpgradeStoreFunc
InitFunc InitStoreFunc
IsPersistent bool
}type NewStoreFunc func(string, Options) (QuadStore, error)
type InitStoreFunc func(string, Options) error
type UpgradeStoreFunc func(string, Options) errorfunc RegisterQuadStore(name string, register QuadStoreRegistration) {
if _, found := storeRegistry[name]; found {
panic(fmt.Sprintf("Already registered QuadStore %q.", name))
}
storeRegistry[name] = registergraph/gaedatastore/quadstore.go每一种存储在init函数里完成了注册。
代码语言：javascript复制func init() {
graph.RegisterQuadStore("gaedatastore", graph.QuadStoreRegistration{
NewFunc: newQuadStore,
UpgradeFunc: nil,
InitFunc: initQuadStore,
IsPersistent: true,
})
}func newQuadStore(_ string, options graph.Options) (graph.QuadStore, error) {
return &QuadStore{}, nil
}func initQuadStore(_ string, _ graph.Options) error {
// TODO (panamafrancis) check appengine datastore for consistency
return nil
}type QuadStore struct {
context context.Context
}类似的，基于kv的存储graph/kv/quadstore.go
代码语言：javascript复制func Register(name string, r Registration) {
graph.RegisterQuadStore(name, graph.QuadStoreRegistration{
InitFunc: func(addr string, opt graph.Options) error {
kv, err := r.InitFunc(addr, opt)
if err = Init(kv, opt); err != nil {
NewFunc: func(addr string, opt graph.Options) (graph.QuadStore, error) {
kv, err := r.NewFunc(addr, opt)
if err = Init(kv, opt); err != nil {
return New(kv, opt)基于内存的存储graph/memstore/quadstore.go
代码语言：javascript复制func init() {
graph.RegisterQuadStore(QuadStoreType, graph.QuadStoreRegistration{
NewFunc: func(string, graph.Options) (graph.QuadStore, error) {
return newQuadStore(), nil
},const QuadStoreType = "memstore"func newQuadStore() *QuadStore {
return &QuadStore{
vals: make(map[string]int64),
quads: make(map[internalQuad]int64),
prim: make(map[int64]*primitive),
index: NewQuadDirectionIndex(),
}
}nosql的注册graph/nosql/quadstore.go
代码语言：javascript复制func Register(name string, r Registration) {
graph.RegisterQuadStore(name, graph.QuadStoreRegistration{
InitFunc: func(addr string, opt graph.Options) error {sql的注册graph/sql/quadstore.go
代码语言：javascript复制func registerQuadStore(name, typ string) {
graph.RegisterQuadStore(name, graph.QuadStoreRegistration{
NewFunc: func(addr string, options graph.Options) (graph.QuadStore, error) {
return New(typ, addr, options)QuadStore 的定义如下graph/quadstore.go
代码语言：javascript复制type QuadStore interface {
Namer
QuadIndexer
// The only way in is through building a transaction, which
// is done by a replication strategy.
ApplyDeltas(in []Delta, opts IgnoreOpts) error
// NewQuadWriter starts a batch quad import process.
// The order of changes is not guaranteed, neither is the order and result of concurrent ApplyDeltas.
NewQuadWriter() (quad.WriteCloser, error)
// Returns an iterator enumerating all nodes in the graph.
NodesAllIterator() Iterator
// Returns an iterator enumerating all links in the graph.
QuadsAllIterator() Iterator
// Stats returns the number of nodes and quads currently stored.
// Exact flag controls the correctness of the value. It can be an estimation, or a precise calculation.
// The quadstore may have a fast way of retrieving the precise stats, in this case it may ignore 'exact'
// flag and always return correct stats (with an appropriate flags set in the output).
Stats(ctx context.Context, exact bool) (Stats, error)
// Close the quad store and clean up. (Flush to disk, cleanly
// sever connections, etc)
Close() error
}其中有两个重要属性
代码语言：javascript复制type Namer interface {
// Given a node ID, return the opaque token used by the QuadStore
// to represent that id.
ValueOf(quad.Value) Ref
// Given an opaque token, return the node that it represents.
NameOf(Ref) quad.Value
}type QuadIndexer interface {
// Given an opaque token, returns the quad for that token from the store.
Quad(Ref) quad.Quad
// Given a direction and a token, creates an iterator of links which have
// that node token in that directional field.
QuadIterator(quad.Direction, Ref) Iterator
// QuadIteratorSize returns an estimated size of an iterator.
QuadIteratorSize(ctx context.Context, d quad.Direction, v Ref) (Size, error)
// Convenience function for speed. Given a quad token and a direction
// return the node token for that direction. Sometimes, a QuadStore
// can do this without going all the way to the backing store, and
// gives the QuadStore the opportunity to make this optimization.
//
// Iterators will call this. At worst, a valid implementation is
//
// qs.ValueOf(qs.Quad(id).Get(dir))
//
QuadDirection(id Ref, d quad.Direction) Ref
}分析完上述结果后，我们来分析下内存存储是如何实现的。内部是通过一个b 树来存储的，四元祖简化为4个int64的值
代码语言：javascript复制type internalQuad struct {
S, P, O, L int64
}type primitive struct {
ID int64
Quad internalQuad
Value quad.Value
refs int
}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),
}}
}所以定义在，值是个b 树
代码语言：javascript复制type QuadDirectionIndex struct {
index [4]map[int64]*Tree
}增加四元祖
代码语言：javascript复制func (qs *QuadStore) AddQuad(q quad.Quad) (int64, bool) {
p, _ := qs.resolveQuad(q, false)
if id := qs.quads[p]; id != 0 {
return id, false
p, _ = qs.resolveQuad(q, true)
pr := &primitive{Quad: p}
id := qs.addPrimitive(pr)
qs.quads[p] = id
for _, t := range qs.indexesForQuad(p) {
t.Set(id, pr)
}func (qs *QuadStore) resolveQuad(q quad.Quad, add bool) (internalQuad, bool) {
for dir := quad.Subject; dir <= quad.Label; dir {
v := q.Get(dir)
if vid, _ := qs.resolveVal(v, add); vid != 0 {
p.SetDir(dir, vid)
} else if !add {
return internalQuad{}, false
}func (qs *QuadStore) resolveVal(v quad.Value, add bool) (int64, bool) {
if n, ok := v.(quad.BNode); ok && strings.HasPrefix(string(n), internalBNodePrefix) {
if p, ok := qs.prim[id]; ok || !add {
if add {
p.refs
}
return id, ok
qs.appendPrimitive(&primitive{ID: id, refs: 1})type primitive struct {
ID int64
Quad internalQuad
Value quad.Value
refs int
}func (qs *QuadStore) appendPrimitive(p *primitive) {
qs.prim[p.ID] = p
if !qs.reading {
qs.all = append(qs.all, p)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
}type QuadDirectionIndex struct {
index [4]map[int64]*Tree
}func (qs *QuadStore) indexesForQuad(q internalQuad) []*Tree {
trees := make([]*Tree, 0, 4)
for dir := quad.Subject; dir <= quad.Label; dir {
v := q.Dir(dir)
if v == 0 {
continue
}
trees = append(trees, qs.index.Tree(dir, v))func (qdi QuadDirectionIndex) Tree(d quad.Direction, id int64) *Tree {
tree, ok := qdi.index[d-1][id]quad.go
代码语言：javascript复制// Our quad struct, used throughout.
type Quad struct {
Subject Value `json:"subject"`
Predicate Value `json:"predicate"`
Object Value `json:"object"`
Label Value `json:"label,omitempty"`
}// List of the valid directions of a quad.
const (
Any Direction = iota
Subject
Predicate
Object
Label
)// Per-field accessor for quads.
func (q Quad) Get(d Direction) Value {
switch d {
case Subject:
return q.Subject
case Predicate:
return q.Predicate
case Label:
return q.Label
case Object:
return q.Object
default:
panic(d.String())
}
}value.go
代码语言：javascript复制type String stringgraph/memstore/keys.go
代码语言：javascript复制// Tree is a B tree.
Tree struct {
c int
cmp Cmp
first *d
last *d
r interface{}
ver int64
}Cmp func(a, b int64) intd struct { // data page
c int
d [2*kd 1]de
n *d
p *d
}func (t *Tree) Set(k int64, v *primitive) {
z := t.insert(btDPool.Get().(*d), 0, k, v)
for {
i, ok := t.find(q, k)
if ok {
switch x := q.(type) {
case *x:
if x.c > 2*kx {github.com/cayleygraph/quad@v1.2.4/quad.go
代码语言：javascript复制// Make creates a quad with provided values.
func Make(subject, predicate, object, label interface{}) (q Quad) {
var ok bool
if q.Subject, ok = AsValue(subject); !ok {
q.Subject = String(fmt.Sprint(subject))
}
if q.Predicate, ok = AsValue(predicate); !ok {
q.Predicate = String(fmt.Sprint(predicate))
}
if q.Object, ok = AsValue(object); !ok {
q.Object = String(fmt.Sprint(object))
}
if q.Label, ok = AsValue(label); !ok {
q.Label = String(fmt.Sprint(label))
}
return
}value.go
代码语言：javascript复制func NativeOf(v Value) interface{} {
if v == nil {
return nil
}
return v.Native()
}github.com/cayleygraph/quad@v1.2.4/value.go是一个单独的包，用来做值的类型转换等
代码语言：javascript复制// AsValue converts native type into closest Value representation.
// It returns false if type was not recognized.
func AsValue(v interface{}) (out Value, ok bool) {
if v == nil {
return nil, true
}
switch v := v.(type) {
case Value:
out = v
case string:
out = String(v)
case int:
out = Int(v)
case int8:
out = Int(v)
case int16:
out = Int(v)
case int32:
out = Int(v)
case int64:
out = Int(v)
case uint:
out = Int(v)
case uint8:
out = Int(v)
case uint16:
out = Int(v)
case uint32:
out = Int(v)
case uint64:
out = Int(v)
case float64:
out = Float(v)
case float32:
out = Float(v)
case bool:
out = Bool(v)
case time.Time:
out = Time(v)
default:
return nil, false
}
return out, true
}
