分享 ShowMeBug 核心技术内幕

lyfi2003 for 深圳至简天成科技有限公司 · 2019年10月26日 · 最后由 lithium4010 回复于 2019年12月24日 · 6018 次阅读
本帖已被设为精华帖!

ShowMeBug 是一款远程面试工具,双方可通过在线面试板进行实时沟通技术。所以关键技术要点在于 “实时同步”。关于实时同步,ShowMeBug 采用了以下技术。

OT 转换算法

本质上,ShowMeBug 核心就是多人同时在线实时编辑,难点即在这里。因为网络原因,操作可能是异步到达,丢失,与他人操作冲突。想想这就是个复杂的问题。

经过研究,最好用户体验的方式是 OT 转换算法。此算法由 1989 年 C. Ellis 和 S. Gibbs 首次提出,目前像 quip,google docs 均用的此法。

OT 算法允许用户自由编辑任意行,包括冲突的操作也可以很好支持,不用锁定。它的核心算法如下:

文档的操作统一为以下三种类型的操作( Operation ):

  1. retain(n): 保持 n 个字符
  2. insert(s): 插入字符串 s
  3. delete(s): 删除字符串 s

然后客户端与服务端各记录历史版本,每次操作都经过一定的转换后,推送给另一端。

转换的核心是

S(o_1, o_2) = S(o_2, o_1)

换言之,把正在并发的操作进行转换合并,形成新的操作,然后应用在历史版本上,就可以实现无锁化同步编辑。

下图演示了对应的操作转换过程。

这个算法的难点在于分布式的实现。客户端服务端均需要记录历史,并且保持一定的序列。还要进行转换算法处理。

OT Rails 侧的处理

本质上,这是一个基于 websocket 的算法应用。所以我们没有怀疑就选用 ActionCable 作为它的基础。想着应该可以为我们节省大量的时间。实际上,我们错了。

ActionCable 实际上与 NodeJS 版本的 socket.io 一样,不具备任何可靠性的保障,做一些玩意性的聊天工具还可以,或者做消息通知允许丢失甚至重复推送的弱场景是可以的。但像 OT 算法这种强要求的就不可行了。

因为网络传输的不可靠性,我们必须按次序处理每一个操作。所以首先,我们实现了一个互斥锁,也就是针对某一个面试板,准备一个锁,同时只有一个操作可以进行操作。锁采用了 Redis 锁。实现如下:

def unlock_pad_history(lock_key)
  logger.debug "[padable] unlock( lock_key: #{lock_key} )..."
  old_lock_key = REDIS.get(_pad_lock_history_key)
  if old_lock_key == lock_key
    REDIS.del(_pad_lock_history_key)
  else
    log = "[FIXME] unlock_pad_history expired: lock_key=#{lock_key}, old_lock_key=#{old_lock_key}"
    logger.error(log)
    e = RuntimeError.new(log)
    ExceptionNotifier.notify_exception(e, lock_key: lock_key, old_lock_key: old_lock_key)
  end
end

# 为防止死锁,锁的时间为5分钟,超时自动解锁,但在 unlock 时会发出异常
def lock_pad_history(lock_key)
  return REDIS.set(_pad_lock_history_key, lock_key, nx: true, ex: 5*60)
end

def wait_and_lock_pad_history(lock_key, retry_times = 200)
  total_retry_times = retry_times
  while !lock_pad_history(lock_key)
    sleep(0.05)
    logger.debug '[padable] locked, waiting 50ms...'
    retry_times-=1
    raise "wait_and_lock_pad_history(in #{total_retry_times*0.1}s) #{lock_key} failed" if retry_times == 0
  end
  logger.debug "[padable] locking it(lock_key: #{lock_key})..."
end

服务端的并发控制完毕后,客户端通过 “状态队列” 技术一个个排队发布操作记录,核心如下:

class PadChannelSynchronized {
  sendHistory(channel, history){
    channel._sendHistory(history)
    return new PadChannelAwaitingConfirm(history)
  }
}

class PadChannelAwaitingConfirm {
  constructor(outstanding_history) {
    this.outstanding_history = outstanding_history
  }

  sendHistory(channel, history){
    return new PadChannelAwaitingWithHistory(this.outstanding_history, history)
  }

  receiveHistory(channel, history){
    return new PadChannelAwaitingConfirm(pair_history[0])
  }

  confirmHistory(channel, history) {
    if(this.outstanding_history.client_id !== history.client_id){
      throw new Error('confirmHistory error: client_id not equal')
    }
    return padChannelSynchronized
  }
}

class PadChannelAwaitingWithHistory {
  sendHistory(channel, history){
    let newHistory = composeHistory(this.buffer_history, history)
    return new PadChannelAwaitingWithHistory(this.outstanding_history, newHistory)
  }
}

let padChannelSynchronized = new PadChannelSynchronized()

export default padChannelSynchronized

