couchbase / moss / 244

pending completion

Build # 244

Build Type

push

travis-ci

Committed by

steveyen

Commit Message

update IDEAS.md, as nested collections & histograms are done

Change-Id: Ibc68d0757
Reviewed-on: http://review.couchbase.org/77838
Well-Formed: Build Bot <build@couchbase.com>
Reviewed-by: Steve Yen <steve.yen@gmail.com>
Tested-by: Steve Yen <steve.yen@gmail.com>

Run Details

2948 of 3549 relevant lines covered (83.07%)

40308.81 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

87.9

/segment_stack.go

//  Copyright (c) 2016 Couchbase, Inc.
//  Licensed under the Apache License, Version 2.0 (the "License");
//  you may not use this file except in compliance with the
//  License. You may obtain a copy of the License at
//    http://www.apache.org/licenses/LICENSE-2.0
//  Unless required by applicable law or agreed to in writing,
//  software distributed under the License is distributed on an "AS
//  IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
//  express or implied. See the License for the specific language
//  governing permissions and limitations under the License.

package moss

import "sync"

// A segmentStack is a stack of segments, where higher (later) entries
// in the stack have higher precedence, and should "shadow" any
// entries of the same key from lower in the stack.  A segmentStack
// implements the Snapshot interface.
type segmentStack struct {
        options *CollectionOptions

        a []Segment

        m sync.Mutex // Protects the fields the follow.

        refs int

        lowerLevelSnapshot *SnapshotWrapper

        // incarNum represents this segmentStack's unique incarnation number assigned
        // when the child collection was created. 0 for top-level collection.
        incarNum uint64

        // childSegStacks recursively store child collection segmentStacks.
        childSegStacks map[string]*segmentStack
}

func (ss *segmentStack) addRef() {
        ss.m.Lock()
        ss.refs++
        ss.m.Unlock()
}

func (ss *segmentStack) decRef() {
        ss.m.Lock()
        ss.refs--
        if ss.refs <= 0 {
                if ss.lowerLevelSnapshot != nil {
                        ss.lowerLevelSnapshot.Close()
                        ss.lowerLevelSnapshot = nil
                }
        }
        ss.m.Unlock()
}

// ------------------------------------------------------

// Close releases associated resources.
func (ss *segmentStack) Close() error {
        if ss != nil {
                ss.decRef()
        }
        return nil
}

// ------------------------------------------------------

// Get retrieves a val from a segmentStack.
func (ss *segmentStack) Get(key []byte, readOptions ReadOptions) ([]byte, error) {
        return ss.get(key, len(ss.a)-1, nil, readOptions)
}

// get() retrieves a val from a segmentStack, but only considers
// segments at or below the segStart level.  The optional base
// segmentStack, when non-nil, is used instead of the
// lowerLevelSnapshot, as a form of controllable chaining.
func (ss *segmentStack) get(key []byte, segStart int, base *segmentStack,
        readOptions ReadOptions) ([]byte, error) {
        if segStart >= 0 {
                ss.ensureSorted(0, segStart)

                for seg := segStart; seg >= 0; seg-- {
                        b := ss.a[seg]

                        op, val, err := b.Get(key)
                        if err != nil {
                                return nil, err
                        }
                        if val != nil {
                                if op == OperationDel {
                                        return nil, nil
                                }
                                if op == OperationMerge {
                                        return ss.getMerged(key, val, seg-1, base, readOptions)
                                }
                                return val, nil
                        }
                }
        }

        if base != nil {
                return base.Get(key, readOptions)
        }

        if !readOptions.SkipLowerLevel && ss.lowerLevelSnapshot != nil {
                return ss.lowerLevelSnapshot.Get(key, readOptions)
        } // TODO: else add a special return error indicating cache-miss!

        return nil, nil
}

// ------------------------------------------------------

