ダブルイレブンとの戦い - アリババのライブ ストリーミング プラットフォームが直面する技術的課題_html/css_WEB-ITnose

前書き: ダブル イレブンは常にトランザクションに重点を置いており、今年も確かに同じですが、これは全能のタオバオがダブル イレブンをより楽しく、より豊かな体験、より多様なゲームプレイをユーザーに提供することを妨げるものではありません。したがって、今年はライブブロードキャストを特徴とするゲームダブルイレブン会場も誕生しました。これが、ダブルイレブン中にアリババのライブブロードキャストプラットフォームが直面する複雑な技術的課題とテクノロジーの選択に焦点を当てます。舞台裏も舞台裏も。

大規模なライブ ブロードキャストの技術的課題は、ビデオ ストリームの処理と配信、再生品質の保証、ビデオの可用性の監視、大規模なライブ ブロードキャスト ルームでのリアルタイムの集中砲火とチャットのやり取り、高性能のメッセージ チャネル、およびコンテンツ制御 (ビデオ コンテンツの自動ポルノ識別やメッセージ テキスト フィルタリングを含む)、システムの可用性、安定性の保証など。この記事では、いくつかの技術的な詳細に焦点を当てますが、テキストの分析と紹介を通じて、誰もがインスピレーションを得られることを願っています。

ライブビデオ

ライブブロードキャストプラットフォームの場合、さまざまなネットワーク環境下でスムーズなビデオ視聴を保証するには、高解像度の入力ストリームを異なる解像度の複数のビデオストリームに変換し、さまざまなネットワーク条件下で鮮明なビデオをサポートする必要があります。また、異なる端末でサポートされるプロトコルとカプセル化形式は完全に同じではないため、たとえば、無線端末の HTML5 ページは HLS プロトコルを十分にサポートできますが、RTMP などのプロトコルには基本的に無力です。 PC 端末で遅延を軽減するには、RTMP などのストリーミング メディア プロトコルを使用する必要があります。したがって、複数の端末 (PC、Android、IOS、HTML5) での表示をサポートするには、入力ストリームをエンコードし、フォーマットにカプセル化する必要があります。トランスコーディングが完了した後も、ビデオ ストリームを配信する必要があります。ビデオなどの大量のコンテンツを消費するシナリオでは、元のサイトの負荷容量とノード数が限られており、ほとんどのユーザーから遠く離れています。再生品質の遅延を軽減するには、ユーザーへの送信リンクを最小限に抑える必要があります。したがって、通常のアプローチは、ビデオ ストリームをスライスして分散ファイル システムに保存し、CDN に配布するか、CDN がユーザーに最も近いため、セカンダリ レベルで CDN を介してストリームを直接転送することです。ライブ コンテンツはユーザーにとって低コストであり、ユーザーの最短パスでアクセスできること。クライアントの遅延要件と使用されるプロトコルによって、ビデオを断片化する必要があるかどうかが決まります。断片化の目的は、ユーザーが HTTP プロトコルを通じてビデオ全体をダウンロードする必要がなく、再生する前にいくつかの断片をダウンロードするだけで済むようにすることです。実際、ライブ ブロードキャストと録画ブロードキャストのテクノロジーは似ていますが、違いは、ライブ ストリームの終了時刻は予測できないのに対し、録画されたビデオ ストリームの終了時刻はわかっていることです。遅延要件がそれほど高くないシナリオでは、クライアントは HLS プロトコルを使用できます。結局のところ、IOS、Andriod、HTML5 などのワイヤレス アプリケーションは互換性があり、サポートされており、一般的に使用される静的リソース CDN は対応する変更を加えることなく使用できます。これはサポートできますが、HLS プロトコルに固有の大きな欠陥は、ビデオ コンテンツがスライスされ、配信され、クライアントによってダウンロードされるまでに長い時間がかかることです。非常に高い適時性要件があるシナリオでは、遅延を減らすために RTMP や RTSP などのリアルタイム ストリーミング メディア プロトコルを使用する必要があります。また、配信元サイトへの負担を軽減するために、CDN エッジ ノードがストリームを転送する必要があります。次に、CDN は、一般にストリーミング メディア CDN として知られる、対応するストリーミング メディア プロトコルをサポートする必要があります。

ライブストリームはアンカーによってアップロードされるため、違法コンテンツ、特にポルノコンテンツをどのように規制するかは非常に困難な問題となっています。嬉しいことに、技術の発展により、黄色画像のアルゴリズムの認識精度が非常に高くなり、基本的に本番環境で適用できるレベルに達しました。そのため、ビデオを配信する前にビデオフレームを抽出することも試みています。画像は識別のためにアルゴリズムに渡され、事前に設定されたしきい値を超えると、早期警告が発せられるか、ライブ ブロードキャスト ルームが閉鎖されます。一定の実践の結果、一定の成果が得られ、人件費も削減されましたが、画像認識アルゴリズムは一般的なアルゴリズムに比べて時間の計算量が多く、スループット率が低いことは避けられません。

