假设一个 TODO 应用需要展示一组任务(Task), 任务从属于一个清单(List).

每个清单下的任务展示必然带来一个需求: 排序

固定排序

简单做法是软件提供多种预定义的排序规则. 比如 按照创建实际降序排; 按照截止时间降序排.

自定义排序

固定排序实现简单, 但不一定符合用户灵活的场景. 自定义排序的能力能够让用户拥有更大的自由度.

为了记录排序信息, 实践中存在几种方案:

排序信息记录在清单上

// List Item
{
  "tasks": [task1, task3, task2]
}

清单上使用数组类型字段记录了任务的顺序.

数据模型通俗易懂. 需要调整顺序时告诉服务端需要放到指定任务之后即可.

这个方案存在几个问题:

  1. 任务删除需要跟新tasks字段, 不然就会存在无效数据;
  2. 新增任务需要自动加入到tasks字段, 不然就会无新任务的排序信息;
  3. 清单下任务数增加时会导致tasks信息过大; (mongodb 会限制一个 Document 的大小)
  4. 任务跨清单移动需要更改两个清单的tasks字段;
  5. 由于清单的tasks严重依赖与任务, 复制清单的操作必须先复制任务;
  6. 批量的任务创建/删除 会带来更多的tasks数据更新问题(数组更新不够原子atomic)

总结: 任何可能导致排序变化的场景都要更新tasks字段; 高并发时很容易导致数据不一致(tasks记录的信息与实际清单下的任务数不一致);

排序信息记录在任务上: 链表式

// Task Item
{
	prevTask: task2 // 记录前一个任务信息
}

经典的链表结构. 根据prevTask构建完链表即完成排序.

链表的问题是不能断, 在排序变化时需要慎重更新相关任务的prevTask, 避免短链:

  1. 新增/删除任务等价于链表节点插入;
  2. 任务移动到其他清单等价于链表节点删除+链表节点插入;
  3. 清单复制必须依据链表顺序逐个复制, 严重影响复制效率;
  4. 高并发插入容易造成链表断链(链表节点插入非原子);

排序信息记录在任务上: 位置信息

之前在知乎上有个简单的介绍: teambition的任务卡排序，数据是怎么存储的？ - 知乎

// Task Item
{
  pos: 12345 // 记录任务的相对位置
}

整个排序按照pos值升序.

为了确保在两个任务间插入新任务时有可用的pos取值范围, 期望任意两个相邻任务的pos差值尽可能大, 但又不能太大(最大利用int32/int64取值范围以记录更多的任务排序信息)

缺点:

  1. 两个任务间同时/批量插入一个任务则会导致最终两个新任务 pos 值相同;
  2. 用户使用过程中会导致两个任务pos差值不足以容纳新的任务, 需要重排整个清单, 重排期间的任务写入也会带来风险;
api