如何原子性的重排某个队列

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 4905 天前的主题，其中的信息可能已经有所发展或是发生改变。

某需求，当前存在一个有序队列，要求可以原子性的增加、删除、重排列表中的元素。并且队列的内容是通过Web来管理和交互的。
有没有什么很好的解决方案？目前存储和算法都没定，只是打算用Python实现。
用锁和优先级的话，由于多用户访问时，可能出现以下情况导致原子性丧失：
1、A用户打开页面
2、B用户打开页面
3、A用户添加了一个元素，并提交（此时这个修改并没有反馈到B用户那里去）
4、B用户重排了列表。此时会有冲突，用优先级来实现的话，必然可能出现重排后的原始列表中的某项和后添加的那个元素优先级冲突，造成逻辑丧失。
不知道除了优先级和锁的方法，还有什么比较好的实现？

优先级

重排

用户

15 条回复 • 1970-01-01 08:00:00 +08:00

aligo

2011-06-07 20:37:20 +08:00

（此时这个修改并没有反馈到B用户那里去）

你自己已经知道问题所在了，如果是在线协同作业的话，利用各种polling方式更新客户端就好了

ssword

2011-06-07 20:39:04 +08:00

"原子性"是指时间周期内不可分割的操作，跟单纯保证并发的正确性不是一回事。看楼主的描述似乎更像是强调实时更新，而不是强调并发。
不大懂“优先级和锁”是怎样的方法，不过仅仅要求数据一致性的话，一般的DBMS都有事务功能可以用。

ayanamist

2011-06-07 20:41:29 +08:00

@aligo poll很浪费资源啊……毕竟这种数据碰撞的情况比较少……

ayanamist

2011-06-07 20:42:09 +08:00

@ssword 不需要实时更新。我想描述的是解决数据碰撞的问题。除了用poll，还有什么办法能解决我描述的那个问题吗？

ssword

2011-06-07 20:49:14 +08:00

@ayanamist 大致明白了，这问题跟原子性无关。
可以这样：每个列表对应一个表单，里面带一个版本号。每次新提交都让版本号+1，如果一个新提交的版本号不是最新，简单地回复给用户一个错误就行。

ayanamist

2011-06-07 20:59:33 +08:00

@ssword 你这太粗暴了……我需要的是平和处理……我刚想到vcs一定会遇到这个问题，两个人co以后，做了不同的修改，同时commit，会发生什么？

ssword

2011-06-07 21:04:53 +08:00

@ayanamist 等解决好这个和平问题，git/svn即可退出历史舞台

reus

2011-06-07 21:22:00 +08:00

貌似这种情况是先要update一下再commit的，如果可以自动合并就合并，commit成功。不能的话，要你自己解决冲突。
所以可以在提交之前更新一下状态并提示用户。
其实我好奇这是啥功能呢？

ayanamist

2011-06-07 21:51:38 +08:00

@reus @ssword 研究了一下git，确实需要人工干预。
想了想，也许只有用户每次操作（包括重排时的每次改变单个元素的顺序）的时候ajax提交，然后服务器用版本号判断，如果版本号不匹配，就放弃此次操作，并返回最新版本的数据比较妥当

reus

2011-06-07 22:28:14 +08:00

我还是好奇这是个啥东西，具体说说吧？或者有其他的解决方法也说不定的啊，不一定要用同步的方式。比如可以用branch+merge的模型

lepture

2011-06-08 00:21:07 +08:00

一定要同时操作的么？
如果A进入了该资源的修改状态，则其它人不可修改，这样子不行么？

dreampuf

2011-06-08 02:52:18 +08:00 via Android

时间戳

nleven

2011-06-08 03:12:12 +08:00

把重排放到服务端去做就好了吧。
B不要把新列表的具体内容传给服务器，只是告诉它去重排。服务端显然总是有最新的列表，让它去重排的话就根本不会冲突了。

aligo

2011-06-09 08:09:20 +08:00

@ayanamist 其实是各种polling，例如long-polling
或者最简单的一个办法如你上面说的，像各种版本管理系统，给每次的变更提供一个hash，A用户添加了东西之后，就改变了那个hash
而B用户客户端的排列的还是原来的hash，B用户在提交的时候就会遇到hash冲突，这时候再更新B眼中的内容，让他解决冲突然后提交好了

aligo

2011-06-09 08:11:45 +08:00

我做过的大家也都做过的类似的应用场景
就是在注册一个用户的时候，输入用户名会检查一遍有没有重复的用户名
最后用户确认提交的时候再一次的检测同时添加数据

darasion

2011-06-09 08:16:53 +08:00

恰好我也正在做这种事情。发现式设计起来很麻烦，现在还在头疼中。

还涉及到工作流什么什么的，更麻烦了。两边都要有解决冲突的机制。

郁闷啊。