ストリーミング、トランスコーディング、スライス、配信、クライアントのダウンロード、再生などを含む、ライブ ブロードキャストのリンク全体は比較的長いです。リンク上のいずれかのノードに問題がある場合、ビデオは再生されない可能性があります。したがって、キー ノードの監視は非常に重要です。また、リンク全体の可用性も監視する必要があります。たとえば、HLS プロトコルの場合、対応する m3u8 インデックス リストが存在するかどうかを監視することで判断できます。ストリームが中断されているかどうかを更新します。もちろん、ビデオ ストリーム内のフレームにぼやけた画面があるか黒い画面があるかを判断するのはさらに複雑です。さらに、監視ノードが訪問する CDN ノードとユーザーが訪問する CDN ノードは同じ領域にない可能性があります。中国の現在のネットワーク環境、特にネットワーク セグメント間のネットワーク アクセスには、ストリーミング メディア アプリケーションにとって制御できない大きな要因があり、クライアントのネットワーク アクセス環境はビデオ再生に決定的な影響を与えます。したがって、フィードバックのためにエンドユーザーの再生データ品質データを収集し、タイムリーにビデオ定義を切り替えることが特に重要です。これらのデータには、クライアントの地理的分布、再生遅延情報、ビデオ フラグメントの読み込み時間などが含まれます。この情報のフィードバックに基づいて、CDN ノードの展開が合理的であるかどうか、新しい CDN ノードを追加する必要があるかどうか、およびビデオのトランスコーディング パラメータなど、さまざまなモデルの互換性をタイムリーに調整して、ユーザー エクスペリエンスを向上させます。

(画像をクリックすると拡大します)

図1 ビデオライブブロードキャストの構造

メッセージ/弾幕

WEB IMアプリケーションと弾幕は近年ますます人気があり、マーケティングやアクティブな活動にとって非常に重要です雰囲気のメソッド。同時にオンラインで多数の人が参加するリアルタイム チャット インタラクションやリアルタイム ライブ集中砲火などのシナリオでは、メッセージのリアルタイム性を確保するという前提の下で、非常に高い同時実行性の圧力がかかります。たとえば、アクティブなライブ ブロードキャスト ルームに同時にオンラインで 100,000 人がいて、人気のゲーム イベントがライブブロードキャストされていると仮定すると、各人が毎秒 1 語ずつ話すと、100,000 メッセージが生成されます。 /s メッセージはアップストリーム QPS であり、各メッセージはその部屋にいる全員にブロードキャストされる必要があります。これは、ダウンストリーム メッセージが 10w 倍に増幅され、10w*10w=100 億/秒の驚くべきメッセージ ダウンストリーム QPS に達することを意味します。ライブ ブロードキャストの QPS の場合、複数の同様のライブ ブロードキャストが同時に行われる可能性があり、これは間違いなくメッセージ チャネルにとって大きな課題になります。したがって、システムを設計するときに最初に考慮すべき問題は、メッセージ チャネルへの負荷をどのように軽減するかということです。

(クリックすると画像が拡大します)

図 2 メッセージの配信と消費

ユーザーが情報をメッセージング システムに配信した後、システムはまず、スパム対策、機密性の高いメッセージに対する一連のフィルタリングをメッセージに対して実行します。情報フィルタリングについては後で詳しく説明するため、ここでは省略します。瞬間的なピークによってシステムが圧倒されるのを防ぐために、メッセージを最初にメッセージ キューに配信してピークをカットして谷を埋め、トラフィックのピーク期間中にメッセージをバックログして、システムに一定のマージンを残して影響を軽減します。現在のビジネスへの影響により失われたメッセージの数。バックエンドは常に固定頻度でメッセージを処理し、非同期メカニズムを使用してピーク時のシステムの安定性を確保します。これは典型的なプロデューサー/コンシューマー モデルです。メッセージ コンシューマー側では、マルチスレッド モデルを使用して、固定頻度でメッセージ キューからメッセージを消費し、対応するルームに対応するオンライン ユーザーのリストを横断し、さまざまなメッセージ チャネルを通じてメッセージを配信できます。マルチスレッドによってシステムのスループット容量が向上します。特に、メッセージを一度に数万人または数十万人のユーザーに配信する必要があるシナリオでは、大規模なクラスターを非同期的に使用して並列処理を行うことで、システムのスループット容量を向上させることができます。システム。非同期により、フロントエンド メッセージのピークアップストリーム トラフィックによってバックエンド メッセージ配信が中断されなくなり、システムの安定性が向上します。

