这是一个创建于 768 天前的主题，其中的信息可能已经有所发展或是发生改变。
当前项目有实现以下数据结构的需求： 1 大量的并行读取与修改； 2 支持在多线程情况下以 O1 或者极小的开销随机获取一个数据并删除（数据集为空时返回 null ，不报错。），插入一个数据。 3 基本上只有 2 一个需求，不需要顺序列表，不需要下标获取数据，不需要队列，不需要迭代器，无重复数据;
使用语言为 C#，目前测试使用 lock(List<T>)或者 Hashset 的开销都太大，使用 ConcurrentBag 、ConcurrentDictionary 都无法满足要求，请问各位大佬实现上述需求最佳的数据结构是什么。
 |
1
lmshl 2022-10-08 14:55:21 +08:00
并行读取从来都不是问题，并行修改在哪里都是问题
建议重新思考读写模型，99%场景下并行修改都是可以避免的。比如把修改请求发送给数据结构持有者，Task<?> 接收修改结果，读取任意并发，写入排队。 |
 |
2
wdc63 OP @lmshl 不能提交延迟修改。业务需求大致上是这样的：
数据集里的对象先称为服务，外部对象先称为代理。有上 W 个并行的代理向数据集请求可用的服务，随机提供一个给它，这个服务就被代理占用，然后这个服务就要从数据集移出，移入到正在接受服务的数据池，当服务完成后，服务可用，又从那边移出移入这边的可用服务数据池。如果提交延迟修改，就会发生多个代理被分配到同一个服务的错误。 |
|
3
lmshl 2022-10-08 15:06:32 +08:00  1
其实是可以做到的，你还没想明白。
看你描述完了整个流程以后，这不就是资源池么？要不你去看看（数据库，HTTP 链接池）资源池是怎么保证独占的？ |
 |
5
optional 2022-10-08 15:11:35 +08:00 via iPhone
强一致性只能加锁，如果数据范围可以分区，尝试分区加锁
|
|
6
lmshl 2022-10-08 15:27:45 +08:00
简单来说，把普通 Dictionary 给 Pin 到一个线程上，建一个接收命令的并发队列，持续消费它。
设计两个函数： Task<TakeResult> Take(...) { 将指令和 TaskCompletionSource 写入队列，返回 Task } Task<SetResult> Set(...) { 将指令和 TaskCompletionSource 写入队列，返回 Task } 单线程持续消费并发队列，消费成功后 TaskCompletionSource::SetResult 告知调用者已经获取到 但是实际上你需要占有的是背后的服务，而不是这个 Dictionary 数据结构，那你没必要用线程安全的数据结构，直接把 lock/semaphore 加在 Dict Value 上不好么？ |
 |
7
cxe2v 2022-10-08 15:42:49 +08:00
还有你为何要维护两个集合，在一个集合里给占用了的做个标记不好吗
|
|
8
wdc63 OP @lmshl 你的意思我懂了，我只需要 lock 被占用对象即可，如果这个对象被分配给另外一个请求者，可以先检查是否被 lock ，如果是就抛弃请求另一个。dict 多线程读取应该是安全的，但是没法获取随机元素。
|
 |
11
documentzhangx66 2022-10-08 16:12:15 +08:00
1.性能与资源粒度是个矛盾。只考虑性能的话，可以按 NUMA 把资源进行平均划分，甚至可以给每个 CPU Thread 安排一个专有资源池，这样就避免了 CPU 竞争内存的问题，接着甚至可以把这部分专有资源池直接优化到 L3 cache 里去。这种优化的本质是空间换时间，会存在一定程度的资源浪费，比如某些不怎么干活的 CPU Thread ，它的专有资源池可能就不怎么使用。
2.如果存在避免不了竞争的资源区域，用 O1 的环形队列来代替 List 、Queue 等结构。这种优化的本质是极端的空间换时间，存在空间的大量浪费，但高端网络设备都这样搞。 |
 |
12
leonshaw 2022-10-08 16:16:22 +08:00
#10 补充一下，删除的时候不要直接删，而是把最后一个换上来。
|
 |
13
visper 2022-10-08 16:20:39 +08:00
为什么要随机,像池的话通常不是拿个空闲能用的就行了嘛
|
|
14
wdc63 OP @visper 不是一般的业务需求，是数理模型中的一部分，用服务池的概念只是一个举例，反正是必须要随机获取的，每个“服务”的属性都不一样。
|
 |
15
xuanbg 2022-10-08 17:41:14 +08:00
你无论如何设计，他也只能是一个数组，无非就是要线程安全罢了。我记得 C#是有 ConcurrentBag 这么一个数据结构的，不明白为何不能满足 OP 的需求。
|
 |
16
fkdtz 2022-10-08 17:50:48 +08:00
在共享字典的基础上，增加一个 pop 接口，返回一个元素并删除之。实现逻辑是随机删除，至于到底有多随机你可以慢慢调。
不知道 ConcurrentDictionary 是哪里不满足要求了。 |
 |
17
liuhan907 2022-10-08 19:32:46 +08:00
@wdc63
如果你的使用过程不伴随异步的话，直接用 ThreadLocal 给每个线程分配一个池就好了。如果有异步。。。你都有异步了锁还不够用？ |
|
18
wdc63 OP @fkdtz 并行读写是一部分，ConcurrentDictionary 主要是不能实现随机获取。
|
 |
19
liyunlong41 2022-10-08 23:00:31 +08:00 via iPhone
应该就是实现一个连接池吧，经典的实现方式就是 idle 和 busy 队列两个队列。另外为什么要随机呢，每次从 idle 队列头部 pop 一个连接放到 busy 就行，busy 用完了放到 idle 尾部排队，感觉也是比较公平的呀。
|
|
20
wdc63 OP @liyunlong41 数学模型要求实现随机获取，不是公平问题，这个项目是一个仿真项目，不是面向用户的真实业务项目。
|
 |
21
helloworld000 2022-10-09 06:43:57 +08:00
你有多大的 qps ？ peak 的 read and write 分别是多少？脱离实际的需求都是瞎扯淡，你说的这些跟数据结构没半毛钱关系，完全是没想清楚问题在 yy
tldr 直接上个 redis 一把梭就行了 |
 |
22
netnr 2022-10-09 08:36:44 +08:00 via Android
ConcurrentDictionary 获取所有 key 为数组再随机取一个，或者其它方式单独存储一份 key
|
|
23
wdc63 OP @helloworld000 高峰时，每个主 loop 有上千这样的查询、删除和写入等，每秒 60-100fps 。
|
 |
25
masterjoess 2022-10-09 10:29:34 +08:00
一个 fixed size array 存放所有对象
一个 atomic random queue 存放所有可用 index 标记软删除或者另外线程回收 这样可以吗? |
|
26
helloworld000 2022-10-09 18:43:47 +08:00
@wdc63 就这点需求，redis 的 hash 就足够了
|
Select Language