[技术方案讨论] 如何仅使用 set、get 操作实现一个锁？
CC11001100 · CC11001100 · 2023-08-11 11:58:17 +08:00 · 2417 次点击这是一个创建于 468 天前的主题，其中的信息可能已经有所发展或是发生改变。
比如现在我们有一个服务，这个服务提供了两种操作：
- set(key string)
- get(key string) string 有没有办法仅基于这两种操作构造出来一个锁？
op 想了几天了也没想清楚到底咋搞，目前隐约有的几种思路：
- 使用多个 key 看看能不能组合出来
- 给 key 加版本号看能不能组合出来
- 没了...
网上找到了几个类似的解决方案，但模拟演算了半天总感觉是有问题的：
localStorage 互斥锁的使用
fast-mutex
op 之前在论坛里发过几次帖子，难的 op 想跳河的问题大佬们都是随手点拨困难烟消云散，所以就寻思着来论坛里问问，看看大佬们有啥看法
BTW: 非公司业务非盈利相关，只是笔者自己学习折腾时的一些奇奇怪怪的想法拿出来和大家讨论一下
 |
1
hsfzxjy 2023-08-11 12:37:05 +08:00 via Android
你得先说清楚：这两个操作是原子性的吗？
|
 |
2
Akitora 2023-08-11 12:45:23 +08:00  1
除非 get+判断+set 能一起原子执行，就像 redis 的 setnx
|
 |
3
hxysnail 2023-08-11 13:14:16 +08:00
你需要一个 cas 操作：compare_and_set
|
 |
4
krapnik 2023-08-11 13:17:31 +08:00
|
 |
5
chesha1 2023-08-11 13:18:47 +08:00
如果你只有这两个指令是无法实现锁的，至少我不知道咋实现
最简单版本的锁需要一个，可以查看值并设置值，的原子指令支持 比如 tets-and-set ，compare-and-swap ，不同硬件平台有这两个指令的支持 |
 |
6
CC11001100 OP @hsfzxjy 这两个操作本身是原子性的
|
|
7
CC11001100 OP @Akitora 是的，如果有已经存在的原子、互斥操作的话可以基于这个操作很方便扩展出来锁
|
 |
8
ysc3839 2023-08-11 13:27:18 +08:00 via Android
@Akitora @hxysnail @chesha1
应该只需要有原子的 exchange ，参见 boost 的 spinlock https://www.boost.org/doc/libs/1_82_0/libs/atomic/doc/html/atomic/usage_examples.html#boost_atomic.usage_examples.example_spinlock.implementation |
|
9
CC11001100 OP |
|
10
CC11001100 OP @CC11001100 互斥特性比如 CAS 、比如某个 mutex 变量之类的
|
|
11
CC11001100 OP @CC11001100 如果上面这个论述是成立的，那靠 set 和 get 似乎是真的不能构造出锁，怎么组合也不行，毕竟无法凭空产生互斥特性，这就令人沮丧了毕竟我都琢磨了好几天了。。。o(╥﹏╥)o
|
 |
12
Masoud2023 2023-08-11 13:37:54 +08:00 1
为什么只能有这两个？架构设计是不是有问题？
即使能做出来，这种违反常理的东西真的 ok 吗？ |
|
13
chesha1 2023-08-11 13:57:28 +08:00
@ysc3839 如果我没理解错的话，因为这里的 state_因为是枚举类型，所以隐藏了另一个输入参数，实际上还是 compare-and-swap ，只是隐藏了 compare 的对象，看上去没有 compare
比较通用的 compare-and-swap 是： int CompareAndSwap(int *ptr, int expected, int new) boost 这里是： state_.exchange(Locked, boost::memory_order_acquire) 实际上等于 exchange(state_, unlocked, locked) |
|
14
chesha1 2023-08-11 14:03:56 +08:00
@CC11001100 我感觉说的没错，锁发明出来就是为了防止别的线程乱搞，只能让这一条线程执行某一块区域，互斥性质是基本属性
其他的公平性和性能，是其次要考虑的问题，比如防止死锁，或者一直自旋之类的 老哥是不是工作好久了，可以复习一下操作系统的书，这些问题书里都讲得很清楚的 |
 |