メッセージ キューの非同期処理を使用することに加えて、部屋にいる人が多すぎる場合、またはメッセージに対する下向きの圧力が大きすぎる場合は、下向きのメッセージ チャネルへの圧力をさらに軽減することも必要です。バケット戦略。いわゆるバケット化戦略により、実際にはメッセージの拡散が制限されます。100,000 人が同じ部屋でチャットしていると仮定すると、各人の言葉が瞬時に画面全体に表示される可能性があり、この場合、メッセージは基本的に読めません。情報の可読性を向上させ、下向きの圧力を軽減するために、10,000 人ごとに 1 つのバケツを配置することができます (各バケツの具体的な容量は実際のニーズに応じて調整できます。ここではほんの一例です)。ユーザーが送信したメッセージは、または、いくつかのバケットが表示され、ユーザーはバケットのサイズに従ってメッセージを受信します。これにより、フロントエンド ユーザーが受信するメッセージの量が大幅に減少します。メッセージはすべてのユーザーに送信する必要はなく、メッセージに対する下向きの圧力を軽減するために 1 つまたはいくつかのバケットに送信するだけで済みます。

バケット化には多くの戦略があります。最も単純かつ大雑把な方法は、ユーザーに基づいてランダム化することです。まず、ルームのアクティビティ レベルに基づいて、ルームをいくつのバケットに分割するかを推定し、ハッシュ関数を通じてユーザーを各バケットにマッピングします。ランダム戦略の利点は、実装が非常に簡単で、次のことができることです。ユーザーを各バケットにバランスよく割り当てる必要がありますが、多くの欠点があります。まず、ルーム内のアクティブ ユーザーの数を正確に推定することは、基本的には推測に基づいて行われるため、単一のバケット内のユーザー数が大きすぎる場合や小さすぎる場合があります。小さすぎるとメッセージ リンクへのプレッシャーが大きくなり、ユーザーが熱心な場合は後でバケットの数を調整するのが面倒になるため、すべてのユーザーがバケット数を調整する必要があります。再びハッシュ化されます。さらに、ユーザー エクスペリエンスの観点から、ライブ ブロードキャストのプロセス中に、オンライン ユーザーの数は通常、徐々に増加してピークに達し、その後バケット化により徐々に減少するプロセスを経験します。各バケットの量は比較的少ないため、必然的に集中砲火の活動に影響を及ぼし、ユーザーの減少につながる可能性があり、ユーザーは徐々にライブ配信から離脱し、不均一な状況につながります。各バケットの数:

図 3 ランダム ハッシュ バケット化

もう 1 つの解決策は、オンデマンドでバケット化して各バケットのサイズを固定し、既存のバケットがいっぱいになったら新しいバケットを作成して各バケットのサイズを制御することです。各バケット内の人数は多すぎず、少なすぎません。これにより、以前に発生した可能性のある各バケット内の人数が少なすぎる問題は解決されます。ただし、以前のランダムなバケットよりも明らかな問題があります。ユーザーが離れ続けると、人の数は徐々に減り、クリーニングが実行されない場合は、さらに多くの新しく開かれたバケツが開かれるため、最終的には依然としてバケツがアンバランスになり、多くの空のバケツが生成されます。そして、データ構造を調整する必要があります:

図 4 オンデマンド バケット化戦略

ソートされたリストを通じて、新しいユーザーが毎回最小人数のバケットに追加されるため、新しいユーザーが参加できるようになります最もアイドル状態のバケット。バケットがいっぱいの場合、新しいユーザーは追加されません。ただし、古いユーザーの離脱速度が新規ユーザーの流入速度よりもはるかに高い場合、この時点でもバケットは不均一になります。場合によっては、バケットを定期的に分割して、少数のユーザーとバケットを結合したり、空のバケットをリサイクルしたりする必要があります。また、結合プロセス中に新しいユーザーが参加し続けるため、正しいユーザー リストを確保する必要もあります。分散型の高同時実行性のシナリオでは、効率を確保するために、ロックがそれほど簡単ではない場合があり、これにより、ダーティ書き込みやダーティ読み取りが発生する可能性があります。バケットのソート アルゴリズムは、メモリに似た非常に複雑なものになります。 JVM のリサイクル アルゴリズム。

大規模なデータ量と高い同時実行性のシナリオにおけるデータベースとテーブルのシャーディング戦略と同様に、実際には、バケット化戦略もトレードオフと妥協の結果になりますが、ダウンストリーム チャネルに対する過度の圧力という元の問題は解決されますが、また、次の問題も発生します。新たな問題。まず、バケット化により、メッセージは一部のバケットのユーザーにのみ表示され、すべてのバケットのユーザーには表示されなくなります。このようにすると、異なるバケットのユーザーには異なるメッセージが表示され、別のバケットのユーザーには表示されます。問題は、上記のバケット化戦略が「人気のあるバケット」と「不人気なバケット」の影響を引き起こす可能性があることです。つまり、多くの「苦情マスター」が同じバケットに割り当てられ、非常に活発な雰囲気が生じる可能性があります。そのバケットには、それほどアクティブでないユーザーが一緒に割り当てられているため、「氷と火」の状況が発生し、製品エクスペリエンスに影響を与えます。もちろん、システムのアナウンス内容や、一部の特別な役割 (ルーム管理者、VIP、教師など) によって送信されるメッセージなど、一部の特別なメッセージの場合は、このタイプのメッセージをすべてのユーザーにブロードキャストする必要があります。メッセージ タイプを区別し、特別なメッセージ タイプを個別に処理する必要があります。

メッセージ配信タスクの場合、メッセージが誰にどのように配信されるかを知る必要があるため、ルーム内のユーザーのリストを動的に管理し、ユーザーがオンライン/オフラインになったときにシステムに通知する必要があります。ルームリストに追加するか、ルームの担当者リストから削除します。ユーザーにとっては、入室時にシステムに通知するだけなので非常に簡単ですが、オフラインのユーザーへの対応は少し面倒です。ユーザーがライブ ブロードキャスト ルームから退出するには、ブラウザのタブを閉じる、ウィンドウを閉じる、電源を切る、ホーム ボタンを押してプロセスをバックグラウンドに切り替えるなど、さまざまな方法が考えられます。イベントのコールバックを取得できますが、イベント通知を取得できない場合は、参加者のリストが増えるだけで、ルームにいる人が増え、メッセージ配信の量も増加します。それは資源の無駄遣いです。この問題を解決するには、Heartbeatを使用する必要があります。

ハートビートとは、同時にオンラインにいる人の数が大きなレベル (数百万人など) に達したときに、サーバーのオンライン状態を定期的にサーバーに報告するクライアントの 1 秒あたりのハートビート数を指します。 QPSも非常に高くなり、高いハートビート効率と高いスループットをいかに確保するかが課題となる。 1 つ目は、HTTP プロトコル、WebSocket、TCP プロトコルなどの通信プロトコルの選択です。 HTTP プロトコルの利点は、互換性とクロスターミナルです。すべてのブラウザ、Android、および IOS の WebView が十分にサポートされ、互換性があることは、PC よりもモバイルが重要である現在の環境では特に重要です。アプリケーション層のプロトコルとして、単一の通信で伝送される追加情報が多すぎるため、非効率的であることも明らかです。 WebSocket はモバイルのシナリオにより適していますが、PC で使用する場合は、多くの古いバージョンのブラウザーの互換性の問題を解決する必要があります。socket.io の登場により、この元々非常に複雑な問題が大幅に簡素化されました。 TCP プロトコルは従来のクライアント アプリケーションでよく使用されますが、WEB アプリケーションの場合は当然の障害があります。 WebSocket および TCP プロトコルを使用する利点は明らかであり、通信効率は HTTP プロトコルよりもはるかに高く、これら 2 つのプロトコルは二重通信をサポートします。

もう 1 つの問題は、このような高い同時読み取りと書き込みをサポートするために、オンライン担当者リストなどのデータ構造を保存するためにどのようなストレージ構造を使用する必要があるかです。最適化され SSD を使用するリレーショナル データベースのパフォーマンスは以前に比べて大幅に向上しましたが、頻繁に変更される多数のオンライン人物リストの場合、永続ストレージは実際にはほとんど意味がありません。したがって、memcache や redis など、読み取りおよび書き込みのパフォーマンスが高いメモリ ストレージがより現実的な選択となる可能性があります。 Memcache は単純な KV オブジェクト ストレージのみをサポートします。データの読み取りと書き込みには頻繁なシリアル化と逆シリアル化が必要ですが、Redis の利点は、リスト、ハッシュ、セットなどの豊富なデータ型を備えているため、その必要がなくなることです。

(クリックして画像を拡大)

図 5 redis Set に基づいて構築されたバケット ストレージ構造

メッセージ チャネル

HTTP プロトコル リクエスト/応答性の高い性質により、ブラウジング ビジネスの処理には適していますが、サーバーとの頻繁なやり取りが必要なインスタント メッセージングのシナリオには非常に適していません。生放送中、ユーザーはアンカーに苦情やコメントをすることができ、ユーザー同士で頻繁にコミュニケーションをとることもできます。このシナリオでは、リアルタイムのメッセージが特に重要です。

この種のシナリオを実現するには、アプリケーション サーバーを継続的にポーリングし、プル メソッドを使用して集中砲火とユーザー チャットの内容を読み取ることが最も単純かつ粗雑な方法です。メッセージのリアルタイム度は、プルとユーザーのチャットの頻度によって異なります。プルの進行状況が速すぎる場合、プルの頻度が低すぎると、サーバーがそれに耐えられなくなる可能性があります。ポーリング方法は粗すぎ、頻繁なサーバー要求が必要で、コストがかかり、ユーザーの情報更​​新頻度はリアルタイムで変化します。ユーザーがメッセージを送信する頻度は時間帯によって異なるため、より適切なポーリング時間を選択するのは困難です。大きな違いは、クライアントが取得した情報をフィルタリングして重複を排除する必要があることです。したがって、WEB 側のリアルタイム対話型アプリケーションの場合は、コミット サーバー プッシュや WebSocket を介した同様のシナリオなど、他のソリューションを使用する必要があります。