// getMerged() retrieves a lower level val for a given key and returns
// a merged val, based on the configured merge operator.
func (ss *segmentStack) getMerged(key, val []byte, segStart int,
        base *segmentStack, readOptions ReadOptions) ([]byte, error) {
        var mo MergeOperator
        if ss.options != nil {
                mo = ss.options.MergeOperator
        }
        if mo == nil {
                return nil, ErrMergeOperatorNil
        }

        vLower, err := ss.get(key, segStart, base, readOptions)
        if err != nil {
                return nil, err
        }

        vMerged, ok := mo.FullMerge(key, vLower, [][]byte{val})
        if !ok {
                return nil, ErrMergeOperatorFullMergeFailed
        }

        return vMerged, nil
}

// ------------------------------------------------------

func (ss *segmentStack) ensureSorted(minSeg, maxSeg int) {
        if ss.options == nil || !ss.options.DeferredSort {
                return
        }

        sorted := true // Two phases allows for more concurrent sorting.
        for seg := maxSeg; seg >= minSeg; seg-- {
                sorted = sorted && ss.a[seg].RequestSort(false)
        }

        if !sorted {
                for seg := maxSeg; seg >= minSeg; seg-- {
                        ss.a[seg].RequestSort(true)
                }
        }
}

// ------------------------------------------------------

// SegmentStackStats represents the stats for a segmentStack.
type SegmentStackStats struct {
        CurOps      uint64
        CurBytes    uint64 // Counts key-val bytes only, not metadata.
        CurSegments uint64
}

// AddTo adds the values from this SegmentStackStats to the dest
// SegmentStackStats.
func (sss *SegmentStackStats) AddTo(dest *SegmentStackStats) {
        if sss == nil {
                return
        }

        dest.CurOps += sss.CurOps
        dest.CurBytes += sss.CurBytes
        dest.CurSegments += sss.CurSegments
}

// Stats returns the stats for this segment stack.
func (ss *segmentStack) Stats() *SegmentStackStats {
        rv := &SegmentStackStats{CurSegments: uint64(len(ss.a))}
        for _, seg := range ss.a {
                rv.CurOps += uint64(seg.Len())
                nk, nv := seg.NumKeyValBytes()
                rv.CurBytes += nk + nv
        }
        return rv
}

// ChildCollectionNames returns an array of child collection name strings.
func (ss *segmentStack) ChildCollectionNames() ([]string, error) {
        var childCollections = make([]string, len(ss.childSegStacks))
        idx := 0
        for name := range ss.childSegStacks {
                childCollections[idx] = name
                idx++
        }
        return childCollections, nil
}

// ChildCollectionSnapshot returns a Snapshot on a given child
// collection by its name.
func (ss *segmentStack) ChildCollectionSnapshot(childCollectionName string) (
        Snapshot, error) {
        if ss.childSegStacks == nil {
                return nil, nil
        }
        childSegStack, exists := ss.childSegStacks[childCollectionName]
        if !exists {
                return nil, nil
        }
        childSegStack.addRef()
        return childSegStack, nil
}

// ensureFullySorted recursively ensures that all child segmentStacks
// are sorted from 0 to end.
func (ss *segmentStack) ensureFullySorted() {
        ss.ensureSorted(0, len(ss.a)-1)
        for _, childSnapshot := range ss.childSegStacks {
                childSnapshot.ensureFullySorted()
        }
}

func (ss *segmentStack) isEmpty() bool {
        if len(ss.a) > 0 {
                return false
        }
        for _, childSegStack := range ss.childSegStacks {
                if !childSegStack.isEmpty() {
                        return false
                }
        }
        return true
}

