ShowMeBugコアテクノロジーの内幕
5802 ワード
ShowMeBugはリモート面接ツールで、双方はオンライン面接板を通じてリアルタイムのコミュニケーション技術を行うことができます.重要なテクノロジーのポイントは、「リアルタイム同期」です.リアルタイム同期について、ShowMeBugは以下の技術を採用している.
OT変換アルゴリズム
本質的に、ShowMeBugの核心は複数人が同時にオンラインでリアルタイムに編集することであり、難点はここにある.ネットワークの原因で、操作は非同期で到着し、失われ、他人の操作と衝突する可能性があります.これが複雑な問題だと思います.
研究の結果,最良のユーザ体験方式はOT変換アルゴリズムである.このアルゴリズムは1989年にC.EllisとS.Gibbsが初めて提案し、現在はquip、google docsのように使われている.
OTアルゴリズムは,ユーザが任意の行を自由に編集することを可能にし,衝突を含む操作もロックせずによくサポートできる.コアアルゴリズムは次のとおりです.
ドキュメントの操作は、以下の3種類の操作(Operation)に統一されています. を保持 その後、クライアントとサービス側はそれぞれ履歴バージョンを記録し、操作のたびに一定の変換を経て、反対側にプッシュします.
変換の核心は
S(o_1, o_2) = S(o_2, o_1)
すなわち、同時実行中の操作を変換して統合し、新しい操作を形成し、履歴バージョンに適用することで、無ロック同期編集を実現することができる.
次の図は、対応する操作変換プロセスを示しています.
https://daotestimg.dao42.com/ipic/070918.jpg
このアルゴリズムの難点は分布式の実現にある.クライアント・サービス・エンドは、履歴を記録し、一定のシーケンスを維持する必要があります.変換アルゴリズム処理も行います.
OT Rails側の処理
本質的には,これはwebsocketに基づくアルゴリズム応用である.だから私たちは疑いなくActionケーブルをその基礎として選んだ.私たちのために多くの時間を節約できると思います.実は、私たちは間違っています.
Actionケーブルは実際にNodeJSバージョンのsocket.とioと同様に、信頼性の保障がなく、遊び心のあるチャットツールを作ったり、メッセージ通知をしたりして、紛失や繰り返しプッシュを許可する弱いシーンをしたりすることができます.しかしOTアルゴリズムのような強い要求はできない.
ネットワーク伝送の信頼性が低いため、各操作を順番に処理しなければなりません.まず、ある面接板に対して、1つのロックを用意し、同時に1つの操作だけが操作できるようにしました.ロックはRedisロックを採用しています.次のようになります.
def unlock_pad_history(lock_key)
end
#デッドロックを防止するため、ロック時間は5分、タイムアウトは自動的にロックを解除しますが、unlock時に異常def lock_が発行されます.pad_history(lock_key)
end
def wait_and_lock_pad_history(lock_key, retry_times = 200)
end
サービス側の同時制御が完了すると、クライアントは「ステータスキュー」技術を通じて1つずつキューに並んで操作記録を発表し、核心は以下の通りである.
class PadChannelSynchronized { sendHistory(channel, history){
} }
class PadChannelAwaitingConfirm { constructor(outstanding_history) {
}
sendHistory(channel, history){
}
receiveHistory(channel, history){
}
confirmHistory(channel, history) {
} }
class PadChannelAwaitingWithHistory { sendHistory(channel, history){
} }
let padChannelSynchronized = new PadChannelSynchronized()
export default padChannelSynchronized
以上で,1つのキューで送信するシーンを実現した.
それ以外に,サーバと通信するイベントを専門に管理し,履歴の状態を維持し,断線再伝送を処理し,変換と検証を操作するためのPadChannelを設計した.
自分の履歴プロトコルを定義する
エディタのコラボレーションの問題を解決することこそ、本当の問題の始まりです.毎回の「コード実行」、「編集」、「端末を空にする」、「初回同期」は、記録する必要がある履歴操作です.そこで、ShowMeBugは以下のプロトコルを定義した.
#には、edit(エディタの内容の更新)、run(コマンドの実行)、clear(端末のクリア)、sync(データの同期)#select(カーソル)、locate(位置決め)#historyフォーマットは次のとおりです:#{#op:'run'|'edit'|'select'|'locate'|'clear'#id:id//グローバル一意操作自増id、初回フロントエンド着信時はnull、サービス側は充填され、戻り時が空の場合、このhistoryが#version:'v 1'//データフォーマットバージョン#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/bl...#[length,“string”,length]#//opがselectの場合、レコードエディタ選択領域(カーソルを含む)#}#snapshot:{#editor_text:'//現在のエディタコンテンツスナップショットを記録します.このスナップショットは、サービス側が#language_type:'//現在のエディタの言語種を記録します#terminal_text:'//現在の端末スナップショットを記録します#}#created_at: created_at//生成時間
なお、
上記の設計を通じて、面接板のすべての操作の詳細をカバーし、複数人の面接のリアルタイム同期、面接問題と面接言語の自動同期、操作再生などの核心機能を実現しました.
まとめ
紙面の制限は、ここではShowMeBugの核心技術だけを話して、もっと詳細は後で共有し続けます.
ShowMeBugは現在3000回の面接記録を載せており、多くの実際の面接官の面接を支えることに成功し、信頼性がさらに保障されている.この中には2つの重要なプログラミングモデルがあります.は、明確なプロトコルデータを定義し、非同期イベントを処理する方法が重要です. はどのように研究開発効率と安定性の関係をバランスさせるか、例えば実現の忙しいなどのロックは、一定の原因の失敗を許可するが、ユーザーのヒントと再試行を処理する.効率的に機能を達成し、ユーザー体験に影響を与えません.
ShowMeBug(showmebug.com)は、技術面接をより効率的にし、希望する候補者を見つけるのに役立ちます.
OT変換アルゴリズム
本質的に、ShowMeBugの核心は複数人が同時にオンラインでリアルタイムに編集することであり、難点はここにある.ネットワークの原因で、操作は非同期で到着し、失われ、他人の操作と衝突する可能性があります.これが複雑な問題だと思います.
研究の結果,最良のユーザ体験方式はOT変換アルゴリズムである.このアルゴリズムは1989年にC.EllisとS.Gibbsが初めて提案し、現在はquip、google docsのように使われている.
OTアルゴリズムは,ユーザが任意の行を自由に編集することを可能にし,衝突を含む操作もロックせずによくサポートできる.コアアルゴリズムは次のとおりです.
ドキュメントの操作は、以下の3種類の操作(Operation)に統一されています.
retain(n):n文字insert(s):挿入文字列s delete(s):削除文字列s 変換の核心は
S(o_1, o_2) = S(o_2, o_1)
すなわち、同時実行中の操作を変換して統合し、新しい操作を形成し、履歴バージョンに適用することで、無ロック同期編集を実現することができる.
次の図は、対応する操作変換プロセスを示しています.
https://daotestimg.dao42.com/ipic/070918.jpg
このアルゴリズムの難点は分布式の実現にある.クライアント・サービス・エンドは、履歴を記録し、一定のシーケンスを維持する必要があります.変換アルゴリズム処理も行います.
OT Rails側の処理
本質的には,これはwebsocketに基づくアルゴリズム応用である.だから私たちは疑いなくActionケーブルをその基礎として選んだ.私たちのために多くの時間を節約できると思います.実は、私たちは間違っています.
Actionケーブルは実際にNodeJSバージョンのsocket.とioと同様に、信頼性の保障がなく、遊び心のあるチャットツールを作ったり、メッセージ通知をしたりして、紛失や繰り返しプッシュを許可する弱いシーンをしたりすることができます.しかしOTアルゴリズムのような強い要求はできない.
ネットワーク伝送の信頼性が低いため、各操作を順番に処理しなければなりません.まず、ある面接板に対して、1つのロックを用意し、同時に1つの操作だけが操作できるようにしました.ロックは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
サービス側の同時制御が完了すると、クライアントは「ステータスキュー」技術を通じて1つずつキューに並んで操作記録を発表し、核心は以下の通りである.
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
以上で,1つのキューで送信するシーンを実現した.
それ以外に,サーバと通信するイベントを専門に管理し,履歴の状態を維持し,断線再伝送を処理し,変換と検証を操作するためのPadChannelを設計した.
自分の履歴プロトコルを定義する
エディタのコラボレーションの問題を解決することこそ、本当の問題の始まりです.毎回の「コード実行」、「編集」、「端末を空にする」、「初回同期」は、記録する必要がある履歴操作です.そこで、ShowMeBugは以下のプロトコルを定義した.
#には、edit(エディタの内容の更新)、run(コマンドの実行)、clear(端末のクリア)、sync(データの同期)#select(カーソル)、locate(位置決め)#historyフォーマットは次のとおりです:#{#op:'run'|'edit'|'select'|'locate'|'clear'#id:id//グローバル一意操作自増id、初回フロントエンド着信時はnull、サービス側は充填され、戻り時が空の場合、このhistoryが#version:'v 1'//データフォーマットバージョン#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/bl...#[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は最も重要な操作記録であり、[length, "string", length]のようなOTの変換データで格納されている.上記の設計を通じて、面接板のすべての操作の詳細をカバーし、複数人の面接のリアルタイム同期、面接問題と面接言語の自動同期、操作再生などの核心機能を実現しました.
まとめ
紙面の制限は、ここではShowMeBugの核心技術だけを話して、もっと詳細は後で共有し続けます.
ShowMeBugは現在3000回の面接記録を載せており、多くの実際の面接官の面接を支えることに成功し、信頼性がさらに保障されている.この中には2つの重要なプログラミングモデルがあります.
ShowMeBug(showmebug.com)は、技術面接をより効率的にし、希望する候補者を見つけるのに役立ちます.