golang 源碼分析：cayley-5-
下面我們分析下不同存儲後端是如何註冊的，最後具體分析下，內存存儲的具體實現方式。
獲取內部存儲註冊完成後的實例函數定義如下 graph/registry.go
func NewQuadStore(name string, dbpath string, opts Options) (QuadStore, error) {
r, registered := storeRegistry[name]
return r.NewFunc(dbpath, opts)實例是存儲在全局變量裏
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 函數里完成了註冊。
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
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
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
func Register(name string, r Registration) {
graph.RegisterQuadStore(name, graph.QuadStoreRegistration{
InitFunc: func(addr string, opt graph.Options) error {sql 的註冊 graph/sql/quadstore.go
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
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
}其中有兩個重要屬性
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 的值
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 + 樹
type QuadDirectionIndex struct {
index [4]map[int64]*Tree
}增加四元祖
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
// 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
type String stringgraph/memstore/keys.go
// 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
// 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
func NativeOf(v Value) interface{} {
if v == nil {
return nil
}
return v.Native()
}github.com/cayleygraph/quad@v1.2.4/value.go 是一個單獨的包，用來做值的類型轉換等
// 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
}本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/3aGNttz-6BPUk_w7jkmhmA