• Home
  • History
  • Annotate
  • only in this directory
Name Date Size

..11-Jan-20224 KiB

.gitignoreH A D11-Jan-202238

.travis.ymlH A D11-Jan-2022328

api.goH A D11-Jan-202224.9 KiB

api_test.goH A D11-Jan-20221.1 KiB

benchmark_get_test.goH A D11-Jan-20222.6 KiB

benchmark_store_big_test.goH A D11-Jan-2022956

benchmark_store_test.goH A D11-Jan-202214 KiB

benchmark_test.goH A D11-Jan-20225.3 KiB

child_collection_test.goH A D11-Jan-20227.5 KiB

collection.goH A D11-Jan-202220.6 KiB

collection_merger.goH A D11-Jan-202210.1 KiB

collection_stats.goH A D11-Jan-20223 KiB

collection_test.goH A D11-Jan-202232.6 KiB

CONTRIBUTING.mdH A D11-Jan-2022964

DESIGN.mdH A D11-Jan-202211.2 KiB

dgm_moss_test.goH A D11-Jan-202224.5 KiB

dgm_test.goH A D11-Jan-20226.6 KiB

file.goH A D11-Jan-20226.4 KiB

file_test.goH A D11-Jan-20222 KiB

graph/H11-Jan-20224 KiB

IDEAS.mdH A D11-Jan-20226.9 KiB

iterator.goH A D11-Jan-202211.9 KiB

iterator_single.goH A D11-Jan-20223.7 KiB

iterator_test.goH A D11-Jan-202212.9 KiB

LICENSE.txtH A D11-Jan-202211.1 KiB

MakefileH A D11-Jan-2022888

mmap.goH A D11-Jan-20221.4 KiB

mmap_gen.goH A D11-Jan-2022958

mmap_test.goH A D11-Jan-20229.1 KiB

mmap_windows.goH A D11-Jan-20221.2 KiB

persister.goH A D11-Jan-20223.6 KiB

persister_test.goH A D11-Jan-202233 KiB

ping.goH A D11-Jan-20221.4 KiB

ping_test.goH A D11-Jan-20221 KiB

README-dgm.mdH A D11-Jan-20221.5 KiB

README-smat.mdH A D11-Jan-2022607

README.mdH A D11-Jan-20228.2 KiB

segment.goH A D11-Jan-202223.7 KiB

segment_index.goH A D11-Jan-20223.8 KiB

segment_index_test.goH A D11-Jan-20226 KiB

segment_stack.goH A D11-Jan-20226.2 KiB

segment_stack_merge.goH A D11-Jan-20225.8 KiB

segment_test.goH A D11-Jan-20221.3 KiB

slice_util.goH A D11-Jan-20222 KiB

slice_util_safe.goH A D11-Jan-20221.4 KiB

smat.goH A D11-Jan-202218.4 KiB

smat_crash_test.goH A D11-Jan-20223 KiB

smat_generate_test.goH A D11-Jan-20221.5 KiB

store.goH A D11-Jan-202219 KiB

store_api.goH A D11-Jan-202213.1 KiB

store_compact.goH A D11-Jan-202215.7 KiB

store_footer.goH A D11-Jan-202213.3 KiB

store_previous.goH A D11-Jan-20221.6 KiB

store_revert.goH A D11-Jan-20222.4 KiB

store_stats.goH A D11-Jan-20223 KiB

store_test.goH A D11-Jan-202254.9 KiB

util_merge.goH A D11-Jan-20221.7 KiB

wrap.goH A D11-Jan-20222.7 KiB

README-dgm.md

1# Instructions for DGM testing for moss
2
3dgm_moss_test.go is a moss component level test that exercises moss.
4
5Included in the test is a simulator of the moss herder memory stalling
6functionality.
7
8The test can be configured to generate a Results*.json file that can be
9used with python script graph/dgm-moss-ploy.py to plot the resutls.
10
11## Steps
12
13Here is an example shell script to exercise the test.
14
15```
16#!/bin/bash
17findDisk()
18{
19    dev=`df ${MossStore} | grep -v Filesystem | awk {'print $1'}`
20    dirName=`dirname ${dev}`
21    devName=`basename ${dev} ${dirName}`
22    echo ${devName}
23}
24
25clearCaches()
26{
27    sudo sync
28    sudo sh -c "echo 1 > /proc/sys/vm/drop_caches"
29    sudo sh -c "echo 2 > /proc/sys/vm/drop_caches"
30    sudo sh -c "echo 3 > /proc/sys/vm/drop_caches"
31
32}
33
34MossStore="/mossstore/MossStoreTest"
35mkdir -p -m=0777 ${MossStore}
36diskMonitor=`findDisk`
37runDesc="${gitInfo}"
38
39go test -v -test.run TestMossDGM -test.timeout 99999s -runTime 5m -memQuota 4gb -keyLength 48 -valueLength 48 -keyOrder random -numWriters 1 -writeBatchSize 100000 -writeBatchThinkTime 1ms -numReaders 16 -readBatchSize 100 -readBatchThinkTime 1ms -outputToFile -dbPath ${MossStore} -diskMonitor ${diskMonitor} -runDescription ${runDesc} -dbCreate
40```
41
42## Ploting a graph of the results
43
44The python script requires numpy, pandas, matploglib
45
46```
47python dgm-moss-plot.py Results_...json
48```
49
50This will process a Results...png file.
51
52## Notes
53
54This test only runs properly on Linux as it gathers stats from /proc.
55

