Data-structure for concurent heavy read workload

Question

I am looking for a data-structure that stores 32bytes strings and allows fast lookups with preferred O(1) or O(log N) lookup complexity (the goal is only to determine if the key exists). Removal and insertion complexity is not critical, since those operations will be infrequent.

Not that it is relevant to the question, but i am working in Go. I could use a hashmap backed by a mutex, but contention would be a problem, and I prefer to avoid sharding if there is a better solution.

Thanks

Have you benchmarked a `map[string]struct{}` with an [`RWMutex`](https://godoc.org/sync#RWMutex)? — , Dec 31 '17 at 03:12
[This hasmap package](https://github.com/cornelk/hashmap) could fit your needs. — bigless, Dec 31 '17 at 03:45
How many lookups per second are we talking here? How many total keys? You say that removal and insertion are infrequent. How infrequent? It sounds to me like a hashmap and a reader/writer lock will be very effective for you. See https://stackoverflow.com/questions/19148809/how-to-use-rwmutex-in-golang — Jim Mischel, Dec 31 '17 at 14:41

Arman Ordookhani · Answer 1 · 2017-12-31T08:28:09.293

map is safe for concurrent read. You could put your desired map inside a sync/atomic.Value and when you want to write to it, duplicate the map and change it, then put it back inside Value. From docs:

The following example shows how to maintain a scalable frequently read, but infrequently updated data structure using copy-on-write idiom.

Code:

type Map map[string]string
var m Value
m.Store(make(Map))
var mu sync.Mutex // used only by writers
// read function can be used to read the data without further synchronization
read := func(key string) (val string) {
        m1 := m.Load().(Map)
        return m1[key]
}
// insert function can be used to update the data without further synchronization
insert := func(key, val string) {
        mu.Lock() // synchronize with other potential writers
        defer mu.Unlock()
        m1 := m.Load().(Map) // load current value of the data structure
        m2 := make(Map)      // create a new value
        for k, v := range m1 {
                m2[k] = v // copy all data from the current object to the new one
        }
        m2[key] = val // do the update that we need
        m.Store(m2)   // atomically replace the current object with the new one
        // At this point all new readers start working with the new version.
        // The old version will be garbage collected once the existing readers
        // (if any) are done with it.
}
_, _ = read, insert

You could also use a pointer to you map instead of Value and store it atomically using StorePointer/LoadPointer but that's not cleaner cause you should use an unsafe pointer and cast it.

Data-structure for concurent heavy read workload

1 Answers1