以上,便实现了一个排队发送的场景。

除此之外,我们设计了一个 PadChannel 用来专门管理与服务器通信的事件,维护历史的状态,处理断线重传,操作转换与校验。

定义自己的历史(history) 协议

解决了编辑器协同的问题,才是真正的问题的开始。每次的 ” 代码运行”,“编辑”,“清空终端”,“首次同步” 都是需要记录的历史操作。于是,ShowMeBug 定义了以下协议:

# 包含以下: edit( 更新编辑器内容 ), run( 执行命令 ), clear( 清空终端 ), sync( 同步数据 )
# select( 光标 ), locate( 定位 )
# history 格式如下:
#
# {
# op: 'run' | 'edit' | 'select' | 'locate' | 'clear'
# id: id // 全局唯一操作自增id, 首次前端传入时为 null, 服务端进行填充, 如果返回时为空, 则说明此 history 被拒绝写入
# version: 'v1' // 数据格式版本
# prev_id: prev_id // JS端生成 history 时上一次收到服务端的 id, 用于识别操作序列
# client_id: client_id // 客户端生成的 history 的唯一标识
# creator_id: creator_id // 操作人的用户id, 为了安全首次前端传入时为 null,由中台填充
# event: { // op 为 edit 时, 记录编辑器 OT 转化后的数据, see here: https://github.com/Aaaaash/blog/issues/10
#   [length, "string", length]
#          // op 为 select 时, 记录编辑器选择区域(包括光标)
#   }
# snapshot: {
#   editor_text: '' // 记录当前编辑器内容快照, 此快照由服务端填充
#   language_type: '' // 记录当前编辑器的语言种类
#   terminal_text: '' // 记录当前终端快照
#   }
# }
# created_at: created_at // 生成时间

值得说明的是,client_id 是客户端生成的一个 8 位随机码,用于去重和与客户端进行 ACK 确认。

id 是由服务端 Redis 生成的自增 id,客户端会根据这个判断历史是否是新的。prev_id 用来操作转换时记录所需要进行转换操作的历史队列。

event 是最重要的操作记录,我们用 OT 的转换数据进行存储,如: [length, "string", length]

通过上述的设计,我们将面试板的所有操作细节涵盖了,从而实现多人面试实时同步,面试题和面试语言自动同步,操作回放等核心功能。

总结

篇幅限制,这里只讲到 ShowMeBug 的核心技术,更多的细节我们以后继续分享。

ShowMeBug 目前承载了 3000 场面试记录,成功支撑大量的实际面试官的面试,可靠性已得到进一步保障。这里面有两种重要编程范式值得考虑:

  1. 如何在不可信链路上设计一种有序可靠的交付协议,定义清晰的协议数据和处理好异步事件是关键。
  2. 如何平衡研发效率与稳定性之间的关系,比如实现的忙等锁,允许一定原因的失败,但处理好用户的提示与重试。既高效完成了功能,又不影响到用户体验。