1	// Copyright (c) 2016 Couchbase, Inc.
2	// Licensed under the Apache License, Version 2.0 (the "License");
3	// you may not use this file except in compliance with the
4	// License. You may obtain a copy of the License at
5	// http://www.apache.org/licenses/LICENSE-2.0
6	// Unless required by applicable law or agreed to in writing,
7	// software distributed under the License is distributed on an "AS
8	// IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
9	// express or implied. See the License for the specific language
10	// governing permissions and limitations under the License.
11
12	package moss
13
14	import "sync"
15
16	// A segmentStack is a stack of segments, where higher (later) entries
17	// in the stack have higher precedence, and should "shadow" any
18	// entries of the same key from lower in the stack. A segmentStack
19	// implements the Snapshot interface.
20	type segmentStack struct {
21	options *CollectionOptions
22
23	a []Segment
24
25	m sync.Mutex // Protects the fields the follow.
26
27	refs int
28
29	lowerLevelSnapshot *SnapshotWrapper
30
31	// incarNum represents this segmentStack's unique incarnation number assigned
32	// when the child collection was created. 0 for top-level collection.
33	incarNum uint64
34
35	// childSegStacks recursively store child collection segmentStacks.
36	childSegStacks map[string]*segmentStack
37	}
38
39	func (ss *segmentStack) addRef() {	938✔
40	ss.m.Lock()	938✔
41	ss.refs++	938✔
42	ss.m.Unlock()	938✔
43	}	938✔
44
45	func (ss *segmentStack) decRef() {	3,986✔
46	ss.m.Lock()	3,986✔
47	ss.refs--	3,986✔
48	if ss.refs <= 0 {	6,664✔
49	if ss.lowerLevelSnapshot != nil {	3,507✔
50	ss.lowerLevelSnapshot.Close()	829✔
51	ss.lowerLevelSnapshot = nil	829✔
52	}	829✔
53	}
54	ss.m.Unlock()	3,986✔
55	}
56
57	// ------------------------------------------------------
58
59	// Close releases associated resources.
60	func (ss *segmentStack) Close() error {	4,937✔
61	if ss != nil {	8,923✔
62	ss.decRef()	3,986✔
63	}	3,986✔
64	return nil	4,937✔
65	}
66
67	// ------------------------------------------------------
68
69	// Get retrieves a val from a segmentStack.
70	func (ss *segmentStack) Get(key []byte, readOptions ReadOptions) ([]byte, error) {	20,388✔
71	return ss.get(key, len(ss.a)-1, nil, readOptions)	20,388✔
72	}	20,388✔
73
74	// get() retrieves a val from a segmentStack, but only considers
75	// segments at or below the segStart level. The optional base
76	// segmentStack, when non-nil, is used instead of the
77	// lowerLevelSnapshot, as a form of controllable chaining.
78	func (ss segmentStack) get(key []byte, segStart int, base segmentStack,
79	readOptions ReadOptions) ([]byte, error) {	20,476✔
80	if segStart >= 0 {	37,103✔
81	ss.ensureSorted(0, segStart)	16,627✔
82		16,627✔
83	for seg := segStart; seg >= 0; seg-- {	63,825✔
84	b := ss.a[seg]	47,198✔
85		47,198✔
86	op, val, err := b.Get(key)	47,198✔
87	if err != nil {	47,198✔
88	return nil, err	×
89	}	×
90	if val != nil {	59,823✔
91	if op == OperationDel {	14,720✔
92	return nil, nil	2,095✔
93	}	2,095✔
94	if op == OperationMerge {	10,592✔
95	return ss.getMerged(key, val, seg-1, base, readOptions)	62✔
96	}	62✔
97	return val, nil	10,468✔
98	}
99	}
100	}
101
102	if base != nil {	7,854✔
103	return base.Get(key, readOptions)	3✔
104	}	3✔
105
106	if !readOptions.SkipLowerLevel && ss.lowerLevelSnapshot != nil {	12,137✔
107	return ss.lowerLevelSnapshot.Get(key, readOptions)	4,289✔
108	} // TODO: else add a special return error indicating cache-miss!	4,289✔
109
110	return nil, nil	3,559✔
111	}
112
113	// ------------------------------------------------------
114
115	// getMerged() retrieves a lower level val for a given key and returns
116	// a merged val, based on the configured merge operator.
117	func (ss *segmentStack) getMerged(key, val []byte, segStart int,
118	base *segmentStack, readOptions ReadOptions) ([]byte, error) {	81✔
119	var mo MergeOperator	81✔
120	if ss.options != nil {	162✔
121	mo = ss.options.MergeOperator	81✔
122	}	81✔
123	if mo == nil {	81✔
124	return nil, ErrMergeOperatorNil	×
125	}	×
126
127	vLower, err := ss.get(key, segStart, base, readOptions)	81✔
128	if err != nil {	81✔
129	return nil, err	×
130	}	×
131
132	vMerged, ok := mo.FullMerge(key, vLower, [][]byte{val})	81✔
133	if !ok {	81✔
134	return nil, ErrMergeOperatorFullMergeFailed	×
135	}	×
136
137	return vMerged, nil	81✔
138	}
139
140	// ------------------------------------------------------
141
142	func (ss *segmentStack) ensureSorted(minSeg, maxSeg int) {	18,383✔
143	if ss.options == nil \|\| !ss.options.DeferredSort {	36,497✔
144	return	18,114✔
145	}	18,114✔
146
147	sorted := true // Two phases allows for more concurrent sorting.	269✔
148	for seg := maxSeg; seg >= minSeg; seg-- {	897✔
149	sorted = sorted && ss.a[seg].RequestSort(false)	628✔
150	}	628✔
151
152	if !sorted {	434✔
153	for seg := maxSeg; seg >= minSeg; seg-- {	653✔
154	ss.a[seg].RequestSort(true)	489✔
155	}	489✔
156	}
157	}
158
159	// ------------------------------------------------------
160
161	// SegmentStackStats represents the stats for a segmentStack.
162	type SegmentStackStats struct {
163	CurOps uint64
164	CurBytes uint64 // Counts key-val bytes only, not metadata.
165	CurSegments uint64
166	}
167
168	// AddTo adds the values from this SegmentStackStats to the dest
169	// SegmentStackStats.
170	func (sss SegmentStackStats) AddTo(dest SegmentStackStats) {	183✔
171	if sss == nil {	328✔
172	return	145✔
173	}	145✔
174
175	dest.CurOps += sss.CurOps	38✔
176	dest.CurBytes += sss.CurBytes	38✔
177	dest.CurSegments += sss.CurSegments	38✔
178	}
179
180	// Stats returns the stats for this segment stack.
181	func (ss segmentStack) Stats() SegmentStackStats {	143✔
182	rv := &SegmentStackStats{CurSegments: uint64(len(ss.a))}	143✔
183	for _, seg := range ss.a {	402✔
184	rv.CurOps += uint64(seg.Len())	259✔
185	nk, nv := seg.NumKeyValBytes()	259✔
186	rv.CurBytes += nk + nv	259✔
187	}	259✔
188	return rv	143✔
189	}
190
191	// ChildCollectionNames returns an array of child collection name strings.
192	func (ss *segmentStack) ChildCollectionNames() ([]string, error) {	6✔
193	var childCollections = make([]string, len(ss.childSegStacks))	6✔
194	idx := 0	6✔
195	for name := range ss.childSegStacks {	9✔
196	childCollections[idx] = name	3✔
197	idx++	3✔
198	}	3✔
199	return childCollections, nil	6✔
200	}
201
202	// ChildCollectionSnapshot returns a Snapshot on a given child
203	// collection by its name.
204	func (ss *segmentStack) ChildCollectionSnapshot(childCollectionName string) (
205	Snapshot, error) {	12✔
206	if ss.childSegStacks == nil {	12✔
207	return nil, nil	×
208	}	×
209	childSegStack, exists := ss.childSegStacks[childCollectionName]	12✔
210	if !exists {	12✔
211	return nil, nil	×
212	}	×
213	childSegStack.addRef()	12✔
214	return childSegStack, nil	12✔
215	}
216
217	// ensureFullySorted recursively ensures that all child segmentStacks
218	// are sorted from 0 to end.
219	func (ss *segmentStack) ensureFullySorted() {	153✔
220	ss.ensureSorted(0, len(ss.a)-1)	153✔
221	for _, childSnapshot := range ss.childSegStacks {	182✔
222	childSnapshot.ensureFullySorted()	29✔
223	}	29✔
224	}
225
226	func (ss *segmentStack) isEmpty() bool {	567✔
227	if len(ss.a) > 0 {	1,131✔
228	return false	564✔
229	}	564✔
230	for _, childSegStack := range ss.childSegStacks {	3✔
231	if !childSegStack.isEmpty() {	×
232	return false	×
233	}	×
234	}
235	return true	3✔
236	}

couchbase / moss / 244

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous