ReactiveDB/core

Optimistic Updates

Brooooooklyn opened this issue · 18 comments

Brooooooklyn commented

Note

今天突然想到一个问题。
假设某个时间点数据版本是 1
然后乐观更新，数据版本变成 2
而 Socket 或者其它东西导致数据再次更新到了版本 3
这种时候数据可能会进入到一个无法回滚的状态（无法从 2 -> 1 -> 3，因为在一次 revert 中无法获取另一次数据更新的中间状态，除非在乐观更新的时候同时 observe 需要乐观更新的数据？？？？）

所以是不是应该在乐观更新期间做一个表锁？
@Saviio @Miloas @chuan6

Saviio commented

所以我给出的方案就是不做真实写，如果 2 需要回滚，那么在action 2 被cancel掉之后，就做1 -> 3的写，因为操作一定是有序的

锁在这里是解决不了问题的，因为会严重迟滞数据的真实变化，而你说的问题本质上来说你需要一个MVCC :p，也就是我在原issue里说的『必须有数据整行快照』

Brooooooklyn commented

我主要是担心在数据库外部做非真实写会带来额外的复杂性。比如乐观更新的东西涉及到跨表的好几个数据，那么在表外要维护的数据结构会不会过于复杂？

Saviio commented

以我的经验来说，这个解决方案你做了真实写，复杂度才会是真的高，因为你要额外设计很多机制来保证lf里存储的数据的『正确性』。

乐观更新的一个性质就是:
pending 的数据 lifecycle 会很短(相对前端而言，基本上就是一次通讯的 round trip (300ms)，真实环境取决于API响应速度)，所以我们可以利用这个特性来尝试提供工程上的解决方案。

Brooooooklyn commented

首先，乐观更新 lifecycle 短并不会降低问题的复杂性，各种 case 依旧会出现在短的 lifecycle 中。(比如 socket back pressure 会导致一次推送里面携带 N 条数据更新)，不认为在这样的场景下工程上的设计会比理论上解决问题的设计简单。
其次，我昨天仔细看了下你在 teambition/ReactiveDB#91 中的描述:

我的想法上面已经给出了，所有的查询在从get接口输出的时候自动combineLatest OptimisticCache, 并且尝试封装出一层 filter 的逻辑，然后就可以根据 action type 从 db 里的资源过滤掉那些已经乐观删除的资源了？

其中如果是 get 的时候 combineLatest OptimisticCache ，这意味着

  • OptimisticCache 需要维护目前所有正在乐观更新的所有数据副本，并且这些数据副本还需要 observe 住，来保证新的数据版本更新到来之后，数据的更新顺序是按 old -> optimistic -> new -> result 的顺序进行更新的。或者是乐观更新失败后按照 old -> new -> result 的顺序进行更新。
  • 上面一点都只需要用额外的性能开销来交换，并不会带来设计上的额外复杂性。但还有一点就是: 当消费者正在使用一个带有 pagination，复杂 predicate 的 QueryToken，optimistic 导致的数据变动对 QueryToken 的变更还需要在 OptimisticCache 中再次计算一次。比如有一个 Query 是查询:
Task: 
{
  dueDate: {
    $gte: new Date('2017-02-01').valueOf()
  }
}

Optimistic 其中一条数据的 dueDate 如何保证对这个查询的影响结果是正确的(在不真实写入 db 的情况下)

Saviio commented

乐观更新 lifecycle 短，这一点我是基于我们可以做出一些略微损失性能的方案，来尝试降低复杂性提出的。

socket back pressure 这个问题，只要是一条socket，那么可以merge到一个patch action里重放，那即使是多条数据，由于之前我提到的乐观更新的lifecycle短，可能造成的性能损失应该也是有限的。

其实，

Task: 
{
  dueDate: {
    $gte: new Date('2017-02-01').valueOf()
  }
}

这个场景是能解决的，因为匹配的策略不同，query是按condition去匹配的，而OptimisticCache是按id匹配的，唯一不好处理的，假设某一个 query 是查询某一个表的update字段，由于不做真实写，update字段的影响无法即时生效。

OptimisticCache 里我不打算维护数据副本，我只打算维护action，因为如果我要维护数据副本，这个方案就没有任何意义了。

另外，基于做真实写我也有个想法，但得容再思考一下....这周太忙，不一定能及时回了

Brooooooklyn commented

嗯，我指的就是 query 查询某个 update 字段，update 字段无法即时生效的问题不好解决，因为 OptimisticCache 不好实现 predicate 的计算。

比如在 我的任务 页面，修改一个任务的执行者，使用乐观更新策略。
那么这条任务如何从所属的列表中及时消失掉。

Brooooooklyn commented

Revert API Proposal

Introduce new RevertController Class:

class RevertController {
  static create(): RevertController
  static getToken(identify: Symbol): RevertController
  // disable new
  private constructor(): void
  toToken(): Symbol
  revert(): Promise<ExecutorResult> // hot and not cancelable
  commit(): void
}

Extend Database#update/#upsert/#delete/#insert

insert<T>(tableName: string, raw: T | T[], controller?: RevertController): Observable<ExecutorResult>

update<T>(tableName: string, clause: Predicate<T>, raw: Partial<T>, controller?: RevertController): Observable<ExecutorResult>

// clause must be specified when passed a RevertController
delete<T>(tableName: string, clause: Predicate<T> = {}, controller?: RevertController): Observable<ExecutorResult>

upsert<T>(tableName: string, raw: T | T[], controller?: RevertController): Observable<ExecutorResult>

Usage:

const revertController = RevertController.create()
const  executor = Database.upsert('Task', {
  _id: 'xxxxxx',
  dueDate: new Date().toISOString()
}, revertController)

;(async function() {
  await executor.toPromise()

  await revertController.revert() // ExecutorResult, same as upsert ExecutorResult
})()

RevertController#toToken is used to store itself to something like redux.
We can take it back from RevertController.getToken

Behaviors:

  • pass RevertController to Database#update/delete/insert/upsert would block all other update/delete/insert/upsert in associated Column, before RevertController#revert or RevertController#giveup called.
  • a RevertController could be associated with one update/delete/insert/upsert call. If a consumed RevertController passed to Database, would throw a RevertController Consumed Error
  • RevertController#revert would revert all data that associated in Database.
  • RevertController#commit would commit the RevertController, and it could not get from class RevertController, after commit, every other method be called would throw RevertController CommittedError

Behaviors of edge case

beforeEach:

const revertController = RevertController.createToken()
const  executor = Database.upsert('Task', {
  _id: 'xxxxxx',
  dueDate: new Date().toISOString()
}, revertController)

const revertToken = revertController.toToken()

Case 1: Should throw when revert before executor execute

;(async function() {
  await revertController.revert()  // throw TypeError, couldn't revert before executor execute
})()

Case 2: RevertController.get() Should return null before executor finish execute

;(async function() {
  revertController.getToken(revertToken) // null
  
  await [
    executor.toPromise(),
    revertController.getToken(revertToken) // null
  ]

  revertController.getToken(revertToken) // revertToken
})()

Case 3: Should be committed if executor Fail to execute

;(async function() {
  const spy = sinon.spy()
  const subscription = Database.get('Task', {
    _id: 'xxxxxx'
  })
     .changes()
     .subscribe(spy)
  
  await executor.toPromise() // Fail and throw error

  await revertController.revert() // throw CommittedError
  
  spy.calledCount // 1

  subscription.unsubscribe()
})()
Brooooooklyn commented

暂定使用表级别 行级别的 “锁” + 真实写实现，具体行为参考 API Proposal。
具体锁的实现是在传入 RevertController 的地方，计算出当前 RevertController 影响的 Column，然后缓存一个 LockObservable，下一个对同样 Column 的操作 concatMap 这个 LockObservable。

Saviio commented

我建议把 『乐观更新』这个行为当做是一个事务来看，因此 giveup() 应该 rename 到 commit()

与其说 block 表 的 C / U / D操作，我会更倾向把行为定义成：

  1. 同时针对某个表只能存在一个未提交的乐观事务
  2. 创建乐观事务的时候保存数据快照并开始收集所有 incoming 的操作
    2.1 如果该事务被revert，以快照为 baseline 开始重放
    2.2 如果该事务被commit，停止收集，清除资源(快照以及收集的数据副本)
  3. 存在事务超时，超时自动提交 (基于乐观策略)
  4. commit 之后无法 revert

锁任何写这个策略我其实很早就想过，这个机制有一个很大的问题就是：会极大的影响 client 的使用体验，它会把所有的写操作『强制序列化』，使得各种弱相关的操作响应时间无故拉长。

先去碎觉了~

Brooooooklyn commented

有一个疑问:
RevertController 绑定的那个 executor 执行失败了之后，以前是直接调用 giveup 这样是符合语义的。
但如果叫 commit，就说不通了

