数据结构求助

[wdc63]

当前项目有实现以下数据结构的需求： 1 大量的并行读取与修改； 2 支持在多线程情况下以 O1 或者极小的开销随机获取一个数据并删除（数据集为空时返回 null ，不报错。），插入一个数据。 3 基本上只有 2 一个需求，不需要顺序列表，不需要下标获取数据，不需要队列，不需要迭代器，无重复数据;

使用语言为 C#，目前测试使用 lock(List<T>)或者 Hashset 的开销都太大，使用 ConcurrentBag 、ConcurrentDictionary 都无法满足要求，请问各位大佬实现上述需求最佳的数据结构是什么。

[lmshl]

并行读取从来都不是问题，并行修改在哪里都是问题

建议重新思考读写模型，99%场景下并行修改都是可以避免的。比如把修改请求发送给数据结构持有者，Task<?> 接收修改结果，读取任意并发，写入排队。

[wdc63]

@lmshl 不能提交延迟修改。业务需求大致上是这样的：

数据集里的对象先称为服务，外部对象先称为代理。有上 W 个并行的代理向数据集请求可用的服务，随机提供一个给它，这个服务就被代理占用，然后这个服务就要从数据集移出，移入到正在接受服务的数据池，当服务完成后，服务可用，又从那边移出移入这边的可用服务数据池。如果提交延迟修改，就会发生多个代理被分配到同一个服务的错误。

[lmshl]

其实是可以做到的，你还没想明白。

看你描述完了整个流程以后，这不就是资源池么？要不你去看看（数据库，HTTP 链接池）资源池是怎么保证独占的？

[wdc63]

@lmshl 确实没想明白，大佬能不能提示一下。

[optional]

强一致性只能加锁，如果数据范围可以分区，尝试分区加锁

[lmshl]

简单来说，把普通 Dictionary 给 Pin 到一个线程上，建一个接收命令的并发队列，持续消费它。

设计两个函数：

Task<TakeResult> Take(...) { 将指令和 TaskCompletionSource 写入队列，返回 Task }
Task<SetResult> Set(...) { 将指令和 TaskCompletionSource 写入队列，返回 Task }

单线程持续消费并发队列，消费成功后 TaskCompletionSource::SetResult 告知调用者已经获取到



但是实际上你需要占有的是背后的服务，而不是这个 Dictionary 数据结构，那你没必要用线程安全的数据结构，直接把 lock/semaphore 加在 Dict Value 上不好么？

[cxe2v]

还有你为何要维护两个集合，在一个集合里给占用了的做个标记不好吗

[wdc63]

@lmshl 你的意思我懂了，我只需要 lock 被占用对象即可，如果这个对象被分配给另外一个请求者，可以先检查是否被 lock ，如果是就抛弃请求另一个。dict 多线程读取应该是安全的，但是没法获取随机元素。

[wdc63]

@cxe2v 我要从未占用的对象中随机获取一个，一个集合在性能上办不到吧。

[leonshaw]

@wdc63 看不出来这里会成为瓶颈，感觉你说的一个锁 + List 够了。建议先做 profiling.

[documentzhangx66]

1.性能与资源粒度是个矛盾。只考虑性能的话，可以按 NUMA 把资源进行平均划分，甚至可以给每个 CPU Thread 安排一个专有资源池，这样就避免了 CPU 竞争内存的问题，接着甚至可以把这部分专有资源池直接优化到 L3 cache 里去。这种优化的本质是空间换时间，会存在一定程度的资源浪费，比如某些不怎么干活的 CPU Thread ，它的专有资源池可能就不怎么使用。

2.如果存在避免不了竞争的资源区域，用 O1 的环形队列来代替 List 、Queue 等结构。这种优化的本质是极端的空间换时间，存在空间的大量浪费，但高端网络设备都这样搞。

[leonshaw]

#10 补充一下，删除的时候不要直接删，而是把最后一个换上来。

[visper]

为什么要随机,像池的话通常不是拿个空闲能用的就行了嘛

[wdc63]

@visper 不是一般的业务需求，是数理模型中的一部分，用服务池的概念只是一个举例，反正是必须要随机获取的，每个“服务”的属性都不一样。

[xuanbg]

你无论如何设计，他也只能是一个数组，无非就是要线程安全罢了。我记得 C#是有 ConcurrentBag 这么一个数据结构的，不明白为何不能满足 OP 的需求。

[fkdtz]

在共享字典的基础上，增加一个 pop 接口，返回一个元素并删除之。实现逻辑是随机删除，至于到底有多随机你可以慢慢调。

不知道 ConcurrentDictionary 是哪里不满足要求了。

[liuhan907]

@wdc63
如果你的使用过程不伴随异步的话，直接用 ThreadLocal 给每个线程分配一个池就好了。如果有异步。。。你都有异步了锁还不够用？

[wdc63]

@fkdtz 并行读写是一部分，ConcurrentDictionary 主要是不能实现随机获取。

[liyunlong41]

应该就是实现一个连接池吧，经典的实现方式就是 idle 和 busy 队列两个队列。另外为什么要随机呢，每次从 idle 队列头部 pop 一个连接放到 busy 就行，busy 用完了放到 idle 尾部排队，感觉也是比较公平的呀。

[wdc63]

@liyunlong41 数学模型要求实现随机获取，不是公平问题，这个项目是一个仿真项目，不是面向用户的真实业务项目。

[helloworld000]

你有多大的 qps ？ peak 的 read and write 分别是多少？脱离实际的需求都是瞎扯淡，你说的这些跟数据结构没半毛钱关系，完全是没想清楚问题在 yy

tldr 直接上个 redis 一把梭就行了

[netnr]

ConcurrentDictionary 获取所有 key 为数组再随机取一个，或者其它方式单独存储一份 key

[wdc63]

@helloworld000 高峰时，每个主 loop 有上千这样的查询、删除和写入等，每秒 60-100fps 。

[wdc63]

@netnr 那每次查询都是 On ，太慢了。

[masterjoess]

一个 fixed size array 存放所有对象
一个 atomic random queue 存放所有可用 index

标记软删除或者另外线程回收
这样可以吗?

[helloworld000]

@wdc63 就这点需求，redis 的 hash 就足够了