5分钟快3首页    注册   登录
5分钟快3 = way to explore
5分钟快3 是一个5分钟快3关于 分享和探索的地方
现在注册
已注册用户请  登录
yafeilee
5分钟快3  ›  程序员

ShowMeBug 核心5分钟快3技术 内幕

  •  2
     
  •   yafeilee · 206 天前 · 3559 次点击
    这是一个创建于 206 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    OT 转换算法

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

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

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

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

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

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

    转换的核心是

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

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

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

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

    OT Rails 侧的处理

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

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

    因为网络传输的不可靠性,5分钟快35分钟快3我 们 必须按次序处理每一个操作。所以首先,5分钟快35分钟快3我 们 实现了一个互斥锁,也就是针对某一个面试板,准备一个锁,同时只有一个操作可以进行操作。锁采用了 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
    

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

    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
    

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

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

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

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

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

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

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

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

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

    总结

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

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

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

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

    31 条回复    2019-11-14 13:35:24 +08:00
    5分钟快3Win
kidney
        1
    5分钟快3Win kidney   206 天前   ❤️ 1
    没想到细节这么多 23333,赞一个。
    yafeilee
        2
    yafeilee   206 天前
    这篇公开了 ShowMeBug 的核心5分钟快3技术 点,但仍然有5分钟快3优化 体验的空间,有兴趣的朋友也可以考虑加入5分钟快35分钟快3我 们 团队哈。yafei#dao42.com
    rykka
        3
    rykka   206 天前 via Android
    八错
    iugo
        4
    iugo   206 天前
    两个特点:

    - 多人编辑
    - 网络延迟

    有点像5分钟快3游戏 , 如果全部要提交到5分钟快3服务 器端是否就会简单一些?

    客户端输入 A -> 5分钟快3服务 器 -> 客户端显示 A

    不过如果网络不好, 体验的确差一些.
    Justin13
        5
    Justin13   206 天前 via Android
    sharedb?
    yafeilee
        6
    yafeilee   206 天前
    @rykka 多谢支持

    @iugo 关键在于冲突检测,OT 算法体验算是最好了,因为不管网络如何,5分钟快3本地 都可以去实时响应用户操作,之后网络恢复再同步到5分钟快3服务 器即可。
    yafeilee
        7
    yafeilee   206 天前
    @Justin13 sharedb 研究过,无法解决冲突问题。
    aptx4689
        8
    aptx4689   206 天前
    @yafeilee 做一下基本安全处理吧,python 没屏蔽危险库,可以做各种操作,还能反弹 shell
    yafeilee
        9
    yafeilee   206 天前
    @aptx4689 放心哈,都做了安全隔离,随便使用。
    yafeilee
        10
    yafeilee   206 天前
    @aptx4689 就是期待给大家一个自由的编程环境,可以考察任何问题。
    xiao0sun
        11
    xiao0sun   206 天前 via iPhone
    5分钟快3你 们会收集面试题吗
    zzl22100048
        12
    zzl22100048   206 天前 via iPhone
    选择 ot 而不是 crdt 是有什么原因吗
    yafeilee
        13
    yafeilee   206 天前
    @zzl22100048 CRDT 是个好东西,OT 的诞生主要是处理文本共享,CRDT 是个分布式思想,更通用。http://stackoverflow.com/questions/26694359/differences-between-ot-and-crdt 这里有个解释。

    用 OT 目前来说主要是考虑实现轻便。
    yafeilee
        14
    yafeilee   206 天前
    @xiao0sun 在规划中,等全部搞定了就开放出来。
    chinese_zmm
        15
    chinese_zmm   206 天前 via iPhone
    github 中的冲突解决也是用的这类算法吗?
    yafeilee
        16
    yafeilee   206 天前
    @chinese_zmm 那就不一样了,git 中冲突是留给用户的。它只提供 diff 对比。ShowMeBug 是用交换幂等自动处理冲突。
    guanhui07
        17
    guanhui07   205 天前   ❤️ 1
    赞一个
    rina
        18
    rina   205 天前
    非常厉害,赞!!!!
    kaneg
        19
    kaneg   205 天前 via iPhone
    问楼主可能引发冲突的几个疑问:
    1 )在同一个位置,第一个人插入字符 A,同时另一个人插入 B,结果是 AB 都在那里还是只有一个 A 或 B ?

    2 )如果有人5分钟快3删除 了一行,而另一个人同时在该行中间插入了一个字符,那结果应该是什么?是整行都没了还是只留一个字符在中间位置?
    Aruforce
        20
    Aruforce   205 天前 via Android
    分布式锁…5分钟快3我 还以为真的实现了并发操作…自动解决冲突……
    yexiaoxing
        21
    yexiaoxing   205 天前
    之前在做 o365 online 的时候也有类似的功能,楼主分享的很好啊
    chenggiant
        22
    chenggiant   205 天前
    有一个小疑问,面试感觉不是多人同时编辑的场景啊?
    wpzero
        23
    wpzero   205 天前 via iPhone
    Codepad
    yafeilee
        24
    yafeilee   205 天前
    @kaneg 5分钟快3你 可以去 ShowMeBug 里试一下,结果是随机的,主要看进入5分钟快3服务 器的顺序。
    yafeilee
        25
    yafeilee   205 天前
    @Aruforce 不明白5分钟快3你 的意思,5分钟快35分钟快3我 们 5分钟快3技术 实现上有锁,在5分钟快3服务 端,对用户无锁,并发操作自动解决冲突。
    yafeilee
        26
    yafeilee   205 天前
    @yexiaoxing 多谢支持呀。
    yafeilee
        27
    yafeilee   205 天前
    @chenggiant 好的面试过程应该是互动的,所以同时讨论是有必要的。
    Aruforce
        28
    Aruforce   205 天前 via Android
    @yafeilee 结合# 19 # 24 来看…5分钟快3你 这是相当于有冲突了就 roll 点…roll 中哪个算哪个…修改谁后近5分钟快3服务 器谁有理…
    这对于用户来说并不是什么自动解决冲突吧?

    冲突5分钟快3你 能无锁解决的话…就不只是 dalao 了…
    即使用锁…5分钟快3你 的一个面试一把锁…这锁的粒度也太大了…根据具体的数据结构应该可以弄分段锁…

    要5分钟快3我 写的话,长链接加分布式锁就可以…,修改前先取锁,取锁成功…发到5分钟快3服务 器做修改…完了推送到各客户端,完了再解锁…并发冲突直接就避免了…并不需要解决什么冲突…
    yafeilee
        29
    yafeilee   205 天前
    @Aruforce 5分钟快3你 的理解有偏差,先看看 OT 算法吧兄弟。

    一个用户在5分钟快3删除 整行,另一个用户在该行加字符,那当然要看谁先提到5分钟快3服务 器而产生不同的结果呀。
    xiao0sun
        30
    xiao0sun   200 天前 via iPhone
    @yafeilee 不太明白5分钟快3你 的意思,5分钟快3你 的初始客户是5分钟快3企业 ,5分钟快3你 要收集5分钟快3企业 的面试题开放给应聘者?还是建题库开放给所有5分钟快3合作 的5分钟快3企业 ?这两个方向区别可大了,别走错了方向啊
    yafeilee
        31
    yafeilee   199 天前
    @xiao0sun 计划是后者,5分钟快3企业 之间也可以开放共享,5分钟快3你 的建议是?
    5分钟快3关于   ·   FAQ   ·   API   ·   5分钟快35分钟快3我 们 的愿景   ·   广告投放   ·   感谢   ·   实用小5分钟快3工具   ·   3930 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 04:45 · PVG 12:45 · LAX 21:45 · JFK 00:45
    ♥ Do have faith in what you're doing.