Miloas commented

  1. 乐观更新的部分写在OptimisticCache会很蛋疼, 因为需要额外的操作来mix真数据和OptimisticCache中的数据. 这点上我建议真实写.

  2. 乐观更新的周期不一定很短。 （比如聊天室的channel，需要 发消息/收消息 触发后端socket来创建真channel）

  3. @Brooooooklyn 的revertController是操作级别的（insert/update/delete...），有时候我们其实需要表级别的revert. (其实我们需要的是事务级别的revert）

  4. 我们现在的where是不支持嵌套的字段的，这样面临的问题就是请求的response和socket过来的数据很难patch到乐观数据上. （因为我们不能通过_id来patch，乐观数据是没有_id的）

但是真对4，有一种hack的方法，就是把乐观数据的嵌套字段拍平... 但是这个方法就很丑了...

Brooooooklyn commented

@Miloas 关于第 3 点不是很明白，你指的是 upsert 的 revert 吗？
第 4 点其实也可以用 upsert 解决。只需要将乐观更新的数据结构构造成 response/socket message 一样就行了

Miloas commented

比如聊天室我创建了三个假的（乐观的）channel，在关闭的时候，我需要把这三个全部revert了 这种情况

Miloas commented

构造成一样似乎不行..

比如
乐观更新的数据是这样的：

{
  _id: 'pseudo_xxxx'
  creator: {
    id: '123456'
    name: 'xxx'
  }
}

socket的数据是这样:

{
  _id: 'xxxxx'
  creator: {
    id: '123456'
    name: 'xxx'
  }
}

只能通过creator.id来patch

Brooooooklyn commented

@Miloas

{
  _id: 'xxxxx'
  creator: {
    id: '123456'
    name: 'xxx'
  }
}

如果后端返回的是这种数据，那么这个行为是无法 revert 的= =，没法构建 predicate 查到这个数据啊，是不是要让后端处理一下返回数据，或者前端自己怼一个 _creatorId 出来 @Saviio

多个乐观更新全部 revert，我们可能要在 revertController 上提供一个 merge 方法，将多个 revertController merge 到一起，然后一次 revert 的时候就可以在一个 transaction 内执行。这个是可以很优雅的实现的。而且这样不止是单一表，就算跨表的操作，也可以弄到一个 tx 内执行。

Miloas commented

嗯 这样就很爽了

Saviio commented

额，这周照旧很忙 (聊天里有好多性能问题要调，苍天大地啊-0-)，细节我们也许可以等周六火车上聊。

所以这里先简单说几句我看到的：

Point 1:
之前 @Miloas 提到这样的数据我们没办法 patch，是因为我早期忘记做这部分的实现了，我的失误，他跟我调 bug 的时候我才想起，之后可能会由他或者@chuan6 看看能不能补上。

{
  _id: 'pseudo_xxxx'
  creator: {
    id: '123456'
    name: 'xxx'
  }
}

本质上，上面的数据的因为可以被转译成

SELECT 
  _id,
  Member.id,
  Member.name
FROM Message 
JOIN Member ON Message.creatorId = Member.id
WHERE Member.id = '123456'

理论上，这部分功能应该是可以被实现、也应该被实现，而且优先级要比 aggregate function 以及乐观更新这个 feature 更高，因为 aggregate function 只是为了聚合数据，但反正其实本质上都可以在程序集上算，即使是后端接口有时用 DB Engine 做聚合效率并不会高，因为可能会导致S锁的存在时间被延长， (不过在我们的场景里可能又会不一样，need investigation :p。

Point 2:
我不认为存在一种需要 merge 多个乐观请求的说法。
以我(们)现在定义，应该以事务的颗粒度来描述『乐观更新』这个 feature，无论是更新一条数据还是多条数据，颗粒度都应该在『事务』的个数上，而不是在数据的条目数上，因为即使影响多条数据也是一个事务，要么一起成功，要么一起失败。

其实早期的时候(3月左右?)我曾经设计过一个外置的 Transaction 的 feature，可以以类似以下的方式写代码 (伪代码)，这样模式可能会更正交。

import { Database, TransactionScope } from 'reactivedb'
const db = new Database()
const tx = new TransactionScope()
const q1 = db.update('foo', { where: { _id: 1 } })
const q2 = db.insert('foo', { _id: 2 })
tx.commit()
// q1 q2 会在一个事务内被执行

但后来另外一个 feature 干扰到了这个设计(但具体原因我已经忘了- -)，我就没做实现了。

Point 3:
你之前问的

RevertController 绑定的那个 executor 执行失败了之后，以前是直接调用 giveup 这样是符合语义的。但如果叫 commit，就说不通了

我认为这个歧义在于，我把『乐观更新』的着眼点放在事务上，而你可能更放在 revert 这个动作上。但其实一个传统的 DB Transaction 中的一个 statement 也是可以执行失败的 (典型的就是一个INSERT Statement 违反表的类型约束)，那么这个 transaction 自然就是无法 commit (报错) 并自动 rollback，而不是用 giveup 的行为来放弃。这里的行为其实还是比较类似的。

Point 4:
我不算特别赞成 LockObservable 的思路，之前我就提到过这个方案会把

所有的写操作『强制序列化』

我洗澡的时候一想，这其实等于开了一个 Serializable 级别的事务，而这个级别的事务本质上是悲观锁，这和我们的初衷并不相同。

Point 5:
我认为我们的场景里也许可以从 git 的 rebase 行为上汲取一些灵感 ?

暂时就想到这么多....讲道理我觉得 Association query 这个需求更重要一些...