slim

Slim - surprisingly space efficient data types in Golang

Slim is collection of surprisingly space efficient data types, with corresponding serialization APIs to persisting them on-disk or for transport.

• Why slim
• Performance and memory overhead
• Synopsis
  • 1. Index on-disk key-values
  • 2. Sparse index
  • 3. Range scan
• Filter mode and KV mode.
• Try it
  • Versions
• Who are using slim
• Slim internal
  • Protobuf data structures
  • Regenerating protobuf code
• Feedback and contributions
• Authors
• License

Why slim

As data on internet keeps increasing exponentially, the capacity gap between memory and disk becomes greater.

Most of the time, a data itself does not need to be loaded into expensive main memory. Only the much more important information, WHERE-A-DATA-IS, deserve a seat in main memory.

This is what slim does, keeps as little information as possible in main memory, as a minimized index of huge amount external data.

• SlimIndex: is a common index structure, building on top of SlimTrie.

• SlimTrie is the underlying index data structure, evolved from trie. Features:

  • Minimized: 11 bits per key(far less than an 64-bits pointer!!).

  • Stable: memory consumption is stable in various scenarios. The Worst case converges to average consumption tightly. See benchmark.

  • Loooong keys: You can have VERY long keys(16K bytes), without any waste of memory(and money). Do not waste your life writing another prefix compression:). (aws-s3 limits key length to 1024 bytes). Memory consumption only relates to key count, not to key length.

  • Ordered: like btree, keys are stored. Range-scan will be ready in 0.6.0.

  • Fast: ~150 ns per Get(). Time complexity for a get is O(log(n) + k); n: key count; k: key length.

  • Ready for transport: a single proto.Marshal() is all it requires to serialize, transport or persisting on disk etc.

Performance and memory overhead

• 3.3 times faster than the btree.

• 2.3 times faster than binary search.

• Memory overhead is about 11 bit per key.

The data struct in this benchmark is a slice of key-value pairs with a SlimTrie serving as the index. The slim itself is built in the filter mode, to maximize memory reduction and performance. The whole struct slimKV is a fully functional kv-store, just like a static btree.

type slimKV struct {
    slim *trie.SlimTrie
    Elts []*KVElt
}
type KVElt struct {
    Key string
    Val int32
}

You can find the benchmark code in benchmark;

Read more about Performance

Synopsis

1. Index on-disk key-values

One of the typical usages of slim is to index serialized data on disk(e.g., key value records in a SSTable). By keeping a slim in memory, one can quickly find the on-disk offset of the record by a key.

…

2. Sparse index

Create an index item for every 4(or more as you wish) keys.

Let several adjacent keys share one index item reduces a lot memory cost if there are huge amount keys in external data. Such as to index billions of 4KB objects on a 4TB disk(because one disk IO costs 20ms for either reading 4KB or reading 1MB).

…

3. Range scan

Slim can also be used as a traditional in-memory kv-store: Building a slim with Opt{ Complete: Bool(true) }, it won't strip out any information(e.g., it won't eliminate single-branch labels) and it will functions the same as a btree. This snippet shows how to iterate key values.

…

Filter mode and KV mode.

Slim can be built into either a filter(like bloom filter but with key order preserved.) or a real kv-store(like btree) There is an option in NewSlimTrie(..., option) to control the building behavior. Ref: Opt

• To use slim as a kv-store, set the option to Complete then there won't be false positives.

• To use it as a filter, set InnerPrefix, LeafPrefix to false(Complete implies InnerPrefix==true and LeafPrefix==true). Then slim won't store any single branch label in the trie it builds.

  With InnerPrefix==true, it does not reduce a single label branch that leads to an inner node.

  With LeafPrefix==true, it does not reduce a single label branch that leads to a leaf node.

  E.g.:

  复制

  // Complete
  InnerPrefix: true
  LeafPrefix: true
  ^ -a-> 1 -b-> $
   `-c-> 2 -x-> 3 -y-> $
                 `-z-> $
  
  InnerPrefix: true
  LeafPrefix: false
  ^ -a-> $
   `-c-> 2 -x-> 3 -y-> $
                 `-z-> $
  
  InnerPrefix: false
  LeafPrefix: true
  ^ -a-> 1 -b-> $
   `-c-> 3 -y-> $
          `-z-> $
  
  InnerPrefix: false
  LeafPrefix: false
  ^ -a-> $
   `-c-> 3 -y-> $
          `-z-> $

The memory consumption in filter mode and kv mode differs significantly. The following chart shows memory consumption by 1 million var-length string, 10 to 20 byte in different mode:

Try it

Install

go get github.com/openacid/slim/trie

Change-log: Change-log

Versions

A newer version y being compatible with an older version x means y can load data serialized by x. But x should never try to load data serialized by a newer version y.

• v0.5.* is compatible with 0.2.*, 0.3.*, 0.4.*, 0.5.*.
• v0.4.* is compatible with 0.2.*, 0.3.*, 0.4.*.
• v0.3.* is compatible with 0.2.*, 0.3.*.
• v0.2.* is compatible with 0.2.*.

Who are using slim

baishancloud

Slim internal

Protobuf data structures

Slim uses protobuf to define its on-disk data structures and as its serialization engine. All .proto files use proto3 syntax.

The protobuf definitions are in the following files:

• array/bitmap.proto: Bits – a bitmap with rank index, used as the building block for sparse arrays.

• array/array.proto: Array32 – a 32-bit sparse array backed by bitmaps and offset tables.

• trie/slim.proto: Bitmap, VLenArray, and Slim – the core trie structures. Slim stores node-type bitmaps, inner-node label bitmaps, short-bitmap tables, inner/leaf prefixes, and serialized leaf values.

These structures are serialized with proto.Marshal() and deserialized with proto.Unmarshal() from the github.com/golang/protobuf package (v1.3.1).

Regenerating protobuf code

The generated Go files (*.pb.go) should not be edited by hand. To regenerate them after modifying a .proto file:

1. Install protoc (the Protocol Buffers compiler). See protoc installation.

2. Install the Go protobuf plugin:

   bash复制

   go install github.com/golang/protobuf/protoc-gen-go@latest

3. Re-generate the Go source:

   bash复制

   # array package (has a go:generate directive in array/gen.go)
   go generate ./array/...
   
   # trie package
   cd trie && protoc --proto_path=. --go_out=. slim.proto

Note: trie/slim.proto was originally built with protoc-gen-go v1.2.0. When regenerating, make sure the generated code is compatible with the module dependency github.com/golang/protobuf v1.3.1.

Feedback and contributions

Feedback and Contributions are greatly appreciated.

At this stage, the maintainers are most interested in feedback centered on:

• Do you have a real life scenario that slim supports well, or doesn't support at all?
• Do any of the APIs fulfill your needs well?

Let us know by filing an issue, describing what you did or wanted to do, what you expected to happen, and what actually happened:

• bug-report
• improve-document
• feature-request

Or other type of issue.

Authors

• 刘保海 marshaling
• 吴义谱 array
• 张炎泼 slimtrie design
• 李文博 trie-compressing, trie-search
• 李树龙 marshaling

See also the list of contributors who participated in this project.

License

This project is licensed under the MIT License - see the LICENSE file for details.