comet[1] は reverse ajax (Reverse AJAX) とも呼ばれ、ロングポーリング方式とストリーミング形式の 2 つの実装方式に分かれます。ロング ポーリング モードでは、クライアントはサーバーとの HTTP 接続を維持し、サーバーが情報を転送するか、HTTP 要求がタイムアウトになるまでブロックし、クライアントが応答を受信すると、別の接続が再確立されます。メソッドはストリームの形式です。サーバーはデータをクライアントにプッシュしますが、接続は閉じられず、接続がタイムアウトになるまで維持されます。クライアントは接続を再確立し、前の接続を閉じます。これら 2 つの方法により、HTTP プロトコルを使用してサーバーとクライアント間の即時通信を実現できます。

WebSocket[2] は IETF によって提案された新しいプロトコルで、ブラウザとサーバー間の全二重通信を実現することを目的としていますが、従来の HTTP プロトコルは一方向通信、つまりクライアントによって開始されたリクエストしか実現できませんでした。 Comet は双方向通信をある程度シミュレートできますが、通信効率は低く、特定のサーバー実装に依存します。

(画像をクリックすると拡大します)

図 6 WebSocket プロトコル [3]

Comet の通信効率が WebSocket よりも低いのはなぜですか?長いポーリングでは、サーバーがメッセージに応答した後に接続を再確立する必要があるため、追加のオーバーヘッドが発生します。

図 7 ロングポーリングと WebSocket メッセージ送信の比較

HTTP プロトコルのリクエスト ヘッダーには多くの情報が含まれていることはわかっていますが、含まれる情報の多くはシナリオによっては実際には必要なく、多くの帯域幅とネットワーク送信時間を無駄にします。 WebSocket プロトコルを使用すると、ブラウザとサーバーは 1 回のハンドシェイクで安定した通信チャネルを形成でき、フレームを介して両者間でデータを転送でき、メッセージ転送によって送信されるヘッダーも非常に小さいため、効率の向上がもたらされます。

図 8 websocket と Comet のパフォーマンスの比較

簡単なテスト比較は、Wireshark パケット キャプチャを通じて実行でき、サーバーが 1 秒あたり 50 メッセージをユーザーにプッシュし、各メッセージの長さが 10 バイトであると仮定します。 WebSocket と Comet という 2 つの異なる通信メカニズムを使用した場合の、さまざまなユーザー サイズに応じて、転送する必要があるバイト数を図 8 に示します。WebSocket プロトコルを使用して通信を行うと、ユーザーの規模とメッセージの量が増加することがわかります。通信効率が大幅に向上します。詳細なテスト プロセスについては、著者のブログを参照してください。

WebSocket プロトコルを導入すると、原理的にはブラウザとサーバー間のリアルタイム通信の効率の問題が解決されますが、HTTP プロトコルに基づいた実装である Comet と比較して、より優れたパフォーマンスを実現できますが、いくつかの問題も導入されます。新たな問題。最優先事項はブラウザの互換性です。WEB アプリケーションの開発において最も厄介な問題の 1 つは、ブラウザの複数のバージョンの互換性です。このプロトコルの実装についてはブラウザのメーカーごとに独自の理解があり、市場には依然として多くのブラウザが存在します。 HTML5 プロトコルをサポートしていない低レベルのブラウザーが多数あり、これらのユーザーが依然として中国で大きな基盤を占めているため、製品開発プロセスではこれらのブラウザーを考慮する必要があります。オープンソースのsocket.io[4]のおかげで、WebSocket、Adobe Flash Socket、ロングポーリング、ストリーミング、ポーリングなどのさまざまなメカニズムの適応スイッチングを通じて、ほとんどのブラウザの問題を解決することができました（ブラウザを含む）。さまざまなカーネル)、webview) の互換性の問題、クライアントとサーバーのプログラミング方法の統一。さまざまなプラットフォームでのメッセージ プッシュについては、メッセージ プッシュ、メッセージ サブスクリプション、シリアル化と逆シリアル化、接続管理、クラスター拡張などの作業をカプセル化するいくつかの成熟したテクノロジー プラットフォームも社内で開発しました。スペースの制限があるため、詳細については説明しません。ここ。 。

テキストコンテンツのフィルタリング

Double イレブンのライブビデオブロードキャストのもう 1 つの課題は、弾幕などの UGC コンテンツをどのようにフィルタリングするかです。過去の経験から、タオバオの場合、フィルタリングせずにコンテンツが直接公開された場合、間違いなくユーザーは全画面広告を見ることになり、大量の広告情報は一部の機能が利用できなくなる直接的な原因となります。したがって、テキストコンテンツのフィルタリングは私たちにとって基本的なスキルであると言えます。初期の頃、ゴミや広告コンテンツ、違法情報の特定は主に手作業に頼っていましたが、WEB2.0 DT の時代では、大量の情報を手作業で選別することは明らかに現実的ではありません。も進歩しており、一連の新しいテキストスクリーニングおよびフィルタリング技術がエンジニアリング分野に適用されています。

