Awesome Open Source
Awesome Open Source
Sponsorship

Slim - surprisingly space efficient data types in Golang

Travis-CI AppVeyor GoDoc Report card GolangCI Sourcegraph Coverage Status

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

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.

    GoDoc

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

    GoDoc

    Features:

    • Minimized: 11 bits per key(even less than an 8-byte 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: ~100 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.

    • Loosely coupled design: index logic and data storage is completely separated. Piece of cake using SlimTrie to index huge data.

Memory overhead

Bits/key is stable when key-count(n) increases, and does not relate to key-length(k) either!

The more dense a key set is, the less memory a trie-like data structure costs.

key-count k=64 k=128 k=256
1000 16 16 16
2000 13 13 13
5000 14 14 14

Performance

The following chart shows the time(in nano second) spent on a Get() operation with golang-map, SlimTrie, array and btree by google. It is about 2.2 times faster than the btree by google, or 1.5 times faster than binary search on a sorted array. Smaller is better.

Time(in nano second) spent on a Get() with different key count(n) and key length(k):

See: trie/report/

Status

  • SlimTrie APIs are stable, and has been used in a production env.

    Meanwhile we focus on optimizing memory usage and query performance.

  • Internal data structure are promised to be backward compatible for ever. No data migration issue!

Roadmap

  • [ ] Query by range
  • [ ] Reduce false positive rate
  • [x] 2019-06-03 v0.5.9 Large key set benchmark
  • [x] 2019-05-29 v0.5.6 Support up to 2 billion keys
  • [x] 2019-05-18 v0.5.4 Reduce memory usage from 40 to 14 bits/key
  • [x] 2019-04-20 v0.4.3 Range index: many keys share one index item
  • [x] 2019-04-18 v0.4.1 Marshaling support
  • [x] 2019-03-08 v0.1.0 SlimIndex SlimTrie

Change-log

Change-log

Synopsis

Index keys, get by key

package index_test

import (
	"fmt"
	"strings"

	"github.com/openacid/slim/index"
)

type Data string

func (d Data) Read(offset int64, key string) (string, bool) {
	kv := strings.Split(string(d)[offset:], ",")[0:2]
	if kv[0] == key {
		return kv[1], true
	}
	return "", false
}

func Example() {

	// Accelerate external data accessing (in memory or on disk) by indexing
	// them with a SlimTrie:

	// `data` is a sample of some unindexed data. In our example it is a comma
	// separated key value series.
	//
	// In order to let SlimTrie be able to read data, `data` should have
	// a `Read` method:
	//     Read(offset int64, key string) (string, bool)
	data := Data("Aaron,1,Agatha,1,Al,2,Albert,3,Alexander,5,Alison,8")

	// keyOffsets is a prebuilt index that stores key and its offset in data accordingly.
	keyOffsets := []index.OffsetIndexItem{
		{Key: "Aaron", Offset: 0},
		{Key: "Agatha", Offset: 8},
		{Key: "Al", Offset: 17},
		{Key: "Albert", Offset: 22},
		{Key: "Alexander", Offset: 31},
		{Key: "Alison", Offset: 43},
	}

	// `SlimIndex` is simply a container of SlimTrie and its data.
	st, err := index.NewSlimIndex(keyOffsets, data)
	if err != nil {
		fmt.Println(err)
	}

	// Lookup
	v, found := st.Get("Alison")
	fmt.Printf("key: %q\n  found: %t\n  value: %q\n", "Alison", found, v)

	v, found = st.Get("foo")
	fmt.Printf("key: %q\n  found: %t\n  value: %q\n", "foo", found, v)

	// Output:
	// key: "Alison"
	//   found: true
	//   value: "8"
	// key: "foo"
	//   found: false
	//   value: ""
}

Index key ranges, get by key

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).

package index_test

import (
	"fmt"
	"strings"

	"github.com/openacid/slim/index"
)

type RangeData string

func (d RangeData) Read(offset int64, key string) (string, bool) {
	for i := 0; i < 4; i++ {
		if int(offset) >= len(d) {
			break
		}

		kv := strings.Split(string(d)[offset:], ",")[0:2]
		if kv[0] == key {
			return kv[1], true
		}
		offset += int64(len(kv[0]) + len(kv[1]) + 2)

	}
	return "", false
}

func Example_indexRanges() {

	// Index ranges instead of keys:
	// In this example at most 4 keys shares one index item.

	data := RangeData("Aaron,1,Agatha,1,Al,2,Albert,3,Alexander,5,Alison,8")

	// keyOffsets is a prebuilt index that stores range start, range end and its offset.
	keyOffsets := []index.OffsetIndexItem{
		// Aaron  +--> 0
		// Agatha |
		// Al     |
		// Albert |

		// Alexander +--> 31
		// Alison    |

		{Key: "Aaron", Offset: 0},
		{Key: "Agatha", Offset: 0},
		{Key: "Al", Offset: 0},
		{Key: "Albert", Offset: 0},

		{Key: "Alexander", Offset: 31},
		{Key: "Alison", Offset: 31},
	}

	st, err := index.NewSlimIndex(keyOffsets, data)
	if err != nil {
		panic(err)
	}

	v, found := st.RangeGet("Aaron")
	fmt.Printf("key: %q\n  found: %t\n  value: %q\n", "Aaron", found, v)

	v, found = st.RangeGet("Al")
	fmt.Printf("key: %q\n  found: %t\n  value: %q\n", "Al", found, v)

	v, found = st.RangeGet("foo")
	fmt.Printf("key: %q\n  found: %t\n  value: %q\n", "foo", found, v)

	// Output:
	// key: "Aaron"
	//   found: true
	//   value: "1"
	// key: "Al"
	//   found: true
	//   value: "2"
	// key: "foo"
	//   found: false
	//   value: ""
}

Getting started

Install

go get github.com/openacid/slim

All dependency packages are included in vendor/ dir.

Prerequisites

  • For users (who'd like to build cool stuff with slim):

    Nothing.

  • For contributors (who'd like to make slim better):

    • dep: for dependency management.
    • protobuf: for re-compiling *.proto file if on-disk data structure changes.

    Max OS X:

    brew install dep protobuf
    

    On other platforms you can read more: dep-install, protoc-install.

Who are using slim

baishancloud

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:

Or other type of issue.

Authors

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.


Get A Weekly Email With Trending Projects For These Topics
No Spam. Unsubscribe easily at any time.
go (13,658
golang (3,427
tree (168
memory (98
trie (33
datastructure (21
compress (18

Find Open Source By Browsing 7,000 Topics Across 59 Categories