15
Kumo31 2023-08-11 14:10:27 +08:00 4
是可以实现的，OSTEP 书里提到过 Peterson 算法，是早期操作系统没有硬件支持（ tas,cas 等指令）时纯软件实现的锁，只需要 load 和 store 两个操作是原子的即可
|
 |
16
silencil 2023-08-11 14:17:30 +08:00
锁的原理：一个状态+一个设置状态的操作+一个读取状态的操作。设置状态的操作需要是原子性的。其他的队列、自旋都是你实现线程管理的方案，能满足上面所说的就能实现一把简单的锁，再去拓展考虑其他。
|
|
17
CC11001100 OP @chesha1 惭愧工作多年很多基础的东西还是不太清楚，书上的东西老是领悟不透彻时常踩坑摸索。
直接看帖子是会觉得这是奇奇怪怪的想法哈哈哈，这件事的来龙去脉是这样，去年底的时候 op 参与过某个 client 端的项目，里面有个业务点是会涉及到多个角色用纯 client 端软件协同操作数据库，当时负责这块的同事没处理到这种并发情况出了几次事故，op 插进来紧急救火撸了个基于 postgresql 数据库的分布式锁，当时是以 Redis 的分布式的思路为基础修改出了 postgresql 的分布式锁，从那就开始业余时间偶尔关注这块。 后来又想这个能不能推广开来，然后就实现了通用的关系型数据库分布式锁。 再后来又想，一定要是关系型数据库吗？ kv 数据库呢？当时关系型数据库的通用的锁是使用基于 CAS 的带版本的乐观锁实现的，但是如果是 kv 数据库的话就只有 set/get 操作没想明白，于是就有了这篇帖子。。。 |
|
18
CC11001100 OP @Kumo31 老哥牛皮，看描述感觉这个就是我苦苦寻找的算法，给跪了我去搜搜资料学习学习，非常感谢！
|
 |
19
aminobody 2023-08-11 14:23:51 +08:00 1
实现锁需要 read–modify–write 操作，比如 cas 。
但还有一种和 cas 等价的操作叫 (load-linked/store-conditional)[https://en.wikipedia.org/wiki/Load-link/store-conditional] ，使用 ll/sc 两条指令实现和 cas 一条指令同样的效果，你可以参考下。 只有 atomic 的 r 和 w ，应该是无法构建一把通用的锁。但是，当并发数只有 2 的时候，则是可以的，参考（ Peterson 算法）[https://en.wikipedia.org/wiki/Peterson%27s_algorithm]。 |
 |
20
nothingistrue 2023-08-11 14:29:44 +08:00
你首先要搞清楚你的原子操作是什么，看你得场景，猜测是“读取—bulabula—写回”这个过程做成原子的。那么你只能在这个原子过程上加锁。是不能在 set get ，原子过程的内部片段上，去做锁的。你需要做的是，在 set 、get 方法之外，另行提供 setAndBulabula 、bulabulaAndGet 方法。
|
 |
21
yinfeng 2023-08-11 15:27:24 +08:00 6
这是非常经典的计科问题，使用任意多个，有读和写方法的，顺序一致的，原子寄存器实现互斥锁。
简单看了下 fast-mutex 用的算法，它试图用两个 SC 的原子寄存器去实现 n 个线程的互斥，假设了一个线程的延迟执行一定能使其他线程执行完 lock 的代码。问题就是如果无视这个假设很容易就能构造反例。 如果非要去做这样的事，有挺多算法可以选择，只是都很慢。最经典的就是，两线程可以用 Peterson lock ，Peterson lock 可以推广到 n 个线程叫作 filter lock ，还有具有公平性的 bakery 算法。 https://en.wikipedia.org/wiki/Peterson%27s_algorithm https://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm |
 |
22
Mistwave 2023-08-11 15:32:25 +08:00 via iPhone
|
|
23
ysc3839 2023-08-11 15:38:35 +08:00 via Android
@chesha1 exchange 实际上不会有 compare 操作，就只是交换值。只有多状态的锁(比如读写锁)才需要 compare exchange 操作。
|
|
24
chesha1 2023-08-11 15:57:33 +08:00
@ysc3839 还真是，我又仔细看了一眼，是我自己想错了
spin 条件判断调用了一个通用的 boost::atomic 的 exchange 方法，肯定跟模板参数的属性没关系 |
 |
25
nuk 2023-08-28 03:55:59 +08:00
老哥可以看看这本书《多处理器编程的艺术》
|
Select Language