センシティブな単語のマッチング

長期的な蓄積により、大規模な Web サイトには通常、センシティブな単語のリストがあり、ユーザーが送信したコンテンツにセンシティブな単語が含まれている場合は、エスケープ (*** に変換) するか、公開を拒否する必要があります。 。では、テキストに機密用語が含まれているかどうかを判断し、機密用語をフィルタリングするにはどうすればよいでしょうか?機密性の高い単語が少数しかない場合、最も簡単な方法は、もちろん、キーワード検索アルゴリズムまたは正規表現を使用してそれらを照合することですが、実際の状況は明らかにさらに複雑で、フィルタリングが必要なキーワードが数千も存在する可能性があります。正規表現の効率は実際には比較的低く、特にシステムの非常に高いスループット能力を必要とする同時実行性の高いシナリオでは顕著です。したがって、このシナリオではより効率的なアルゴリズムが必要です。現在、空間と時間の計算量のバランスが取れている、トライ ツリー アルゴリズム、またはダブル アレイ トライ ツリー アルゴリズムなどのトライ アルゴリズムの変形を使用することがより一般的です。トライ ツリーは辞書ツリーまたは単語検索ツリーとも呼ばれ、その利点は、文字列の共通の接頭辞を使用してクエリ時間を短縮し、文字列比較の数を最小限に抑え、メモリ内でキーワードが占有する記憶領域を削減できることです。

図 9 トライ ツリー構造

Trie は本質的に、入力データに基づいて状態遷移を実行する有限状態マシンです。センシティブな単語には「アメリカ」、「美人」、「金貨」、「金」、「皇帝」が含まれ、入力テキストは「私のデスクメイトは美しい女の子です」であると仮定します。によると、この文字とそれに続く文字がリーフ ノードまでトライ木を検索すると、テキストに含まれる禁止単語「美しい」と、テキスト内でのこの単語の対応する位置と頻度がわかります。

もちろん、同じ親ノードを持つ単語を同じハッシュ テーブルに配置して、入力テキストに対してのみ必要なだけで、トライ ツリーの実装を簡素化することもできます。 to 文字を 1 つずつ入力して、対応するキーが含まれている場合は、最下位のリーフ ノードが見つかるまで検索を続けます。

図 10 マルチレベル ハッシュ テーブルはトライ ツリーの実装を簡素化します

システムがますますインテリジェントになるにつれて、悪意のあるユーザーもますます狡猾になり、「米国」などの機密単語のチェックを回避するためにテキストに干渉する文字が含まれる場合があります。テキストを検索し、干渉する文字をフィルタリングして除外し、一致させます。

クラスター環境では、アルゴリズムの実装に加えて、システムのスループットとマシンのメモリへの負荷も総合的に考慮する必要があります。これは、機密単語のフィルタリングは巨大な機密単語の辞書に依存する必要があり、辞書には必要な情報が必要となるためです。ツリーまたはマルチレベルのハッシュ テーブルは検索のためにメモリに配置されるため、必然的に多くのメモリ スペースが占有されます。したがって、メモリ リソースの使用率を向上させるために、ほとんどの場合、RPC モードを使用して機密ワード フィルタリング サービスを展開します。ただし、同時実行性が高いシナリオでは、機密ワード フィルタリングの導入によって生じる遅延を軽減し、システムのスループットを向上させます。 , 機密ワードのデータをローカル メモリにプッシュし、ローカル メモリ内のデータを読み取ることで RPC によって生じる遅延を軽減することも必要です。機密ワード ライブラリが更新されると、サーバーは対応する変更情報を他のアプリケーションにプッシュする必要があります。

分類アルゴリズム

分類とは、実際には、特定の基準に従ってオブジェクトにラベルを付け、そのラベルに基づいてそれらを区別することを意味します。確率統計に基づくベイズ分類アルゴリズム [5] は、最も一般的な分類アルゴリズムであり、現在も使用されています。ガベージ テキスト認識 この分野で最も広く使用されているアルゴリズム。

ベイジアン分類アルゴリズムを使用したバイナリ分類は、次の手順に大別できます:

