[技术方案讨论] 如何仅使用 set、get 操作实现一个锁?

2023-08-11 11:58:17 +08:00
 CC11001100

比如现在我们有一个服务,这个服务提供了两种操作:

op 想了几天了也没想清楚到底咋搞,目前隐约有的几种思路:

网上找到了几个类似的解决方案,但模拟演算了半天总感觉是有问题的:
localStorage 互斥锁的使用
fast-mutex

op 之前在论坛里发过几次帖子,难的 op 想跳河的问题大佬们都是随手点拨困难烟消云散,所以就寻思着来论坛里问问,看看大佬们有啥看法

BTW: 非公司业务非盈利相关,只是笔者自己学习折腾时的一些奇奇怪怪的想法拿出来和大家讨论一下

2418 次点击
所在节点    程序员
25 条回复
hsfzxjy
2023-08-11 12:37:05 +08:00
你得先说清楚:这两个操作是原子性的吗?
Akitora
2023-08-11 12:45:23 +08:00
除非 get+判断+set 能一起原子执行,就像 redis 的 setnx
hxysnail
2023-08-11 13:14:16 +08:00
你需要一个 cas 操作:compare_and_set
krapnik
2023-08-11 13:17:31 +08:00
chesha1
2023-08-11 13:18:47 +08:00
如果你只有这两个指令是无法实现锁的,至少我不知道咋实现

最简单版本的锁需要一个,可以查看值并设置值,的原子指令支持

比如 tets-and-set ,compare-and-swap ,不同硬件平台有这两个指令的支持
CC11001100
2023-08-11 13:24:05 +08:00
@hsfzxjy 这两个操作本身是原子性的
CC11001100
2023-08-11 13:25:21 +08:00
@Akitora 是的,如果有已经存在的原子、互斥操作的话可以基于这个操作很方便扩展出来锁
ysc3839
2023-08-11 13:27:18 +08:00
CC11001100
2023-08-11 13:31:37 +08:00
@hxysnail @chesha1 @krapnik 是的我之前跟朋友讨论的时候也突然领悟到一个点当时还跟他说来着,上面帖子描述没说是因为我也不知道悟得对不对,就是所谓的锁其实就是在某个互斥特性的基础上施加一些操作构造出来更复杂的操作,但是基础是必须要有一个互斥特性否则就没办法构造出锁,锁不能凭空生成必须要有互斥基础,锁或者分布式锁也只是对互斥特性的作用域进行放大,其本质特性还是最底下的那一个互斥特性
CC11001100
2023-08-11 13:33:04 +08:00
@CC11001100 互斥特性比如 CAS 、比如某个 mutex 变量之类的
CC11001100
2023-08-11 13:35:25 +08:00
@CC11001100 如果上面这个论述是成立的,那靠 set 和 get 似乎是真的不能构造出锁,怎么组合也不行,毕竟无法凭空产生互斥特性,这就令人沮丧了毕竟我都琢磨了好几天了。。。o(╥﹏╥)o
Masoud2023
2023-08-11 13:37:54 +08:00
为什么只能有这两个?架构设计是不是有问题?

即使能做出来,这种违反常理的东西真的 ok 吗?
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)
chesha1
2023-08-11 14:03:56 +08:00
@CC11001100 我感觉说的没错,锁发明出来就是为了防止别的线程乱搞,只能让这一条线程执行某一块区域,互斥性质是基本属性
其他的公平性和性能,是其次要考虑的问题,比如防止死锁,或者一直自旋之类的

老哥是不是工作好久了,可以复习一下操作系统的书,这些问题书里都讲得很清楚的
Kumo31
2023-08-11 14:10:27 +08:00
是可以实现的,OSTEP 书里提到过 Peterson 算法,是早期操作系统没有硬件支持( tas,cas 等指令)时纯软件实现的锁,只需要 load 和 store 两个操作是原子的即可
silencil
2023-08-11 14:17:30 +08:00
锁的原理:一个状态+一个设置状态的操作+一个读取状态的操作。设置状态的操作需要是原子性的。其他的队列、自旋都是你实现线程管理的方案,能满足上面所说的就能实现一把简单的锁,再去拓展考虑其他。
CC11001100
2023-08-11 14:18:18 +08:00
@chesha1 惭愧工作多年很多基础的东西还是不太清楚,书上的东西老是领悟不透彻时常踩坑摸索。

直接看帖子是会觉得这是奇奇怪怪的想法哈哈哈,这件事的来龙去脉是这样,去年底的时候 op 参与过某个 client 端的项目,里面有个业务点是会涉及到多个角色用纯 client 端软件协同操作数据库,当时负责这块的同事没处理到这种并发情况出了几次事故,op 插进来紧急救火撸了个基于 postgresql 数据库的分布式锁,当时是以 Redis 的分布式的思路为基础修改出了 postgresql 的分布式锁,从那就开始业余时间偶尔关注这块。

后来又想这个能不能推广开来,然后就实现了通用的关系型数据库分布式锁。

再后来又想,一定要是关系型数据库吗? kv 数据库呢?当时关系型数据库的通用的锁是使用基于 CAS 的带版本的乐观锁实现的,但是如果是 kv 数据库的话就只有 set/get 操作没想明白,于是就有了这篇帖子。。。
CC11001100
2023-08-11 14:21:28 +08:00
@Kumo31 老哥牛皮,看描述感觉这个就是我苦苦寻找的算法,给跪了我去搜搜资料学习学习,非常感谢!
aminobody
2023-08-11 14:23:51 +08:00
实现锁需要 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]。
nothingistrue
2023-08-11 14:29:44 +08:00
你首先要搞清楚你的原子操作是什么,看你得场景,猜测是“读取—bulabula—写回”这个过程做成原子的。那么你只能在这个原子过程上加锁。是不能在 set get ,原子过程的内部片段上,去做锁的。你需要做的是,在 set 、get 方法之外,另行提供 setAndBulabula 、bulabulaAndGet 方法。

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/964395

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX