A simple and efficient thread-safe sharded hashmap for Go

Overview

shardmap

GoDoc

A simple and efficient thread-safe sharded hashmap for Go. This is an alternative to the standard Go map and sync.Map, and is optimized for when your map needs to perform lots of concurrent reads and writes.

Under the hood shardmap uses robinhood hashmap and xxhash.

Getting Started

Installing

To start using shardmap, install Go and run go get:

$ go get -u github.com/tidwall/shardmap

This will retrieve the library.

Usage

The Map type works similar to a standard Go map, and includes four methods: Set, Get, Delete, Len.

var m shardmap.Map
m.Set("Hello", "Dolly!")
val, _ := m.Get("Hello")
fmt.Printf("%v\n", val)
val, _ = m.Delete("Hello")
fmt.Printf("%v\n", val)
val, _ = m.Get("Hello")
fmt.Printf("%v\n", val)

// Output:
// Dolly!
// Dolly!
// <nil>

Performance

Benchmarking conncurrent SET, GET, RANGE, and DELETE operations for sync.Map, map[string]interface{}, github.com/tidwall/shardmap.

go version go1.13 darwin/amd64 (Macbook 2018)

     number of cpus: 12
     number of keys: 1000000
            keysize: 10
        random seed: 1569421428153357000

-- sync.Map --
set: 1,000,000 ops over 12 threads in 955ms, 1,046,873/sec, 955 ns/op
get: 1,000,000 ops over 12 threads in 269ms, 3,718,882/sec, 268 ns/op
rng:       100 ops over 12 threads in 2434ms,       41/sec, 24342711 ns/op
del: 1,000,000 ops over 12 threads in 241ms, 4,156,554/sec, 240 ns/op

-- stdlib map --
set: 1,000,000 ops over 12 threads in 481ms, 2,078,213/sec, 481 ns/op
get: 1,000,000 ops over 12 threads in 45ms, 22,439,321/sec, 44 ns/op
rng:       100 ops over 12 threads in 260ms,       384/sec, 2598202 ns/op
del: 1,000,000 ops over 12 threads in 187ms, 5,339,459/sec, 187 ns/op

-- github.com/tidwall/shardmap --
set: 1,000,000 ops over 12 threads in 78ms, 12,828,089/sec, 77 ns/op
get: 1,000,000 ops over 12 threads in 22ms, 45,686,575/sec, 21 ns/op
rng:       100 ops over 12 threads in 231ms,       432/sec, 2310163 ns/op
del: 1,000,000 ops over 12 threads in 49ms, 20,259,435/sec, 49 ns/op
go version go1.13.1 linux/amd64 (ec2 r5.12xlarge)

     number of cpus: 48
     number of keys: 1000000
            keysize: 10
        random seed: 1569533867316350480

-- sync.Map --
set: 1,000,000 ops over 48 threads in 999ms, 1,001,035/sec, 998 ns/op
get: 1,000,000 ops over 48 threads in 414ms, 2,415,938/sec, 413 ns/op
rng:       100 ops over 48 threads in 548ms,       182/sec, 5483971 ns/op
del: 1,000,000 ops over 48 threads in 250ms, 4,003,491/sec, 249 ns/op

-- stdlib map --
set: 1,000,000 ops over 48 threads in 479ms, 2,085,895/sec, 479 ns/op
get: 1,000,000 ops over 48 threads in 40ms, 25,032,448/sec, 39 ns/op
rng:       100 ops over 48 threads in 116ms,       865/sec, 1155953 ns/op
del: 1,000,000 ops over 48 threads in 222ms, 4,499,962/sec, 222 ns/op

-- github.com/tidwall/shardmap --
set: 1,000,000 ops over 48 threads in 51ms, 19,592,641/sec, 51 ns/op
get: 1,000,000 ops over 48 threads in 7ms, 150,933,098/sec, 6 ns/op
rng:       100 ops over 48 threads in 114ms,       880/sec, 1135747 ns/op
del: 1,000,000 ops over 48 threads in 12ms, 81,879,373/sec, 12 ns/op

Contact

Josh Baker @tidwall

License

shardmap source code is available under the MIT License.

You might also like...
A memory-efficient trie for testing the existence/prefixes of string only(for now).

Succinct Trie A memory-efficient trie for testing the existence/prefixes of string only(for now). Install go get -u github.com/nobekanai/sutrie Docume

Type-safe, zero-allocation sets for Go

Set Package set is a type-safe, zero-allocation port of the excellent package fatih/set. It contains sets for most of the basic types and you can gene

dagger is a fast, concurrency safe, mutable, in-memory directed graph library with zero dependencies
dagger is a fast, concurrency safe, mutable, in-memory directed graph library with zero dependencies

dagger is a blazing fast, concurrency safe, mutable, in-memory directed graph implementation with zero dependencies

A simple set type for the Go language. Trusted by Docker, 1Password, Ethereum and Hashicorp.