1. 大量のガベージ コンテンツと非スパム コンテンツ コーパスを収集し、トレーニング ガベージ コーパスと通常のコンテンツ コーパスを確立します。
2. コーパステキストのコードセグメント化、独立した文字列の抽出、テキスト内に出現する文字列の頻度をカウントします。
3. 各トレーニング コーパスは、ハッシュ テーブルに対応します。たとえば、ガベージ コーパスは hashtable_bad に配置され、非ジャンク コーパスは、単語分割によって抽出された文字列と、対応する単語の頻度がハッシュ テーブルに格納されます。
4. ハッシュテーブル内のすべての文字列の出現確率、つまり P = 文字列の単語頻度 / 文字列の総数を計算します。
5. hashtable_good と hashtable_bad に基づいて、テキストの文字列に特定の文字列が含まれる場合、そのテキストがジャンク コンテンツである確率は次のように推定されます。 対応する数式は次のとおりです。 P (A|k i ) = P bad (ki i ) ) / [ P good (ki) +P bad (ki )]、イベント A はテキストがスパムであることを示し、k 1 、k 2 ... k n は抽出されたキーワードを表し、P (A|ki )キーワードがテキスト内に出現することを示します。 k i のとき、テキストがジャンク コンテンツである確率、P bad (ki ) は hashtable_bad の ti の値、P Good (ki ) は hashtable_good の k i の値です。
6. 新しい hashtable_probability を作成して、文字列 k i から P(A|k i) へのマッピングを保存します。

この時点で、ベイズ分類のトレーニングと学習プロセスが完了します。次に、テキストがスパムである可能性を hashtable_probability に基づいて計算できます。ユーザーが送信したテキスト コンテンツが分割されて n 個のキーワード k 1 、 k 2 、 k 3 ...... k n が取得されるとします。hashtable_probability の対応する値は P 1 、 P 2 ... です。 P n ,P(A|k 1 ,k 2 ,k 3 ……k n ) は、キーワード k 1 ,k 2 ,k 3 ……k n がテキスト内に同時に出現する場合に、この段落の内容がジャンク テキストである確率を表します。ユーザーによって送信された、P(A|k 1 ,k 2 , k 3...k n ) =P 1 *P 2 *...P n 。 P(A|k 1 ,k 2 ,k 3 ...k n )が所定の閾値を超えた場合、そのコンテンツはスパムであると判断でき、その閾値を調整することにより、スパム対策システムによるコンテンツフィルタリングの厳しさを調整することができる。制御されている。

もちろん、上記は単純な 2 つのカテゴリの状況にすぎませんが、コーパスの強化により、ジャンク コーパスは詐欺、広告、ポルノ、悪口、個人攻撃などに細分化され、使用シナリオが異なると、テキスト内のジャンク テキストに対する許容範囲が異なるため、必然的に誤って削除される可能性が高まり、特定のシナリオでは一部のコーパスがジャンク広告に属する可能性があります。他のシナリオでは、通常のコンテンツである可能性があります。たとえば、電子商取引 Web サイトの評価で QQ、WeChat、電話、その他の連絡先情報が見つかった場合、それは広告コンテンツである可能性が高くなりますが、ソーシャル アプリケーションの場合は通常のコンテンツです。さらに、確率計算への干渉を減らすために、いくつかの一般的な単語をフィルタリングする必要があります。たとえば、特定のキーワードが出現すると、そのような単語の重みが大幅に増加する可能性があります。が増えました。

ベイジアン アルゴリズムの利点は、コーパスが強化され続けるにつれて、悪意のあるユーザーの無限の「新しいトリック」に対処できることです。トレーニングに基づいて、アルゴリズム モデルは既知の種類のスパム コンテンツを検出できますが、新しい種類のスパムについては何もできないため、外部の介入が必要です。手動の注釈または他の方法 (テキストの重複判定など) を通じて、新しいジャンク テキスト タイプを発見し、トレーニング コーパスを充実させることができます。コーパスが充実するにつれて、認識の精度はますます高くなり、悪意のあるユーザーと戦う過程でシステムの能力はますます強力になります。

ユーザーをブラックリストに登録する

悪意のある情報を頻繁に送信するユーザーに対しては、一定期間または永久にアクセスを禁止することで対処できます。この方法では、ユーザーが UGC コンテンツを送信するときに、まずユーザーのブラックリストを維持する必要があります。ブラックリストに追加されている場合は、公開を拒否します。

ブラックリストを実装する最も簡単な方法は、ハッシュ テーブルを使用し、メモリ キャッシュ用に redis ハッシュなどのデータ構造を借用し、ダウンタイムによるデータ損失を防ぐために定期的な永続化またはデータ バックアップを実行することです。この方法の実装はシンプルで、クエリ効率は比較的高く、ほとんどのシナリオのニーズを満たすことができますが、ビジネスで必要な場合には、ハッシュ テーブル メソッドが占有するメモリ スペースも増加します。さらに、ブラックリストが大きくなるほど、ハッシュの競合が多くなり、クエリの効率も低下します。ブラックリスト フィルタリングの要件がそれほど正確ではない場合は、ブルーム フィルタ [6] ソリューションを使用できます。

図 11 ブルーム フィルターの基本原理 [7]