ShowMeBug( https://www.showmebug.com ) 让你的技术面试更高效,助你找到你想要的候选人。

1楼 已删除

这个场景比较适合 Elixir, 除了并发上的优势,还有 OTP 用来支持 “OT 转换算法”。

"ActionCable 实际上与 NodeJS 版本的 socket.io 一样,不具备任何可靠性的保障"

可否给些链接/资料,给外行/小白解释/讲诉可靠性的问题?

lana 回复

ActionCable 的使用建议大家自行研究源码,外面的文档只有 https://guides.rubyonrails.org/action_cable_overview.html 比较完整。

ActionCable 的问题可参阅: https://www.ably.io/blog/rails-actioncable-the-good-and-the-bad

申请加精

hooopo 将本帖设为了精华贴 10月29日 19:24
piecehealth 回复

并发上的优势是啥

一说到可靠性 就不得不吹一波 Phoenix Channel

其实 Phoenix LiveView 也可以实现

rails 对这方面的支持真不如 Phoenix,LiveView 可吹爆

WalkPhoneGo 回复

不一样不一样的需求。因此切换的话成本也巨高。

lyfi2003 回复

@WalkPhoneGo @lyfi2003

可靠性 具体指的什么?

要是说,从服务端,发出去的消息,客户端一定能收到。这个 phoenix 也做不到吧?这个应该考回执来做?

@WalkPhoneGo 求具体介绍下。

yfractal 回复

1.ActionCable 只有服务端到客户端的心跳,客户端掉线不知道。这点 Phoenix Channel 自带。

2.ActionCable 存在重复进入问题,同一个用户可以多次进入同一个频道.这点 Phoenix Channel 自带去重。

3.ActionCable 的订阅机制是基于 Redis Pub/Sub, 无法平行扩展,必须要连同一个的 Redis 存 Session。这点 Phoenix Channel 也是自带的,基于 PG2。

4.Phoenix Channel 可以回复给单独一个用户,这点 ActionCable 做不到,除非单独给用户一个频道。

5.Phoenix Channel 可以支持单机 200 万并发 可以 Google,虽然用的硬件很好,但是也很厉害。据说 Ruby 2.7 可以提升 ws 的并发性能。

6.Phoenix Channel 自带用户在线列表,不需要自己维护,可以在一个集群内监控用户的上下线。

你一定要说 Actioncable 有一点好,就是太 TM 简单了,快速出效果还是极好的,真的上线还是推荐 Phoenix Channel!!!

WalkPhoneGo 回复

从服务端,发出去的消息,客户端一定能收到。

这个 phoenix 是怎么做到的?还是说,可靠性不考虑这一点?

WalkPhoneGo 回复

是一台物理机,记得没错是 120g 的内存。

但这个是性能吧?还看过 go 可以几个 G 百万并发。。。

虽然 go 性能看起来更好,但 erlang 在这个场景更合适。

因为 erlang 有抢占式调度,go 没有。erlang 有并发模型,go 的 channel 相对来讲太简单了。很多东西做不了,或者不好做。

我问的不是 phoenix 性能好不好好,也不是想跟你讨论,phoenix 和 rails 相比,哪个好。

我就是想问。

  1. 可靠性指的是什么?
  2. phoenix 怎么保证的?

我理解,你回答的 1、2、4、6 都是功能的问题。 3、5 是性能的问题。

大体上(看起来都没问题,不过没仔细看),暂时都同意你的说法。

最后再强调下

  1. 我不想跟你讨论哪个更好的这个问题。 我更好奇的是,背后的原因是什么? 就是
  2. 可靠性具体指的是什么?
  3. 既然你说,phoenix 更可好,那 phoenix 怎么做到的?

@yfractal @WalkPhoneGo 很多时候还要看具体的应用表现怎么样,开发成本如何。

yfractal 回复

AC 不知道客户端死活,可重复进入,并发差 这看起很可靠吗?

我的意思就是 Pheonix Channel 一开始就解决了这些问题。

至于为什么,不好意思我没研究过。

因为我用 AC 和 PC 分别实现了一个聊天程序,这是我的一些直观感受。

WalkPhoneGo 回复

如果这么理解可靠性,也不是不可以。

关于这个模块,我说下我理解的可靠性吧。

坦白的讲,我不是很介意性能差一点,但 AC 似乎是很不怎么好。更在乎这个模块可不可以横向扩展。能横向能扩展,就可以无脑堆机器。

再就是,在一些奇奇怪怪的场景下,这个服务还可以健康的活着。比如大量用户重连的情况下、流量激增、一台机器突然挂掉,剩下的节点是不是能正常工作。

以及,用户断连到重连,这段时间内的消息,要怎么处理(有单独服务处理会更好)。能不能确认消息已经传到客户端有单独服务处理会更好)。再复杂一点,有序。

1 无脑堆机器 不行

2 大量用户 是多少 稍微多一点人 AC 就是一具尸体了

3 这个不是框架能保证的 需要自己实现

@WalkPhoneGo 功能、性能、可靠性,这些是不同的东西?为啥跟你讨论可靠性,你为什么非要说功能和性能呢?

至于为什么,不好意思我没研究过。

其实挺期待你说说原因的。

那按照你的逻辑,我试着回复一下哈。

1 无脑堆机器 不行

大量用户 是多少 稍微多一点人 AC 就是一具尸体了

没事

这个不是框架能保证的 需要自己实现

1、2、4、6 都是功能,需要自己实现。

刚看到别人的实时协同的研究成果 local-first software

Together with my collaborators I am developing the foundations of a new kind of collaboration software, which we are calling local-first software. It aims to achieve the best of both worlds: allowing the user-friendly real-time collaboration of applications like Google Docs, in which several people can make changes simultaneously without suffering conflicts, but without relying on trusted, centralised servers.

这个互斥锁的 redis 实现有点简陋了

lithium4010 回复

怎么实现不简陋? 听听你的高见😀

redisson 的锁没有 zookeeper 的锁可靠。

rubyonlinux 回复

要保证正确性的话, 数据库也不错

def unlock_pad_history(lock_key)
  logger.debug "[padable] unlock( lock_key: #{lock_key} )..."
# --- BEGIN 我觉得主要问题是这里,两步操作如果可以合并成原子操作就会好很多,基本够用  
old_lock_key = REDIS.get(_pad_lock_history_key)
  if old_lock_key == lock_key
    REDIS.del(_pad_lock_history_key)
#### ---- END
  else
    log = "[FIXME] unlock_pad_history expired: lock_key=#{lock_key}, old_lock_key=#{old_lock_key}"
    logger.error(log)
    e = RuntimeError.new(log)
    ExceptionNotifier.notify_exception(e, lock_key: lock_key, old_lock_key: old_lock_key)
  end
end
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册