并发大量读取工作负载的数据结构

我正在寻找一种存储32bytes字符串并允许使用首选O(1)或O进行快速查找的数据结构 (日志N)查找复杂度(目的只是确定密钥是否存在)。 删除和插入的复杂性并不重要,因为这些操作很少发生。</ p>

这与问题无关,但我正在Go中工作。 我可以使用由互斥锁支持的 hashmap </ em>,但是争用会成为问题,如果有更好的解决方案,我宁愿避免使用分片。</ p>

谢谢< / p>
</ div>

展开原文

原文

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

douwa1304
douwa1304 我们在这里每秒说话多少次?总钥匙数是多少?您说删除和插入很少。多不频繁?在我看来,像是一个哈希表和一个读/写锁将对您非常有效。见stackoverflow.com/questions/19148809/…
接近 3 年之前 回复
donglei_0507
donglei_0507 hasmap软件包可以满足您的需求。
接近 3 年之前 回复
dongrao9436
dongrao9436 您是否使用RWMutex对map[string]struct{}进行了基准测试?
接近 3 年之前 回复

1个回答



map </ code>对于同时读取是安全的。 您可以将所需的地图放入 sync / atomic.Value </ code>中,并在要写入时将其复制并更改地图,然后将其放回 Value </ code>中。 来自文档:</ p>


< p>以下示例说明了如何使用写时复制
惯用法来维护可伸缩的,经常读取但不经常更新的数据结构。</ p>

代码:</ p>

 类型Map map [string] string 
var m值
m.Store(make(Map))
var mu sync.Mutex //仅由编写者使用
//可以使用读取功能 无需进一步同步即可读取数据
read:= func(key string)(val string){
m1:= m.Load()。(Map)
return m1 [key]
}
//插入 函数可用于更新数据而无需进一步同步
insert:= func(key,val string){
mu.Lock()//与其他潜在的编写者同步
延迟mu.Unlock()
m1:= m.Load()。(Map)//加载数据结构的当前值
m2:= make(Map)//为k创建新值
,v:=范围m1 {
m2 [k] = v //从 当前对象到新对象
}
m2 [key] = val //完成我们需要的更新
m.Store(m2)//用新对象原子替换当前对象
// 指向所有新阅读器开始使用新版本。
//现有阅读器完成后,旧版本将被垃圾收集
//(如果有)完成。
}
=读取,插入
</ code> </ pre>
</ blockquote>

您也可以使用指向 map </ code>的指针代替 Value </ code>和 使用 StorePointer / LoadPointer 原子存储它,但这并不是更干净的原因,因为您应该使用不安全的 指针并对其进行投射。</ p>
</ div>

展开原文

原文

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.

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