golang-set The missing set collection for the Go language. Until Go has sets built-in...use this. Coming from Python one of the things I miss is the s

Simple code just to try out and Binary Tree on Golang.

Character counter | ▮▮▮▮▮▮▮▮ Simple code just to try out and Binary Tree on Golang. Count characters to train openning a file and reading it, as well

A simple Set data structure implementation in Go (Golang) using LinkedHashMap.

Set Set is a simple Set data structure implementation in Go (Golang) using LinkedHashMap. This library allow you to get a set of int64 or string witho

Simple priority queue in Go

Priority Queue in Go ==================== This package provides a priority queue implementation and scaffold interfaces. Installation ------------ U

BTree provides a simple, ordered, in-memory data structure for Go programs.

BTree implementation for Go This package provides an in-memory B-Tree implementation for Go, useful as an ordered, mutable data structure. The API is

A simple Bloom Filter implementation in Go

This is a simple Bloom filter implementation written in Go. For the theory behind Bloom filters, read http://en.wikipedia.org/wiki/Bloom_filter This

Comments
  • panic: bad news

    panic: bad news

    This happens roughly once every few runs (other maps removed):

    go run bench/main.go
    
    go version go1.13 darwin/amd64
    
         number of cpus: 12
         number of keys: 10000000
                keysize: 10
            random seed: 1569543723944908000
    
    -- github.com/tidwall/shardmap --
    set: 10,000,000 ops over 12 threads in 973ms, 10,272,813/sec, 97 ns/op
    get: panic: bad news
    
    goroutine 66 [running]:
    main.main.func2(0x8f87a3, 0xb)
            /Users/cafxx/go/src/github.com/tidwall/shardmap/bench/main.go:155 +0xa1
    github.com/tidwall/lotsa.Ops.func1(0xc0174ef070, 0x989680, 0xc00006e180, 0xb, 0x8bdf47, 0x98967f)
            /Users/cafxx/go/src/github.com/tidwall/lotsa/lotsa.go:45 +0x98
    created by github.com/tidwall/lotsa.Ops
            /Users/cafxx/go/src/github.com/tidwall/lotsa/lotsa.go:39 +0x16c
    
    opened by CAFxX 2
  • Fair bench

    Fair bench

    Hi! Thanks for the awesome package! I had my own concurrent map package based on Orcaman's one, so I took interest on yours immediately, and I have no shame in saying I'm stealing some of your ideas :). Anyway, I think this would be a more fair benchmark, iterating over shards with a function like in yours and sync.Map case.

    opened by antoniomo 1
Owner
Josh Baker
Josh Baker
Go concurrent-safe, goroutine-safe, thread-safe queue

goconcurrentqueue - Concurrent safe queues The package goconcurrentqueue offers a public interface Queue with methods for a queue. It comes with multi

Enrique Bris 225 Nov 26, 2022
go.fifo provides a simple fifo thread-safe queue for the Go programming language

go.fifo Description go.fifo provides a simple FIFO thread-safe queue. *fifo.Queue supports pushing an item at the end with Add(), and popping an item

Foize 42 Aug 29, 2022
Package ring provides a high performance and thread safe Go implementation of a bloom filter.

ring - high performance bloom filter Package ring provides a high performance and thread safe Go implementation of a bloom filter. Usage Please see th

Tanner Ryan 130 Nov 20, 2022
A thread safe map which has expiring key-value pairs

~ timedmap ~ A map which has expiring key-value pairs. go get github.com/zekroTJA/timedmap Intro This package allows to set values to a map which will

zekro 49 Oct 17, 2022
Novel, efficient, and practical image compression with visually appealing results. 🤏 ✨

Tiny Thumb ?? ✨ A novel, efficient, and practical method for lossy image compression, that produces visually appealing thumbnails. This technique is u

Slack 8 Nov 1, 2022
Null Types, Safe primitive type conversion and fetching value from complex structures.

Typ Typ is a library providing a powerful interface to impressive user experience with conversion and fetching data from built-in types in Golang Feat

Gurukami 33 Sep 26, 2022
A Go library for an efficient implementation of a skip list: https://godoc.org/github.com/MauriceGit/skiplist

Fast Skiplist Implementation This Go-library implements a very fast and efficient Skiplist that can be used as direct substitute for a balanced tree o

Maurice Tollmien 239 Nov 25, 2022
Package mafsa implements Minimal Acyclic Finite State Automata in Go, essentially a high-speed, memory-efficient, Unicode-friendly set of strings.

MA-FSA for Go Package mafsa implements Minimal Acyclic Finite State Automata (MA-FSA) with Minimal Perfect Hashing (MPH). Basically, it's a set of str

SmartyStreets (Archives) 293 Oct 27, 2022
Surprisingly space efficient trie in Golang(11 bits/key; 100 ns/get).

Slim - surprisingly space efficient data types in Golang Slim is collection of surprisingly space efficient data types, with corresponding serializati

null 1.8k Dec 4, 2022