エンジニアリングの観点からYandexを検索します。 Yandexでの講義

本日、夏の会議で行われたYandex検索デバイスに関する別のレポートを公開します。 その日のランキング部門長であるペトルポポフのスピーチは、幅広い聴衆にとって最もアクセスしやすいものであることが判明しました。つまり、最小限の公式、最大限の検索に関する一般的な概念です。 しかし、Peterは何度も詳細に目を通し、その結果、Yandexがこれまでに公表したことがないことについて多くのことを語ったため、誰にとっても興味深いものでした。

ちなみに、この復号化の公開と同時に、Yandexテクノロジーに特化したシリーズで2回目の会議が始まります。 今日のイベントは、もはや検索に関するものではなく、インフラストラクチャに関するものです。 こちらがブロードキャストリンクです。


さて、カットの下で-ピーターポポフとスライドの一部による講義。

---

私の名前はピーター・ポポフ、私はヤンデックスで働いています。 私はここに7年ほどいます。 それ以前は、コンピューターゲームをプログラミングし、3Dグラフィックスに従事し、ビデオカードを知っており、SSEアセンブラーに書いていました。一般的に、彼はそのようなことに従事していました。

Yandexで仕事に就いたとき、私はこの分野についてはほとんど知りませんでした-ここで人々が何をするかについて。 良い人がここで働くことしか知りませんでした。 したがって、いくつかの疑問がありました。



ここで、私たちの検索がどのように見えるかについて、非常に深くではなく、完全に説明します。 Yandexとは何ですか？ これは検索エンジンです。 ユーザーリクエストを受け取り、多数の結果を作成する必要があります。 なぜトップ10なのか？ ユーザーが他のページにアクセスすることはほとんどありません。 10個のドキュメントがすべて表示されていると想定できます。

メインのYandex製品は完全に異なると信じているため、Yandexの広告に携わっている人々がホールにいるかどうかはわかりません。 いつものように、2つの視点があり、両方とも正しいです。

私たちは、主なことはユーザーの幸せだと信じています。 そして、驚くべきことに、この幸福は、10の構成と10のランク付けに依存します。 発行が悪化すると、ユーザーはYandexの使用を減らし、他の検索エンジンにアクセスして、気分が悪くなります。



この単純なタスクを解決するために、10個のドキュメントを表示するためにどのような設計を作成しましたか？ 設計は非常に強力で、下から見たところ、開発者はそれを見ているようです。

私たちの作業モデル。 いくつかのことをするだけです。 インターネットを巡回し、作成されたドキュメントのインデックスを作成する必要があります。 ダウンロードしたWebページと呼ばれるドキュメント。 インデックスを作成し、検索インデックスに追加し、このインデックスに対して検索プログラムを実行し、ユーザーに応答します。 一般的に、それはすべて、利益です。

このコンベアの手順を見ていきましょう。 インターネットとは何ですか？ インターネット、カウント、無限です。 何かを販売しているサイト、オンラインストア、並べ替えオプションを変更すると、別のページが表示されます。 つまり、ページのCGI​​パラメーターを設定でき、コンテンツはまったく異なります。

重要でないCGIパラメーターを破棄するまでに、基本的に重要なページをいくつ知っていますか？ 今-約数兆。 1日に数十億ページ程度の速度でページをダウンロードします。 そして、2年で有限の時間で作業を完了することができるように思われます。

インターネットで新しいページを見つけるにはどうすればいいですか？ いくつかのページを回って、そこからリンクを引き出しました。 彼らは私たちのダウンロードの潜在的な犠牲者です。 おそらく2年以内にこれらの数兆のURLをバイパスしますが、新しいURLが表示され、ドキュメントを解析する過程で新しいページへのリンクが表示されます。 ここで、私たちの主なタスクがインターネットの無限に対処することであり、データセンターの形で究極のエンジニアリングリソースを手に持つことはすでに明らかです。

インデックスに登録された膨大な数のドキュメントをすべてダウンロードしました。 次に、それらを検索インデックスに入れる必要があります。 すべてをインデックスに入れるのではなく、ダウンロードしたものの中で最高のものだけを入れます。



インターネット検索エンジンの狭いサークルの有名な専門家である同志、アシュマノフがいます。 彼は、検索エンジンのさまざまな品質のグラフを作成します。 これは、検索ベースの完全性のグラフです。 どのように構築されていますか？ リクエストはまれな単語から作成され、すべての検索エンジンにあるドキュメントを検索します。これは100％です。 すべての検索エンジンは共有について知っています。 私たちの主な競争相手は、上下が赤、黒が赤です。

ここで疑問に思うかもしれません：これをどのように達成したのでしょうか？ 可能な答えがいくつかあります。 オプション1：これらのテストを使用してページを解析し、すべてのURL、同志Ashmanovが要求し、ページにインデックスを付けたすべてのリクエストを抽出しました。 いいえ、そうしませんでした。 2番目の選択肢：私たちにとって、ロシアは主要市場であり、競合他社にとっては、視野の周辺のどこかにある、わずかなものです。 この答えには命の権利がありますが、私も好きではありません。

私が好きな答えは、私たちは多くのエンジニアリング作業を行い、「ビッグベース」と呼ばれるプロジェクトを行い、そのために多くの鉄を購入し、現在この結果を見ているということです。 競争相手もbeatられます、それは鉄ではありません。



ドキュメントをダウンロードしました。 どのようにして検索ベースを構築しますか？ コンテンツシステムの図を次に示します。 インターネット、ドキュメントのクラウドがあります。 彼を迂回する車があります-クモ、クモ。 ドキュメントをダウンロードしました。 はじめに-保存したコピーに入れます。 これは、実際には別のセンター間ハッシュテーブルであり、後でこのドキュメントのインデックスを作成したり、配信時に保存されたコピーとしてユーザーを表示したりする場合に読み書きできます。

次に、ドキュメントのインデックスを作成し、言語を定義し、言語の形態に応じて主要な形式に縮小した単語を引き出しました。 また、他のページへのリンクを引き出しました。

インデックスを作成するとき、および一般的にランキングで広く使用する別のデータソースがあります-Yandexログ。 ユーザーはリクエストを要求し、多数の結果を受け取り、何らかの形でそこで動作します。 彼にはドキュメントが表示され、クリックするかクリックしないかのどちらかです。

文書が検索結果に表示された場合、またはユーザーがそれをクリックした場合、何らかの相互作用があった場合、そのような文書は検索データベースに残されるべきであると仮定するのは合理的です。 さらに、このような優れたドキュメントからのリンクからも優れたドキュメントが得られ、ダウンロードの優先度が高いと想定するのは理にかなっています。 これがツアーの計画です。 バイパス計画からの矢印は、バイパスにつながるはずです。

次は、検索インデックスを作成する段階です。 これらの角丸長方形は、 YT、Yandex Tableと呼ばれるMapReduceの独自の実装であるMapReduceにあります。 ここで少しニスをかけます-実際、ベースの構築とシャーディングはファイルと同様にインデックスで動作します。 少し修正します。 これらの角丸長方形はMapReduceにあります。 ここでのデータの合計量は約50 PBです。 ここで、それらは検索インデックス、ファイルに変わります。

この回路には問題があります。 主な理由は、MapReduceが純粋に戦闘操作であるという事実によるものです。 たとえば、クロールの優先順位のドキュメントを決定するために、リンクグラフ全体を取得し、すべてのユーザーの動作でそれをwezhimし、ジャンプのキューを形成します。 このプロセスは非常に潜在的で、時間がかかります。 インデックスの構築とまったく同じです。 処理段階があります-それらはベース全体のバッチです。 そして、レイアウトも調整されます。デルタをレイアウトするか、それだけです。

これらのボリュームの重要なタスクは、インデックス配信手順を高速化することです。 このタスクは私たちにとって難しいと言わなければなりません。 私たちは、基地建設のバッチキャラクターとの戦いについて話している。 あらゆる種類のニュースをリアルタイムでダウンロードし、ユーザーに通知する特別なクイックサーキットがあります。 これが私たちの仕事です。



そして、これがコインの裏面です。 1つ目はコンテンツシステム、2つ目は検索です。 私がピラミッドを描いた理由を理解することができます-Yandexの検索は本当にピラミッドのように見えるので、このような階層構造です。 上記はバランサーであり、引き渡しを生成するフロントです。 もう少し-さまざまな分野からの発行を集約するメタサーチを集約します。 引き渡しで、おそらくウェブ文書、ビデオ、写真を見たと言わなければなりません。 3つの異なるインデックスがあり、それらは独立して調査されます。

各検索クエリはこの階層を下って行き、検索ベースの各部分に行きます。 構築したインデックス全体を数千個に分割しました。 条件付きで、2〜3〜5千。 検索はすべてのピースに対して解除され、このクエリはどこにでも行きました。