ブルーム フィルターは、初期状態では、配列のすべてのビットが 0 に設定されます。ブラックリストを設定する必要がある場合、一連の異なるハッシュ関数が使用されます。ハッシュ関数は、対応する入力要素を配列内のビットにマップし、配列の対応する位置を 1 に設定します。同じハッシュ関数で対応するビットが見つかった場合、そのビットがすべて 1 でない場合、そのユーザーはブラックリストに含まれていないことを意味します。次に、すべてのビットが 1 である場合、そのユーザーは確実にブラックリストに含まれていることを意味します。ブラックリストに載ってる？必ずしもそうとは限りません。図 11 に示すように、他のいくつかのユーザー入力がすべてのビットを 1 に設定しているだけである可能性があります。x、y、z の 3 つの要素を挿入して w をクエリすると、w が次のようになります。それらの中に含まれておらず、3 つのハッシュ関数によって計算された w のインデックスのビットがすべて 1 である場合、ブルーム フィルターは w がセット内にあることを示します。実際、これは偽陽性です。 w がセットに含まれていないということは、いわゆる偽陽性を意味します。確率の観点から見ると、誤検知の確率は非常に低く、システムの許容範囲内にあります。100% 正確な判断が必要な場合、ブルーム フィルターは適していません。

基本的なブルーム フィルターは削除操作をサポートしていません。Counting Bloom Filter の登場により、標準のブルーム フィルターのビット配列の各ビットが、要素の挿入時に対応する小さなカウンター (Counter) に拡張されます。 k 個のカウンタ (k はハッシュ関数の数) がそれぞれ 1 ずつ増加します。要素を削除すると、対応する k 個のカウンタの値がそれぞれ 1 ずつ減少します。 Counting Bloom Filter の値に 1 を加算します。削除操作が追加されていますが、ハッシュ テーブルと比較すると、格納効率は大幅に向上しています。

図 12 カウンティング ブルーム フィルターの基本原理[8]

システムの安定性

毎年恒例のダブル イレブンでは、高トラフィックおよび高同時実行のシナリオでシステムがダウンタイムなしで安定したサービスを提供することを保証する方法が検討されてきました。は永遠のテーマであり、技術担当者の徹底的な見直しが毎年行われています。パフォーマンスの最適化、依存関係のソート、大規模なプロモーション開始前のピーク評価から、システムのストレス テスト、新しいマシンの調達とオンライン、フロー制御しきい値の評価、スイッチ構成のダウングレード、データ収集の監視、災害復旧緊急計画まで。 、包括的なリンク ストレス テスト、演習、リアルタイムおよびオフラインのデータ分析など、インターネット上に関連する記事がたくさんあると思うので、ここでは詳しく説明しません。

概要

この記事では、主に、ダブル イレブン期間中にアリババのライブ ブロードキャスト プラットフォームが直面したいくつかの技術的課題と、音声とビデオのライブ ブロードキャスト アーキテクチャから、集中砲火やメッセージ配信、メッセージ チャネル テクノロジーの選択とテキスト フィルタリングの実装メカニズムは、オーディオとビデオの信頼性の保証、ビデオ ポルノの検出、数万のオンライン ユーザーによる増幅後のテキスト メッセージのダウンリンクなど、大規模なライブ ブロードキャストですべて直面します。 、そしてメッセージの内容自体のフィルタリングは大きな挑戦ですが、それは恐ろしい挑戦ではありません、それを阻むのは兵士であり、水が来てそれを覆うときだけ、私たちは立ち向かうことで突破口と革新を達成することができます。困難に。

参考資料

comet、https://software.intel.com/zh-cn/articles/comet-java-realtime-system-essay
WebSocket、https://tools.ietf.org/html/rfc6455
WebSocket 通信原理
socket.io プロジェクト アドレス: http://socket.io/
ベイズ分類、https://en.wikipedia.org/wiki/Naive_Bayes_classifier
ブルーム フィルター、http://my. oschina.net/kiwivip/blog/133498
画像ソース、http://my.oschina.net/kiwivip/blog/133498
画像ソース、http://my.oschina.net/kiwivip/blog /133498

著者について

淘宝網では龍龍という愛称を持つ陳康賢は、淘宝網技術部門の技術専門家であり、『大規模分散 Web サイトのアーキテクチャ設計と実践』という本の著者であり、分散システム アーキテクチャの専門知識を持っています。システムの安定性保証の分野で豊富な実務経験を積んでおり、新しいテクノロジーに強い関心を持っています。連絡や履歴書については、longlong@taabao.com までご連絡ください。

この記事をレビューしてくれた Guo Lei に感謝します。

InfoQ 中国語 Web サイトに記事を投稿したり、コンテンツの翻訳に参加するには、editors@cn.infoq.com に電子メールを送信してください。また、Sina Weibo (@InfoQ、@丁晓昀)、WeChat (WeChat ID: InfoQChina) を通じて私たちをフォローし、編集者や他の読者とコミュニケーションをとることも歓迎します (InfoQ 読者交換グループ (フル)、InfoQ 読者交換グループへの参加を歓迎します)グループ (#2) )。