Looking for fast, space-efficient key-lookup

• yottaStore

  9 79 1.8

  A datastore aiming at linear scalability up to the yottabyte range. Inspired by dynamo and cassandra.

  

I copied this approach from several papers, with some improvements, for my datastore.

• goleveldb

  15 6,018 0.0 Go

  LevelDB key/value database in Go.

Looks like a job for GoLevelDB.

• WorkOS

  workos.com sponsored

  The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.

  

• bbolt

  18 7,617 9.1 Go

  An embedded key/value database for Go.

  

- bbolt for storage on disk. In order to get the smallest db file size possible make sure you insert the keys in order and set:

• cuckoofilter

  1 1,066 0.0 Go

  Cuckoo Filter: Practically Better Than Bloom

- a cuckoo filter for fast lookup. This has around a 3% false positive rate. There are other implementations however that have a much lower rate. You can store the filter in the database as well in a different bucket so you don't have to rebuild the filter on startup.

• RoaringBitmap

  24 3,377 8.5 Java

  A better compressed bitset in Java: used by Apache Spark, Netflix Atlas, Apache Pinot, Tablesaw, and many others

  

Use a two stage approach, with a bloom/cuckoo filter stored as a https://roaringbitmap.org/ in memory. Then a secondary key/value store on disk (bolt or anything else).

• diskv

  3 1,324 0.0 Go

  A disk-backed key-value store.

https://github.com/peterbourgon/diskv might be a solution

• go

  2,068 119,564 10.0 Go

  The Go programming language

  

Most hash map (or set) implementations also overallocate quite a bit to reduce the number of collisions. You could use a custom map implementation that has a tuned load factor, that way you can trade speed for memory. You can have a look at the go map implementation to see how that could work: https://github.com/golang/go/blob/master/src/runtime/map.go With that said, unless you have a very good reason to go down that rabbit hole I'd avoid it.

• InfluxDB

  www.influxdata.com sponsored

  Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.

  

• pebble

  11 4,448 9.8 Go

  RocksDB/LevelDB inspired key-value database in Go

  

https://github.com/cockroachdb/pebble Pure go SSD native key-value store. You could think of it as map[[]byte][]byte on persistent storage.

• cdb

  1 64 10.0 Go

  A native golang implementation of cdb (http://cr.yp.to/cdb.html) (by colinmarc)

github.com/colinmarc/cdb is a Go implementation,

Suggest a related project