Yandexの検索が大きなものであることがすぐにわかります。 なぜ彼女は大きいのですか？ 前のスライドで見たように、かなり代表的で強力なインターネットの一部であるため、記憶を保持しているためです。 複数のデータセンターに保存します。各データセンターには、インデックスのコピーを2〜4個保存します。 クエリは各検索に渡り、実際には各インデックスを検索します。 現在、使用されるデータ構造は、これらすべてをRAMに直接保存することを余儀なくされるようなものです。



何をする必要がありますか？ 高価なRAMの代わりに、安価なSSDを使用して、検索を2倍に高速化し、数千または数億ドルの資本コストの利益を得ます。 しかし、言う必要はありません：危機、Yandexはすべてを保存します。 実際、保存したものはすべて、有用な仕事に費やします。 インデックスを2倍にします。 よりよく検索します。 そして、このような複雑なエンジニアが実行されている理由です。 これは実際のプロジェクトですが、かなり重くて遅いですが、本当に改善しています。検索を改善したいのです。

検索クラスターは十分に大きいだけでなく、非常に複雑です。 さまざまなプログラムの何百万ものインスタンスが実際にそこで回転しています。 最初に書いたのは、数十万人でしたが、作戦の仲間が私を修正しました。 非常に多くのコピーの各マシンで、10〜20個が正確に回転しています。

数千の異なる種類のサービスがクラスタ全体に広がっています。 明確にする必要があります。クラスタは、そのようなマシン、ホスト、プログラムで実行されており、それらはすべてTCP / IPを介して通信します。 プログラムは、CPU、メモリ、ハードドライブ、ネットワークの消費量が異なります。要するに、これらすべてのリソースです。 プログラムはホステルのホステルに住んでいます。 より正確には、1つのプログラムをホストに配置すると、クラスターの使用率はなくなります。 したがって、私たちはお互いにプログラムを提出せざるを得ません。

それをどうするかについての次のスライド。 そして、ここでは、すべてのプログラムデータ、トレントを使用したすべてのリリースをダウンロードし、トレントトラッカーのディストリビューションの数がPirate Bayのディストリビューションの数を超えているという小さなコメントがあります。 私たちは本当に大きいです。

このすべてのクラスター設計で何をする必要がありますか？ 仮想化メカニズムを改善する必要があります。 Linuxカーネルの開発に本当に投資しています。Dockerに似た独自のコンテナ管理システムがあります。Olegがそれについて詳しく説明します。

どのホストがどのプログラムを相互にホストするかを事前に計画する必要がありますが、これも難しいタスクです。 私たちは常にクラスターに行きます。 現在、おそらく10個のリリースがリリースされています。

プログラムを相互に正しく展開する必要があります。仮想化を改善する必要があります。ロボットと検索クラスターという2つの大きなクラスターを組み合わせる必要があります。 私たちはどういうわけか鉄を注文し、膨大な数のディスクを備えた別々のマシンと別々に-検索用の薄いブレードがあると考えました。 統合されたハードウェアを注文し、MapReduceと検索プログラムを単独で実行する方がよいことがわかりました。1つは主にドライブとネットワークを使用し、2つ目は主にCPUを使用しますが、CPUのバランスが取れているため、前後に調整する必要があります。 これらは、私たちも実施している大規模なエンジニアリングプロジェクトです。

これから何が得られますか？ 資本コストの節約における数千万ドルの利点。 あなたはすでにこのお金をどのように使うか知っています-私たちはそれを検索の改善に使います。

ここで、デザイン全体について説明しました。 いくつかの別個の構成要素。 人々はノミでこれらのブロックを爆破し、彼らは何かをしました。



ランキング関数マトリックス。 かなりシンプルな機能。 あなたは読むことができます-ベクターにはドキュメントのバイナリ記号があり、このサイクルでは関連性が計算されます。 私はあなたの中にSSEでプログラムできる専門家がいると確信しています。そして彼らはこれを10倍速くしたでしょう。 そのため、ある時点でそれが起こりました。 数千行のコードにより、クラスターの合計CPU消費量の10〜15％が節約されました。これも、使用方法がわかっている数千万ドルの資本コストに相当します。 これは数千行のコードであり、非常に高価です。

多かれ少なかれリポジトリからそれをきれいにし、最適化しましたが、まだやるべきことがあります。