README-smat.md

1# Instructions for smat testing for moss
2
3[smat](https://github.com/mschoch/smat) is a framework that provides
4state machine assisted fuzz testing.
5
6To run the smat tests for moss...
7
8## Prerequisites
9
10    $ go get github.com/dvyukov/go-fuzz/go-fuzz
11    $ go get github.com/dvyukov/go-fuzz/go-fuzz-build
12
13## Steps
14
151.  Generate initial smat corpus:
16```
17    go test -tags=gofuzz -run=TestGenerateSmatCorpus
18```
19
202.  Build go-fuzz test program with instrumentation:
21```
22    go-fuzz-build github.com/couchbase/moss
23```
24
253.  Run go-fuzz:
26```
27    go-fuzz -bin=./moss-fuzz.zip -workdir=workdir/ -timeout=2000
28```
29

README.md

1moss
2----
3
4moss provides a simple, fast, persistable, ordered key-val collection
5implementation as a 100% golang library.
6
7moss stands for "memory-oriented sorted segments".
8
9[![Build Status](https://travis-ci.org/couchbase/moss.svg?branch=master)](https://travis-ci.org/couchbase/moss) [![Coverage Status](https://coveralls.io/repos/github/couchbase/moss/badge.svg?branch=master)](https://coveralls.io/github/couchbase/moss?branch=master) [![GoDoc](https://godoc.org/github.com/couchbase/moss?status.svg)](https://godoc.org/github.com/couchbase/moss) [![Go Report Card](https://goreportcard.com/badge/github.com/couchbase/moss)](https://goreportcard.com/report/github.com/couchbase/moss)
10
11Features
12========
13
14* ordered key-val collection API
15* 100% go implementation
16* key range iterators
17* snapshots provide for isolated reads
18* atomic mutations via a batch API
19* merge operations allow for read-compute-write optimizations
20  for write-heavy use cases (e.g., updating counters)
21* concurrent readers and writers don't block each other
22* child collections allow multiple related collections to be atomically grouped
23* optional, advanced API's to avoid extra memory copying
24* optional lower-level storage implementation, called "mossStore",
25  that uses an append-only design for writes and mmap() for reads,
26  with configurable compaction policy; see: OpenStoreCollection()
27* mossStore supports navigating back through previous commit points in
28  read-only fashion, and supports reverting to previous commit points.
29* optional persistence hooks to allow write-back caching to a
30  lower-level storage implementation that advanced users may wish to
31  provide (e.g., you can hook moss up to leveldb, sqlite, etc)
32* event callbacks allow the monitoring of asynchronous tasks
33* unit tests
34* fuzz tests via go-fuzz & smat (github.com/mschoch/smat);
35  see README-smat.md
36* moss store's diagnostic tool: [mossScope](https://github.com/couchbase/mossScope)
37
38License
39=======
40
41Apache 2.0
42
43Example
44=======
45
46    import github.com/couchbase/moss
47
48    c, err := moss.NewCollection(moss.CollectionOptions{})
49    c.Start()
50    defer c.Close()
51
52    batch, err := c.NewBatch(0, 0)
53    defer batch.Close()
54
55    batch.Set([]byte("car-0"), []byte("tesla"))
56    batch.Set([]byte("car-1"), []byte("honda"))
57
58    err = c.ExecuteBatch(batch, moss.WriteOptions{})
59
60    ss, err := c.Snapshot()
61    defer ss.Close()
62
63    ropts := moss.ReadOptions{}
64
65    val0, err := ss.Get([]byte("car-0"), ropts) // val0 == []byte("tesla").
66    valX, err := ss.Get([]byte("car-not-there"), ropts) // valX == nil.
67
68    // A Get can also be issued directly against the collection
69    val1, err := c.Get([]byte("car-1"), ropts) // val1 == []byte("honda").
70
71For persistence, you can use...
72
73    store, collection, err := moss.OpenStoreCollection(directoryPath,
74        moss.StoreOptions{}, moss.StorePersistOptions{})
75
76Design
77======
78
79The design is similar to a (much) simplified LSM tree, with a stack of
80sorted, immutable key-val arrays or "segments".
81
82To incorporate the next Batch of key-val mutations, the incoming
83key-val entries are first sorted into an immutable "segment", which is
84then atomically pushed onto the top of the stack of segments.
85
86For readers, a higher segment in the stack will shadow entries of the
87same key from lower segments.
88
89Separately, an asynchronous goroutine (the "merger") will continuously
90merge N sorted segments to keep stack height low.
91
92In the best case, a remaining, single, large sorted segment will be
93efficient in memory usage and efficient for binary search and range
94iteration.
95
96Iterations when the stack height is > 1 are implementing using a N-way
97heap merge.
98
99In this design, the stack of segments is treated as immutable via a
100copy-on-write approach whenever the stack needs to be "modified".  So,
101multiple readers and writers won't block each other, and taking a
102Snapshot is also a similarly cheap operation by cloning the stack.
103
104See also the DESIGN.md writeup.
105
106Limitations and considerations
107==============================
108
109NOTE: Keys in a Batch must be unique.  That is, myBatch.Set("x",
110"foo"); myBatch.Set("x", "bar") is not supported.  Applications that
111do not naturally meet this requirement might maintain their own
112map[key]val data structures to ensure this uniqueness constraint.
113
114Max key length is 2^24 (24 bits used to track key length).
115
116Max val length is 2^28 (28 bits used to track val length).
117
118Metadata overhead for each key-val operation is 16 bytes.
119
120Read performance characterization is roughly O(log N) for key-val
121retrieval.
122
123Write performance characterization is roughly O(M log M), where M is
124the number of mutations in a batch when invoking ExecuteBatch().
125
126Those performance characterizations, however, don't account for
127background, asynchronous processing for the merging of segments and
128data structure maintenance.
129
130A background merger task, for example, that is too slow can eventually
131stall ingest of new batches.  (See the CollectionOptions settings that
132limit segment stack height.)
133
134As another example, one slow reader that holds onto a Snapshot or onto
135an Iterator for a long time can hold onto a lot of resources.  Worst
136case is the reader's Snapshot or Iterator may delay the reclaimation
137of large, old segments, where incoming mutations have obsoleted the
138immutable segments that the reader is still holding onto.
139
140Error handling
141==============
142
143Please note that the background goroutines of moss may run into
144errors, for example during optional persistence operations.  To be
145notified of these cases, your application can provide (highly
146recommended) an optional CollectionOptions.OnError callback func which
147will be invoked by moss.
148
149Logging
150=======
151
152Please see the optional CollectionOptions.Log callback func and the
153CollectionOptions.Debug flag.
154
155Performance
156===========
157
158Please try `go test -bench=.` for some basic performance tests.
159
160Each performance test will emit output that generally looks like...
161
162    ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
163    spec: {numItems:1000000 keySize:20 valSize:100 batchSize:100 randomLoad:false noCopyValue:false accesses:[]}
164         open || time:     0 (ms) |        0 wop/s |        0 wkb/s |        0 rop/s |        0 rkb/s || cumulative:        0 wop/s |        0 wkb/s |        0 rop/s |        0 rkb/s
165         load || time:   840 (ms) |  1190476 wop/s |   139508 wkb/s |        0 rop/s |        0 rkb/s || cumulative:  1190476 wop/s |   139508 wkb/s |        0 rop/s |        0 rkb/s
166        drain || time:   609 (ms) |        0 wop/s |        0 wkb/s |        0 rop/s |        0 rkb/s || cumulative:   690131 wop/s |    80874 wkb/s |        0 rop/s |        0 rkb/s
167        close || time:     0 (ms) |        0 wop/s |        0 wkb/s |        0 rop/s |        0 rkb/s || cumulative:   690131 wop/s |    80874 wkb/s |        0 rop/s |        0 rkb/s
168       reopen || time:     0 (ms) |        0 wop/s |        0 wkb/s |        0 rop/s |        0 rkb/s || cumulative:   690131 wop/s |    80874 wkb/s |        0 rop/s |        0 rkb/s
169         iter || time:    81 (ms) |        0 wop/s |        0 wkb/s | 12344456 rop/s |  1446616 rkb/s || cumulative:   690131 wop/s |    80874 wkb/s | 12344456 rop/s |  1446616 rkb/s
170        close || time:     2 (ms) |        0 wop/s |        0 wkb/s |        0 rop/s |        0 rkb/s || cumulative:   690131 wop/s |    80874 wkb/s | 12344456 rop/s |  1446616 rkb/s
171    total time: 1532 (ms)
172    file size: 135 (MB), amplification: 1.133
173    BenchmarkStore_numItems1M_keySize20_valSize100_batchSize100-8
174
175There are various phases in each test...
176
177* open - opening a brand new moss storage instance
178* load - time to load N sequential keys
179* drain - additional time after load for persistence to complete
180* close - time to close the moss storage instance
181* reopen - time to reopen the moss storage instance (OS/filesystem caches are still warm)
182* iter - time to sequentially iterate through key-val items
183* access - time to perform various access patterns, like random or sequential reads and writes
184
185The file size measurement is after final compaction, with
186amplification as a naive calculation to compare overhead against raw
187key-val size.
188
189Contributing changes
190====================
191
192Please see the CONTRIBUTING.md document.
193