a thread-safe concurrent map for go

Overview

concurrent map Build Status

As explained here and here, the map type in Go doesn't support concurrent reads and writes. concurrent-map provides a high-performance solution to this by sharding the map with minimal time spent waiting for locks.

Prior to Go 1.9, there was no concurrent map implementation in the stdlib. In Go 1.9, sync.Map was introduced. The new sync.Map has a few key differences from this map. The stdlib sync.Map is designed for append-only scenarios. So if you want to use the map for something more like in-memory db, you might benefit from using our version. You can read more about it in the golang repo, for example here and here

usage

Import the package:

import (
	"github.com/orcaman/concurrent-map"
)
go get "github.com/orcaman/concurrent-map"

The package is now imported under the "cmap" namespace.

example

	// Create a new map.
	m := cmap.New()

	// Sets item within map, sets "bar" under key "foo"
	m.Set("foo", "bar")

	// Retrieve item from map.
	if tmp, ok := m.Get("foo"); ok {
		bar := tmp.(string)
	}

	// Removes item under key "foo"
	m.Remove("foo")

For more examples have a look at concurrent_map_test.go.

Running tests:

go test "github.com/orcaman/concurrent-map"

guidelines for contributing

Contributions are highly welcome. In order for a contribution to be merged, please follow these guidelines:

  • Open an issue and describe what you are after (fixing a bug, adding an enhancement, etc.).
  • According to the core team's feedback on the above mentioned issue, submit a pull request, describing the changes and linking to the issue.
  • New code must have test coverage.
  • If the code is about performance issues, you must include benchmarks in the process (either in the issue or in the PR).
  • In general, we would like to keep concurrent-map as simple as possible and as similar to the native map. Please keep this in mind when opening issues.

language

license

MIT (see LICENSE file)