機械学習のためのプラットフォームがあります。 前のスライドのインデックスを貪欲に選択し、すべての可能性をソートする必要があります。 これはCPUで長時間かかります。 GPUで-すぐに、ただしトレーニングプールはメモリに入りません。 何をする必要がありますか？ または、これらのグランドの多くが詰まっているカスタムソリューションを購入するか、マシンをすばやく接続し、ある種の相互接続、インフィニバンドを使用して、それと一緒に暮らすことを学びます。 通常はバグが多く、機能しません。 これは非常に面白いエンジニアリングの課題であり、私たちも直面しています。 それは私たちの主な活動とはまったく関係がないように思えますが、それでもなおそうです。



まだ投資しているのは、データ圧縮アルゴリズムです。 圧縮の主なタスクは次のようになります。整数のシーケンスがあり、何らかの方法で圧縮する必要がありますが、圧縮するだけでなく、i番目の要素へのランダムアクセスも必要です。 典型的なアルゴリズムは、これを小さなブロックに圧縮して、共通のデータストリームのマークアップを作成することです。 このようなタスクは、zipやLZファミリのようなコンテキスト圧縮とはまったく異なります。 完全に異なるアルゴリズムがあります。 ハフマン、Varlnt、PFORXなどのブロックで圧縮できます。 独自の独自のアルゴリズムがあり、それを改善していますが、これも単純なアルゴリズムでのRAM節約の10〜15％です。

CPU、Linuxスケジューラーの改善など、あらゆる種類の面白い小さなものがあります。 Intelのハイパーストーンの問題点は何ですか？ 物理コアに2つのスレッドがあること。 2つのスレッドが2つのスレッドを占有すると、動作が遅くなり、遅延が増加します。 物理プロセッサにタスクを正しく分散させる必要があります。

ストックプランナのように正しく投げない場合、条件付きでリクエストの10〜15％のレイテンシを得ることができます。 これはユーザーに表示されるものです。 保存されたミリ秒に検索数を掛けます。これがユーザーの保存時間です。

実際には機能しないmallocの独自の実装など、いくつかの非常に奇妙なものがあります。 それはアリーナで動作し、各場所は単にこのアリーナ内でポインタを動かします。 さて、アリーナのrefカウンターは1つ上がります。 アリーナは生きていますが、最後の場所は生きています。 混合負荷の場合、短命と長命の場所がある場合、これは機能せず、メモリリークのように見えます。 ただし、サーバープログラムはそのように配置されていません。 リクエストが到着し、そこに内部構造を割り当てて、何らかの形で機能し、ユーザーに答えを出すと、すべてが破壊されます。 このアロケーターは、ステートレスサーバープログラムに最適です。 すべての場所はローカルであり、アリーナ内で一貫しているため、非常に迅速に機能します。 ページフォールト、キャッシュミスなどはありません。非常に高速です。これは、一般的なサーバープログラムの速度の5％〜25％です。

これはエンジニアですが、他に何ができますか？ 機械学習を行うことができます。 サーシャ・サフロノフは 、これについて愛をもって語ります。

次に質問と回答。

私は、ニュースレターに来て、私のプレゼンテーションに含めるべき非常に気に入った質問に答えます。 アナトリー・ドラプコフ同志は尋ねます。MatrixNetの導入前に式がどれほど速く成長したかについて有名なスライドがあります。 実際、前と後の両方。 現在、成長の問題はありますか？

完全な成長で直面する成長の問題。 ランキング式で反復回数を増やす次の順序。 現在、ユーザーに応答するためにMatrixNet関数で約20万回の反復を行っています。 次のエンジニアリングステップで取得されました。 以前はベースでランク付けしていました。 つまり、基本的なものはそれぞれMatrixnetを起動し、100の結果を生成します。 私たちは言った：平均で最高の100の結果を組み合わせて、非常に難しい式でもう一度整理しましょう。 はい、平均して、必要なリソースが千倍少ないため、複数のスレッドでMatrixNet関数を計算できます。 これは、ランキング関数のボリュームを増やすという次の順序を達成できるプロジェクトです。 他に何が起こる-私は知りません。

Yandex Search Products Departmentの責任者、Andrey Styskin氏：
-最初のYandexランキング式は何バイトを占有しましたか？

ピーター：
-ダース、おそらく。

アンドリュー：
「ええ、はい、おそらくどこかで100文字です。」 そして、Yandexランキング式は今どのくらいかかりますか？

ピーター：
-どこか100 MB。

アンドリュー：
-関連式。 これは、ウェブマスター、SEOエキスパート向けです。 100MBランキングをリエンジニアリングしてみてください。

