• 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.4 KiB

collection_merger.goH A D11-Jan-20229.9 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.5 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.1 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    defer c.Close()
50
51    batch, err := c.NewBatch(0, 0)
52    defer batch.Close()
53
54    batch.Set([]byte("car-0"), []byte("tesla"))
55    batch.Set([]byte("car-1"), []byte("honda"))
56
57    err = c.ExecuteBatch(batch, moss.WriteOptions{})
58
59    ss, err := c.Snapshot()
60    defer ss.Close()
61
62    ropts := moss.ReadOptions{}
63
64    val0, err := ss.Get([]byte("car-0"), ropts) // val0 == []byte("tesla").
65    valX, err := ss.Get([]byte("car-not-there"), ropts) // valX == nil.
66
67    // A Get can also be issued directly against the collection
68    val1, err := c.Get([]byte("car-1"), ropts) // val1 == []byte("honda").
69
70For persistence, you can use...
71
72    store, collection, err := moss.OpenStoreCollection(directoryPath,
73        moss.StoreOptions{}, moss.StorePersistOptions{})
74
75Design
76======
77
78The design is similar to a (much) simplified LSM tree, with a stack of
79sorted, immutable key-val arrays or "segments".
80
81To incorporate the next Batch of key-val mutations, the incoming
82key-val entries are first sorted into an immutable "segment", which is
83then atomically pushed onto the top of the stack of segments.
84
85For readers, a higher segment in the stack will shadow entries of the
86same key from lower segments.
87
88Separately, an asynchronous goroutine (the "merger") will continuously
89merge N sorted segments to keep stack height low.
90
91In the best case, a remaining, single, large sorted segment will be
92efficient in memory usage and efficient for binary search and range
93iteration.
94
95Iterations when the stack height is > 1 are implementing using a N-way
96heap merge.
97
98In this design, the stack of segments is treated as immutable via a
99copy-on-write approach whenever the stack needs to be "modified".  So,
100multiple readers and writers won't block each other, and taking a
101Snapshot is also a similarly cheap operation by cloning the stack.
102
103See also the DESIGN.md writeup.
104
105Limitations and considerations
106==============================
107
108NOTE: Keys in a Batch must be unique.  That is, myBatch.Set("x",
109"foo"); myBatch.Set("x", "bar") is not supported.  Applications that
110do not naturally meet this requirement might maintain their own
111map[key]val data structures to ensure this uniqueness constraint.
112
113Max key length is 2^24 (24 bits used to track key length).
114
115Max val length is 2^28 (28 bits used to track val length).
116
117Metadata overhead for each key-val operation is 16 bytes.
118
119Read performance characterization is roughly O(log N) for key-val
120retrieval.
121
122Write performance characterization is roughly O(M log M), where M is
123the number of mutations in a batch when invoking ExecuteBatch().
124
125Those performance characterizations, however, don't account for
126background, asynchronous processing for the merging of segments and
127data structure maintenance.
128
129A background merger task, for example, that is too slow can eventually
130stall ingest of new batches.  (See the CollectionOptions settings that
131limit segment stack height.)
132
133As another example, one slow reader that holds onto a Snapshot or onto
134an Iterator for a long time can hold onto a lot of resources.  Worst
135case is the reader's Snapshot or Iterator may delay the reclaimation
136of large, old segments, where incoming mutations have obsoleted the
137immutable segments that the reader is still holding onto.
138
139Error handling
140==============
141
142Please note that the background goroutines of moss may run into
143errors, for example during optional persistence operations.  To be
144notified of these cases, your application can provide (highly
145recommended) an optional CollectionOptions.OnError callback func which
146will be invoked by moss.
147
148Logging
149=======
150
151Please see the optional CollectionOptions.Log callback func and the
152CollectionOptions.Debug flag.
153
154Performance
155===========
156
157Please try `go test -bench=.` for some basic performance tests.
158
159Each performance test will emit output that generally looks like...
160
161    ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
162    spec: {numItems:1000000 keySize:20 valSize:100 batchSize:100 randomLoad:false noCopyValue:false accesses:[]}
163         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
164         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
165        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
166        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
167       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
168         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
169        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
170    total time: 1532 (ms)
171    file size: 135 (MB), amplification: 1.133
172    BenchmarkStore_numItems1M_keySize20_valSize100_batchSize100-8
173
174There are various phases in each test...
175
176* open - opening a brand new moss storage instance
177* load - time to load N sequential keys
178* drain - additional time after load for persistence to complete
179* close - time to close the moss storage instance
180* reopen - time to reopen the moss storage instance (OS/filesystem caches are still warm)
181* iter - time to sequentially iterate through key-val items
182* access - time to perform various access patterns, like random or sequential reads and writes
183
184The file size measurement is after final compaction, with
185amplification as a naive calculation to compare overhead against raw
186key-val size.
187
188Contributing changes
189====================
190
191Please see the CONTRIBUTING.md document.
192