Comments
  • Go map is not good at storing huge key/value ?

    Go map is not good at storing huge key/value ?

    Hi, this is my codes.

    package main
    
    import "net/http"
    import "fmt"
    import "github.com/streamrail/concurrent-map"
    import (
    	"crypto/rand"
    	"encoding/hex"
    	"log"
    	_ "net/http/pprof"
    	"runtime"
    	"strconv"
    )
    
    var myMap = cmap.New()
    
    func main() {
    	runtime.GOMAXPROCS(runtime.NumCPU())
    	log.Println("here start test")
    	http.HandleFunc("/", myHandler)
    	http.HandleFunc("/delete", deHandler)
    	log.Fatal(http.ListenAndServe(":9090", nil))
    }
    
    func myHandler(w http.ResponseWriter, r *http.Request) {
    
    	str := "aaaaaaaaaaaaaaaaaaaaaaaa"
    	for i := 0; i < 10000000; i++ {
    		key := str + strconv.Itoa(i)
    		myMap.Set(key, "8ff98326-2187-4de2-924e-af5098921aba")
    	}
    	// myMap.Set(randString(), "1000")
    
    	fmt.Println(myMap.Count())
    	w.Write([]byte(strconv.Itoa(myMap.Count())))
    }
    
    func deHandler(w http.ResponseWriter, r *http.Request) {
    	fmt.Println("delete")
    	fmt.Println(myMap.Count())
    	str := "aaaaaaaaaaaaaaaaaaaaaaaa"
    
    	for i := 0; i < 10000000; i++ {
    		key := str + strconv.Itoa(i)
    		myMap.Remove(key)
    	}
    	runtime.GC()
    	fmt.Println("after delete")
    	fmt.Println(myMap.Count())
    	w.Write([]byte(strconv.Itoa(myMap.Count())))
    }
    
    func randString() string {
    	b := make([]byte, 10)
    	if _, err := rand.Read(b); err != nil {
    		panic(err)
    	}
    	return hex.EncodeToString(b)
    }
    

    The server consumes about 1.4G memory. And when I request the "localhost:9090/delete", myMap.Count() is 0. But the memory is not reduced.

    I use pprof, the results is:

     go tool pprof http://localhost:9090/debug/pprof/heap
    Fetching profile from http://localhost:9090/debug/pprof/heap
    Saved profile in /home/user/pprof/pprof.for_go.localhost:9090.alloc_objects.alloc_space.inuse_objects.inuse_space.018.pb.gz
    Entering interactive mode (type "help" for commands)
    (pprof) top
    582.01MB of 582.01MB total (  100%)
    Dropped 9 nodes (cum <= 2.91MB)
    Showing top 10 nodes out of 11 (cum >= 582.01MB)
          flat  flat%   sum%        cum   cum%
         544MB 93.47% 93.47%      544MB 93.47%  runtime.hashGrow
       32.51MB  5.59% 99.05%   582.01MB   100%  runtime.mapassign
        5.50MB  0.95%   100%     5.50MB  0.95%  runtime.evacuate
             0     0%   100%   582.01MB   100%  github.com/streamrail/concurrent-map.(*ConcurrentMap).Set
             0     0%   100%   582.01MB   100%  main.myHandler
             0     0%   100%   582.01MB   100%  net/http.(*ServeMux).ServeHTTP
             0     0%   100%   582.01MB   100%  net/http.(*conn).serve
             0     0%   100%   582.01MB   100%  net/http.HandlerFunc.ServeHTTP
             0     0%   100%   582.01MB   100%  net/http.serverHandler.ServeHTTP
             0     0%   100%   582.01MB   100%  runtime.goexit
    
    

    And I read some posts, maybe map is not good at storing huge key/value ?

    opened by pathbox 11
  • Support for 1.18 generics

    Support for 1.18 generics

    Hello!

    I found myself beginning to port some personal projects to 1.18 and found that this library didn't yet have any support for generics. So, I figured I might as well take a swing at it.

    I'm not exactly sure what the right path is for making this available is since 1.18 is still a beta. Regardless, hopefully this is useful to others :)

    opened by ImVexed 7
  • Allow for configurable number of shards

    Allow for configurable number of shards

    closes #17

    allows for users to get a concurrent map with a configurable number of shards

    made it an optional "list" so that the .New() call signature doesn't change.

    I've also set SHARD_COUNT to be a constant. This could break people, but I think it's better for users not to be modifying globals to change the libraries behavior.

    opened by sparrc 5
  • Golang 1.9 and concurrent map

    Golang 1.9 and concurrent map

    Hello,

    Thanks for this package that has been useful for years. Golang 1.9 now provides a concurrent map in standard library. Consider mentioning it on the README for those using latest version of Golang.

    Though, the package is still very useful for older versions :)

    opened by matcornic 4
  • Fix deadlock when using Iter/IterBuffered

    Fix deadlock when using Iter/IterBuffered

    As mentioned by @efeller. When Using the current implementation, after calling Iter/IterBuffered, if the returned channel were not drained, some readlock may not be properly released. Which cause subsequent call to change the map, namely Set/Remove/Pop operations to block forever, thus a deadlock occurs.

    We introduce two test functions (TestUnDrainedIter and TestUnDrainedIterBuffered) which demonstrate the bug.

    This main idea of the fix is to take a snapshot of the current concurrentMap when calling Iter/IterBuffered. We factor out a snapshot function here, which returns an array of buffered channels(one per each shard, the readlocks are released after the related channel is populated). They then fan in to a return channel. In the buffered case, the size of the returned channel is the sum of length of all the channels. We avoid using m.Count() here since m may change between the function calls, which makes it inaccurate.

    This fix passes those two test functions mentioned before.

    opened by flyingfoxlee 4
  • Index out of range

    Index out of range

    Got index out of range panic, https://github.com/streamrail/concurrent-map/blob/master/concurrent_map_template.txt#L34

    No idea how that happened, afaik it should not. Marvell PJ4Bv7 Processor rev 2 (v7l)

    opened by sammy007 4
  • map.Items block indifinetly.

    map.Items block indifinetly.

    If you declare a concurrentMap item without creating it with New() then calling map.Items blocks forever.

            var work cmap.ConcurrentMap
    	for k, _ := range work.Items() {
    		fmt.Println(k)
    	}
            //Never reached
    

    I think this should be treated as a bug, it should panic just like how other methods panic when the map hasn't been created.

    opened by dreson4 3
  • Why not having go routines in IterCB ?

    Why not having go routines in IterCB ?

    The current implementation of iterCB is quite simple:

    // Callback based iterator, cheapest way to read
    // all elements in a map.
    func (m ConcurrentMap) IterCb(fn IterCb) {
    	for idx := range m {
    		shard := (m)[idx]
    		shard.RLock()
    		for key, value := range shard.items {
    			fn(key, value)
    		}
    		shard.RUnlock()
    	}
    }
    

    We could create SHARD_COUNT go routines , one for each shard, and do some parrallelism here. If one callback function does lock the shard, that will keep the other ones unlocked.

    Any specific reason why this is implemented this way ?

    opened by a-lucas 3
  • Hashing: Why not using hash/fnv?

    Hashing: Why not using hash/fnv?

    Context: concurrent-map uses FNV-1 (see: http://www.isthe.com/chongo/tech/comp/fnv/) to consistently map keys to one of its internal shards.

    Surprisingly, it does not make use of hash/fnv, but instead relies on a custom implementation (see: https://github.com/orcaman/concurrent-map/blob/master/concurrent_map.go#L285).

    I was about to make a PR to correct this, but I noticed that in the tests we actually check the behavior of the custom implementation against hash/fnv (see: https://github.com/orcaman/concurrent-map/blob/master/concurrent_map_test.go#L389).

    What is the reason for that? I see that the native implementation is stateful but this can be work-around easily:

    // Returns shard under given key
    func (m ConcurrentMap) GetShard(key string) *ConcurrentMapShared {
    	return m[uint(fnv32(key))%uint(SHARD_COUNT)]
    }
    

    would become:

    // Returns shard under given key
    func (m ConcurrentMap) GetShard(key string) *ConcurrentMapShared {
            hash := fnv.New32()
            hash.Write([]byte(key))
            hashKey := hash.Sum32()
            return m[hashKey%uint32(SHARD_COUNT)]
    }
    

    which is slightly more verbose, but makes us rely on a maintained implementation of FNV-1. Is there a reason I am not seeing for this?

    opened by erwanor 3
  • error when use with channel

    error when use with channel

    hi,i use buffer channels as map value for thread safe,when test use 10 goroutines the value got from channel was not same with the one send in,any suggestion?

    testmap := cmap.New()
        fmt.Println("SyncMapNew:    ", TestInParallel(&testmap, 10))
    
    func TestInParallel(g *cmap.ConcurrentMap, n int) time.Duration {
        start := time.Now()
        var wait sync.WaitGroup
    
        for i := 0; i < n; i++ {
            wait.Add(1)
            go func() {
                TheTest(g, rand.New(rand.NewSource(int64(i*500))))
                wait.Done()
            }()
        }
        wait.Wait()
        return time.Now().Sub(start)
    }
    func TheTest(g *cmap.ConcurrentMap, rnd *rand.Rand) time.Duration {
        start := time.Now()
        var key string
        var value time.Time
        //var got time.Time
        for i := 0; i < 10000; i++ {
            key = strconv.Itoa(int(rnd.Int31n(50000)))
            if g.Has(key) == false {
                g.Set(key, make(chan time.Time, 100))
            }
            tchan, _ := g.Get(key)
            castchan := tchan.(chan time.Time)
            //castchan := make(chan time.Time, 100)
            value = time.Now()
            castchan <- value
            got := <-castchan
            g.Set(key, castchan)
            if value != got {
                panic(fmt.Sprintf("ERROR: expected %v, got %v", value, got))
            }
        }
        return time.Now().Sub(start)
    }
    
    opened by sdhjl2000 3
  • Renamed 'Add' to 'Set'

    Renamed 'Add' to 'Set'

    Although I updated the comment and changed the method name as well, at the very least the comment should state what happens when the key already exists in the map (even if it becomes obvious when reading the source).

    opened by crufter 3
  • add a clone() and append()?

    add a clone() and append()?

    hello,as the title ,can you add a clone func to deep copy a cmap to a new one? and for the values like string,add a function maybe named append to append new string to the old ones stored before,because if the string stored in cmap is large,i get it and cancat with another large string will cost a lot of memory

    opened by Nyx2022 1
  • Add non locking versions of Get, Set and Has

    Add non locking versions of Get, Set and Has

    I have personally had a requirement to do multiple consecutive operations using the same key with the requirement that nothing can change from start to end. To enable this, I propose explicitly named versions of the Get, Set and Has functions which do not take out locks on the shard. Instead, it is up to the user to use the GetShard method and lock/unlock it correctly.

    The three functions would look like

    func (m ConcurrentMap) UnlockedSet(key string, value interface{})
    
    func (m ConcurrentMap) UnlockedGet(key string) (interface{}, bool)
    
    func (m ConcurrentMap) UnlockedHas(key string) bool
    

    I'm not sure about the naming. Maybe UnsafeGet, UnsafeSet and UnsafeHas is better?

    Here's an example of how I think this could be useful

    shard := conMap.GetShard(key)
    shard.RLock()
    pointerToMyStruct, ok := conMap.UnlockedGet(key)
    // Some other thread might be trying to write to this same key but, we still have a lock!
    if ok {
        pointerToMyStruct.ReadSomeCoolInfo()
    }
    shard.RUnlock()
    // Now the write on the other thread will go-ahead
    

    In my case, I'm developing a cache where entries expire. I want to ensure that if the value has expired when the Get call is made, it's still expired when when ReadSomeCoolInfo call is made. If another thread were allowed to refresh the value between the two functions, it would cause me to return the wrong information.

    The alternative to these functions would be to expose items on the shards to other packages and let the developer dig in and do it all manually.

    opened by Lochlanna 5
  • Eliminate false sharing possibility

    Eliminate false sharing possibility

    The current implementation leaves non-zero possibility of false sharing between ConcurrentMapShared structs since they're allocated on heap in a loop in the New function. Hence, there is a possibility that some pairs of these structs get on the same cache line. In such situation (it's called false sharing), even a read from different shards would lead to contention (and CPU cache traffic) since RLock() does a write (atomic increment over an internal counter; lock xadd instruction in x86) from the memory perspective.

    The simplest way to reproduce false sharing is to run the following benchmark:

    func BenchmarkGetSame(b *testing.B) {
    	SHARD_COUNT = 2 // set num of shards to 2 for the simpler reproduction
    	m := New()
    	cdone := make(chan struct{}, 2)
    	m.Set("key1", "value")
    	m.Set("key2", "value")
    	b.ResetTimer()
    	go func() {
    		for i := 0; i < b.N; i++ {
    			// it's safer to use the returned value, but the compiler doesn't eliminate this code for me
    			m.Get("key1")
    		}
    		cdone <- struct{}{}
    	}()
    	go func() {
    		for i := 0; i < b.N; i++ {
    			m.Get("key2")
    		}
    		cdone <- struct{}{}
    	}()
    	<-cdone
    	<-cdone
    }
    

    Environment: Ubuntu 20.04, i5-8300h CPU, Go 1.16.2

    Baseline:

    BenchmarkGetSame-8   	11753236	       100.1 ns/op	       0 B/op	       0 allocs/op
    

    Note: there is a small chance that the shards will get allocated with enough distance, so make sure to run the benchmark multiple times in order to see the worst case scenario. On my machine the worst case occurred most of the runs.

    This PR:

    BenchmarkGetSame-8   	52440186	        22.13 ns/op	       0 B/op	       0 allocs/op
    

    Consider this PR to be an experiment aimed to demonstrate the false sharing effect and an approach to get rid of it.

    opened by puzpuzpuz 0
  • Performance issues during traversal

    Performance issues during traversal

    When we are traversing frequently, using IterBuffered() will generate a lot of memory garbage, which will cause a lot of burden on the GC of the program. At this time, we need to traverse externally, so we have to provide the items method

    opened by big-uncle 2
  • puzzled about func ConcurrentMap.Key()

    puzzled about func ConcurrentMap.Key()

    func (m ConcurrentMap) Keys() []string {
    	count := m.Count()
    
    	time.Sleep(5*time.Second)
    
    	ch := make(chan string, count)
    	go func() {
    		// Foreach shard.
    		wg := sync.WaitGroup{}
    		wg.Add(SHARD_COUNT)
    		for _, shard := range m {
    			go func(shard *ConcurrentMapShared) {
    				// Foreach key, value pair.
    				shard.RLock()
    				for key := range shard.items {
    					ch <- key
    				}
    				shard.RUnlock()
    				wg.Done()
    			}(shard)
    		}
    		wg.Wait()
    		close(ch)
    	}()
    
    	// Generate keys
    	keys := make([]string, 0, count)
    	for k := range ch {
    		keys = append(keys, k)
    	}
    	return keys
    }
    

    as the func shows, m.Count() is called before loop keys from shards. However, there was no direct connect between Cont() res and the length of keys. So why the func is designed to count first ?

    opened by bluesky1024 7
Releases(v2.0.0)
Owner
Or Hiltch
Founder @Skyline_AI / Founder @StreamRail (acquired by @ironSource) / Machine Learning Hero @awscloud
Or Hiltch
Lightweight, Simple, Quick, Thread-Safe Golang Stack Implementation

stack Lightweight, Simple, Quick, Thread-Safe Golang Stack Implementation Purpose Provide a fast, thread safe, and generic Golang Stack API with minim

Brendan Wilson 5 May 3, 2022
A simple thread-safe, fixed size LRU written in Go. Based on dominictarr's Hashlru Algorithm. 🔃

go-hashlru A simple thread-safe, fixed size LRU written in Go. Based on dominictarr's Hashlru Algorithm. ?? Uses map[interface{}]interface{} to allow

Saurabh Pujari 72 Sep 18, 2022
Leftright - A concurrent map that is optimized for scenarios where reads are more frequent than writes

leftright A concurrent map that is optimized for scenarios where reads are more

Yang Pan 1 Jan 30, 2022
A concurrent rate limiter library for Golang based on Sliding-Window rate limiter algorithm.

ratelimiter A generic concurrent rate limiter library for Golang based on Sliding-window rate limitng algorithm. The implementation of rate-limiter al

Narasimha Prasanna HN 218 Sep 7, 2022
A concurrent Download Manager written in Go

golang-download-manager A concurrent Download Manager written in Go Changes In main.go file paste the file url in fileUrl variable paste the path for

Sabuj Jana 3 Aug 16, 2022
Go library for decoding generic map values into native Go structures and vice versa.

mapstructure mapstructure is a Go library for decoding generic map values to structures and vice versa, while providing helpful error handling. This l

Mitchell Hashimoto 6.2k Sep 27, 2022
💪 Helper Utils For The Go: string, array/slice, map, format, cli, env, filesystem, test and more.

?? Helper Utils For The Go: string, array/slice, map, format, cli, env, filesystem, test and more. Go 的一些工具函数,格式化,特殊处理,常用信息获取等等

Gookit 921 Sep 24, 2022
Fast integer map for uint32-to-uint32

Uint32-to-Uint32 Map This repository contains an implementation of uint32-to-uint32 map which is ~20-50% faster than Go standard map for the same type

Roman Atachiants 21 Sep 21, 2022
read copy update map for golang 1.18+

(R)ead-(C)opy-Update read copy update map for golang 1.18+ How it works This is a simple generic implementation for https://en.wikipedia.org/wiki/Read

Michael Ernst 11 Mar 30, 2022
Experimenting with golang generics to implement functional favorites like filter, map, && reduce.

funcy Experimenting with golang generics to implement functional favorites like filter, map, && reduce. 2021-12 To run the tests, you need to install

null 0 Dec 29, 2021
Map downloader and configurator for KillingFloor 2

kf2-map-config Copy the kf2-map-config.exe and maps.txt into the Killing Floor2

Peter Spiess-Knafl 1 Jul 2, 2022
Automatically creates & tiles .tmx format maps from a world map interface

Autotile Create tiled maps for an arbitrarily large world space from a simple interface, then add larger objects randomly with simple rules (eg. place

null 2 Aug 19, 2022
Q2entities - Parse the entities string from a Quake 2 .bsp map file. Written in Go

Q2Entities A simple command-line utility to extract the entities string from a Quake 2 map file. Entities? Binary Space Partitioning maps (.bsp) conta

null 1 Apr 9, 2022
Goterators - A util library that Supports aggregate & transforms functions Go. Such as filter, map, reduce, find, exist

Goterators Goterators is util library that Supports aggregate & transforms functions Go, including: for-each find exist reduce filter map API and func

Thuc Le 90 Sep 22, 2022
Slice - provides generic Map, Reduce and Filter functions for Go.

slice slice is a simple Go package to provide generic versions of Map, Reduce and Filter on slices. I mainly wrote it as an exercise to get more famil

Andreas Krennmair 23 Sep 19, 2022
MapReduceGolang - Map Reduce with Golang

Map Reduce This demonstrates how map reduce can be run for a Synchronous path As

null 6 Feb 16, 2022
Timeboundmap - A Map data structure with expiration cleanup

timeboundmap A Map data structure with expiration cleanup Benchmark goos: darwin

null 2 Feb 23, 2022
Highly configurable struct to map converter.

Mapify Highly configurable struct to map converter. Will convert maps into other maps as well (work in progress). Features configuration outside the s

Jacek Olszak 2 Jul 30, 2022
safe and easy casting from one type to another in Go

cast Easy and safe casting from one type to another in Go Don’t Panic! ... Cast What is Cast? Cast is a library to convert between different go types

Steve Francia 2.5k Sep 25, 2022