Alesya Bolgova、Intel：
-mallocに関する最後のスライドによると、メモリの割り当て方法について説明していただけますか？ とても興味深い。

ピーター：
-通常のページ（4 KB）が開始され、最初に回転カウンターがあり、各割り当てがあります...小さい割り当てがページ未満の場合、このページに移動します。 もちろん、各スレッドには、このページに独自のページがあります。 ページが閉じられたとき-それだけです、彼らはそれを忘れていました。 彼女が持っている唯一のものは、最初の回転カウンターです。

アレシア：
-では、ページを強調表示しますか？

ピーター：
-割り当てのあるページ内では、このように成長します。 唯一のことは、ページ内の最後の割り当てが存続する限りページが存続することです。 通常のワークロードの場合はリークのように見えますが、私たちの場合は通常のジョブのように見えます。

-ページの品質をどのように判断しますか。インデックスに入れる価値がありますか？ 機械学習も？

ピーター：
「はい、もちろん。」 ページには、そのサイズから検索のインプレッションまで、多くの要因があります...

アンドリュー：
-ロボットのランクへ。 いくつかのホスト、いくつかのホストサブディレクトリにあり、そこへのいくつかの着信リンクがあります。 それを参照する人はある程度の品質を持っています。 このすべてを取得し、どの確率で予測しようとします。このページがダウンロードされた場合、問題の何らかのリクエストに応じる情報が含まれます。 , — , - , . . .

— …

:
— .

— , ?

:
— , Mail.Ru.

:
— — . , . , , , , , …

:
— , . , . , — -. 30 , . .

:
— .

:
— , , .

:
-わかった。 — ? , ?

:
— , , . , , — .

:
— . , .

:
— , — , . , .

:
— , . : , , Lenta.ru. Lenta.ru, . . , .

:
— , 3-4 .

:
— , , real time.

:
— ?

:
— -, , .

:
— .

:
— . — , . — , , , - . .

:
— , , , ? , , ? : «Google». , . , -, - …

:
— , .

:
— , . , , . , , , . — , , , - , . «Google», Google - , , . .

:
— , . , .

:
— , , , : , - . , , , .

:
— : . , , .

:
— , «», , — , , , , .

:
— , .

:
— , , , . , . , - ?

:
— . : - , , , . « », , .

:
— — . , CPU- . Xeon Phi Intel? , GPU.

:
— , , . , - 1,5%. , , , ++-, .

— , , . , - ?

:
— . , , . , , , . , .

:
— . , , - , . , , , , , — . -, .

:
— , .

():
— , . deep learning ? -, ?

:
— Deep learning , . . , .

:
— , 0,5% , deep learning . - , , .

:
— , , -100 . . .

:
— deep learning , , , — .

:
— . , , , . , 10 , , ? , , 10 ?

:
— , - . .

:
— . , . , , , , , , , .

:
— 10 — , , .

():
— , , ?

:
— — 50 , , . , . , .

:
— ?

:
— — torrent, torrent share. .

:
— - ?

:
— , . , , .

:
— F5 — , …

:
— , , .

:
— - ?

:
— , , .

:
— .

:
— . , , , , , - . , , .

:
— . , , , . - — , - , — . DDoS .

, Sphinx Search:
— . — ? SSD , - , SSD?


— , 50-100 , . , . , . , . , .

:
— bandwidth latency?

:
— . , .

:
— , : -…

:
— , - — .

:
— ?

:
-はい、はい。

:
— : ?

:
— .

:
— .

:
— , . .

:
— - ?

:
— , , - .

:
— , …

:
— .

:
— ?

:
— - .

:
— , , .

:
— . , .

:
— ?

:
— .

:
— , .

:
— . . , ?

:
— , . … -, 250 , 95- . , - 700 .

:
— , JavaScript, 250 , 700.

:
— , , . .

:
— . , . ?

:
— , , , . .

:
— , , . , , , , , .

:
— , . , .

:
— , , ?

:
— . , , .

:
— real time, - . up . , .

:
— , .

:
— , , real time?

:
— , . , .

:
— , - , ?

:
— , . , .

:
— ?

:
— . , . , , . .

:
— ? , , ?

:
-キャッシュはありますが、ケースの50％で機能します。ユーザー要求の40〜50％は一意であり、二度と尋ねられることはありません。一般的に、Yandexの生涯を通じて多くの真にユニークなユーザーリクエスト。50〜60％をキャッシュします。キャッシング用のシステムもあります。