ビデオを報告する

テキスト版

2年前のルーブル為替レートの変化により、Mail.Ru Mailの鉄のコストを削減する方法について考えさせられました。 購入したハードウェアの量とホスティングの価格を削減する必要がありました。 保存する場所を見つけるために、メールの構成を見てみましょう。









インデックスと文字の本文がボリュームの15％、ファイル-85％を占めています。 最適化のための場所をファイル（文字の添付ファイル）で探す必要があります。 当時、ファイルの重複排除は実装されていませんでした。 見積もりによると、メール全体の36％を節約できます。同じ手紙が多くのユーザーに届きます（写真付きのソーシャルネットワーク、価格表付きのショップなど）。 この投稿では、 PSIAltのリーダーシップの下で行われたこのようなシステムの実装について説明します。

メタ情報リポジトリ

ファイルのストリームがあり、ファイルが重複しているかどうかをすばやく理解する必要があります。 簡単な解決策は、ファイルの内容に基づいて生成される名前を付けることです。 sha1を使用しています。 元のファイル名はレター自体に保存されるため、面倒を見る必要はありません。



レターを受け取り、ファイルを取得し、sha1の内容から計算し、計算の値をレターに追加しました。 これは、レターを送信するときに将来のリポジトリで簡単にファイルを見つけられるようにするために必要です。



ここでファイルを埋めます。 リポジトリに問い合わせることに興味があります：sha1のファイルはありますか？ これは、すべてのsha1をメモリに保存する必要があることを意味します。 fileDBストレージの場所に名前を付けましょう。







同じファイルを異なる文字にすることができます。 したがって、このようなファイルの文字数のカウンターを保持します。







ファイルを追加すると、カウンターが増加します。 ファイルの約40％が削除されます。 したがって、ファイルがクラウドにアップロードされているレターを削除する場合は、カウンターを減らす必要があります。 0に達すると、ファイルを削除できます。



ここで最初の問題に直面します。文字（インデックス）に関する情報はあるシステムにあり、ファイルに関する情報は別のシステムにあります。 これにより、たとえば次のようなエラーが発生する場合があります。

1. 手紙を削除する要求が来ます。
2. システムは文字インデックスを上げます。
3. 彼はファイル（sha1）があることを確認します。
4. ファイルを削除する要求を送信します。
5. 障害が発生し、メッセージは削除されません。

この場合、文字はシステムに残り、カウンターは1つ減少しました。 この手紙の削除が2回目になった場合、カウンターを再び減らして問題を取得します。 ファイルはもう1文字であり、そのカウンターはゼロです。







データを失わないことが重要です。 ユーザーがレターを開いても、ファイルが存在しないという状況を許可することはできません。 同時に、ディスクに少し余分なファイルを保存しても問題はありません。 カウンターがゼロに正しく減少したかどうかを明確に示すメカニズムがあれば十分です。 これを行うために、別のフィールド-マジックがありました。







アルゴリズムは簡単です。 レターでは、ファイルのsha1とともに、もう1つの任意の数値を生成して保存します。 ファイルの入力または削除の要求はすべて、この番号で行われます。 フィルリクエストが受信された場合、保存されているマジックにこの番号を追加します。 削除する場合は、削除します。



したがって、すべての文字が正しい回数だけカウンターを増減すると、魔法もゼロになります。 ゼロ以外の場合、ファイルを削除できません。



例を見てみましょう。 sha1ファイルがあります。 一度フラッディングされ、文字を入力すると、345に等しい乱数（マジック）が生成されます。







今、同じファイルで別の手紙が届きます。 マジック（123）を生成し、ファイルをアップロードします。 新しいマジックが古いマジックに追加され、カウンターが1つ増えます。 その結果、FileDBではsha1のマジックは468になり、カウンター-2になりました。







ユーザーは2番目の文字を削除します。 2番目の文字に格納されている魔法は現在の魔法から差し引かれ、カウンターが1つ減ります。







まず、すべてが順調に進んでいる状況を考えます。 ユーザーは最初の文字を削除します。 その後、魔法とカウンターはゼロになります。 そのため、データは一貫しているため、ファイルを削除できます。







何かがうまくいかなかったとしましょう。最初の文字は2つの削除コマンドを送信しました。 カウンター（0）はファイルへのリンクがないことを示しますが、マジック（222）は問題を通知します。データが一貫した状態になるまでファイルを削除することはできません。







状況を完成させて、最初の文字が削除されたと仮定しましょう。 この場合、魔法（–123）は依然としてデータの不整合を意味します。







信頼性のために、カウンターがゼロになり、マジックが（この場合、マジック= 222、カウンター= 0）ではない場合、ファイルは「削除しない」フラグに設定されます。 そのため、多くの追加と削除の後、偶然の一致によって、マジックとカウンターがゼロになったとしても、ファイルに問題があり、削除できないことがわかります。



FileDBに戻ります。 エンティティにはフラグがあります。 あなたが計画しているかどうかにかかわらず、彼らは必要になります。 たとえば、ファイルを削除不可としてマークする必要があります。







主なものを除いて、ファイルのすべてのプロパティがあります：それは物理的にあります。 この場所は、サーバー（IP）とドライブを識別します。 ディスクを備えたこのようなサーバーが2台必要です。







しかし、1つのディスクには多くのファイルがあります（この例では約2,000,000）。 つまり、FileDBのこれらのエントリには、保存場所と同じディスクペアがあります。 したがって、この情報をFileDBに保存するのは無駄です。 それを別のテーブルに取り出し、FileDBに新しいテーブルのレコードを示すIDを残します。







このようなペアの説明に加えて、フラグフィールドも必要であることは明らかです。 フラグには、ディスクがロックされているという情報が含まれています。たとえば、1つが流出し、2つ目がコピーされているため、新しい情報を書き込むことはできません。







また、各ディスクの空き容量を知る必要もあります。 これらのフィールドをテーブルに追加します。







すべてが迅速に機能するには、FileDBとPairDBがRAMに存在する必要があります。 Tarantool 1.5を使用してください。 今すぐ最新バージョンを使用する必要があると言わなければなりません。 FileDBには5つのフィールド（それぞれ20、4、4、4、4バイト）があり、合計36バイトのデータがあります。 各ヘッダーには、16バイトと各フィールド長ごとに1バイトが含まれます。 レコードごとに合計57バイト。









Tarantoolでは、構成で割り当ての最小サイズを設定できるため、メモリオーバーヘッドをほぼゼロに減らすことができます。 1つのレコードに必要なだけ正確に割り当てます。 1200万のファイルがあります。

(57 * 12 * 10^9) / (1024^3) = 637 Gb
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

しかし、それだけではありません。sha1フィールドにインデックスが必要です。 そして、これはレコードごとにさらに12バイトです。

 (12 * 12 * 10^9) / (1024^3) = 179 Gb
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

合計で、約800 GbのRAMが取得されます。 ただし、レプリカを忘れないでください。これは×2を意味します。









256 GbのRAMを搭載したマシンを使用する場合、8台のマシンが必要です。



PairDBのサイズを見積もることができます。 ただし、平均ファイルサイズは1 MBで、ディスクのサイズは1 Tbです。 これにより、約1,000,000個のファイルをディスクに保存できます。 したがって、約28,000枚のディスクが必要です。 PairDBの1つのエントリは2つのディスクを記述するため、PairDBには14,000レコードがあります。 これは、FileDBと比較してごくわずかです。

ファイルのアップロード

データベース構造を把握しました。次に、システムを操作するためのAPIに進みましょう。 アップロードおよび削除メソッドが必要なようです。 ただし、重複排除については覚えておいてください。アップロードしようとしているファイルがすでにリポジトリにある可能性があります。 もう一度入力するのは意味がありません。 そのため、次のようなメソッドが必要になります。

• inc（sha1、magic） -カウンターを増やします。 ファイルがない場合は、エラーを返します。 魔法も必要だということを思い出してください。 これにより、誤ったファイルの削除から保護されます。
• upload（sha1、magic）-incがエラーを返した場合に呼び出す必要があります。 そのため、そのようなファイルはなく、アップロードする必要があります。
• dec（sha1、magic） -ユーザーがメッセージを削除すると呼び出されます。 まず、カウンターを減らします。
• GET / sha1-単純にhttp経由でファイルをダウンロードします。

アップロード中に何が起こるか見てみましょう。 このインターフェイスを実装するデーモンには、iprotoプロトコルを選択しました。 デーモンは任意の数のマシンに合わせてスケーリングする必要があるため、状態を保存しません。 ソケットリクエストが来ます：







コマンドの名前によって、ヘッダーの長さがわかり、最初に読み取ります。 ここで、 origin-lenファイルの長さが重要です。 それを満たすために、いくつかのサーバーを選択する必要があります。 PairDB全体を出力するだけで、数千のレコードしかありません。 次に、目的のペアを選択するための標準アルゴリズムを使用します。 すべてのペアの自由空間の合計に等しい長さのセグメントを構成し、セグメント上のポイントをランダムに選択します。 セグメントヒットのポイントがどのペアであるかが選択されます。







ただし、このような単純な方法でペアを選択することは危険です。 すべてのディスクが90％満杯で、空のディスクを追加したとします。 かなりの確率で、すべての新しいファイルがそこに注がれます。 この問題を回避するには、共通のセグメントを作成するために、ペアの空き領域ではなく、空き領域からN次の根を取得する必要があります。



いくつか選択しましたが、デーモンはストリーミング中です。ファイルをストアにストリーミングし始めた場合、後戻りすることはできません。 したがって、実際のファイルをアップロードする前に、最初に小さなテストファイルを送信します。 テストファイルがいっぱいになっている場合は、ソケットからファイルコンテンツを減算し、ストレージにストリーミングします。 そうでない場合は、別のペアを選択します。 Sha1はオンザフライで検討できるため、注ぐときにすぐにチェックします。



ローダーから選択したディスクのペアにファイルを書き込むことを検討してください。 ディスクを搭載したマシンでは、nginxを上げてwebdavプロトコルを使用しました。 手紙が届きました。 このファイルはまだFileDBに存在しないため、ローダーを介していくつかのディスクにアップロードする必要があります。







ただし、別のユーザーが同じメールを受信するのを妨げるものはありません。メールに2人の受信者がいるとします。 このファイルはまだFileDBにありません。 別のローダーがまったく同じファイルをアップロードし、同じペアを選択できます。







ほとんどの場合、nginxは問題を正しく解決しますが、すべてを制御する必要があるため、複雑な名前でファイルを保存します。







各ローダーが乱数を書き込む名前の部分は、赤で強調表示されています。 したがって、2つのPUTは交差せず、異なるファイルをアップロードします。 nginxが201に応答すると、ローダーはアトミックMOVE操作を行い、最終的なファイル名を指定します。







2番目のローダーがファイルをアップロードし、MOVEを作成すると、ファイルは上書きされますが、これは同じファイルです-問題はありません。 ディスクに表示されたら、FileDBにレコードを追加する必要があります。 タランチュラは2つのスペースに分かれています。 今のところ、ゼロのみを使用します。







ただし、新しいファイルのエントリを単に追加する代わりに、ファイルカウンタをインクリメントするか、ファイルエントリを追加するストアドプロシージャを使用します。 なぜそう ローダーがファイルがFileDBにないことを確認し、ファイルをアップロードしてエントリを追加する間、誰かがすでにこのファイルをアップロードしてエントリを追加できました。 上記では、まさにそのような状況を考えました。 1通の手紙には2人の受取人がおり、2人のローダーがそれを埋め始めました。 2番目が終了すると、FileDBにも移動します。







この場合、2番目のローダーは単にカウンターをインクリメントします。



では、decプロシージャに進みましょう。 システムにとって2つのタスクが優先されます-ファイルをディスクに書き込み、ディスクからクライアントにすばやく提供することが保証されています。 物理ファイルを削除するとディスクの負荷が発生し、最初の2つのタスクに干渉します。 したがって、オフラインで転送します。 decプロシージャ自体がカウンタを減らします。 マジックのように後者がゼロになった場合、他の誰もファイルを必要としません。 タランチュラのspace0からspace1にそのレコードを転送します。

 decrement (sha1, magic){ counter-- current_magic –= magic if (counter == 0 && current_magic == 0){ move(sha1, space1) } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

バルキリー

各店舗には、データの整合性と一貫性を監視するValkyrieデーモンがあり、space1で動作します。 1つのドライブ-1つのデーモンインスタンス。 デーモンはディスク上のファイルを1つずつ調べ、ファイルエントリがspace1にあるかどうか、つまり削除する必要があるかどうかを確認します。







しかし、dec（）操作の実行中にファイルをspace1に転送してから、Valkyrieがファイルを検出するまでに時間がかかります。 そのため、これらの2つのイベントの間、ファイルはspace0に何度もアップロードできます。







したがって、Valkyrieは、ファイルがspace0にあるかどうかをすぐに確認します。 これが発生し、レコードのpair_idが現在のValkyrieが使用しているディスクのペアを示している場合、space1からレコードを削除します。







エントリがない場合、ファイルは削除の候補です。 それでも、space0でのリクエストと物理的な削除の間には時間差があります。 したがって、このギャップでは、スペース0にファイルエントリが表示される可能性が再びあります。 したがって、ファイルを検疫します。







ファイルを削除する代わりに、deletedとtimestampを名前に追加して名前を変更します。 つまり、設定で指定された時間の間、タイムスタンプ+ファイルを物理的に削除します。 障害が発生し、ファイルが誤って削除されることが決定された場合、ユーザーはそのファイルにアクセスします。 ファイルを復元し、データを失うことなくエラーを修正します。



ここで、2つのディスクがあり、それぞれに独自のValkyrieがあることを思い出してください。 Valkyriesは互いに同期していません。 質問が発生します：space1からエントリを削除するのはいつですか？







2つのことを行います。 最初に、特定のファイルにValkyrieウィザードの1つを割り当てます。 これは非常に簡単に行われます。ファイル名の最初のビットです。 0の場合、マスターはdisk0で、1の場合、マスターはdisk1です。







今、私たちはそれらを時間内に広げます。 リコール：ファイルエントリがspace0にある場合、整合性をチェックするマジックフィールドがあります。 レコードをspace1に転送するとき、魔法は必要ないため、転送時間のタイムスタンプをspace1に書き込みます。 現在、Valkyrieマスターはspace1のレコードをすぐに処理し、スレーブはタイムスタンプに遅延を追加し、後でレコードを処理し、space1からレコードを削除します。







これにより、さらにプラスが得られます。 ファイルがマスターで誤って隔離された場合、マスターを要求すると、ログでこれが表示され、それが把握されます。 その間にファイルを要求したクライアントはスレーブでハッキングされ、ユーザーはファイルを受け取ります。



Valkyrieがディスク上にsha1という名前のファイルを見つけ、このファイル（削除の候補として）にspace1にエントリがある場合を調べました。 他にどんなオプションが可能か見てみましょう。



例。 ファイルはディスク上にありますが、FileDBには記録がありません。 何らかの理由でValkyrieマスターが何らかの理由でしばらく動作しなかった場合、スレーブはファイルを検疫し、space1からエントリを削除しました。 この場合、sha1.deleted.tsを使用してファイルを検疫します。



別の例。 レコードはありますが、別のペアを指します。 これは、1つのメッセージが2人の受信者に送信された場合、ファイルのアップロード時に発生する可能性があります。 図を思い出しましょう。







2番目のローダーが最初のローダーと同じディスクペアにファイルをダウンロードしなかった場合はどうなりますか？ space0のカウンタをインクリメントしますが、ジャンクファイルはそれが注がれたディスクのペアに残ります。 このペアに進み、ファイルが読み込まれ、sha1が一致することを確認します。 すべてが問題なければ、そのようなファイルはすぐに削除できます。



Valkyrieは、隔離されたファイルに遭遇することもあります。 検疫の有効期限が切れている場合、ファイルは削除されます。



ヴァルキリーは良いファイルを見つけました。 sha1と比較して、ディスクから読み取って整合性をチェックする必要があります。 次に-ペアから別のドライブに移動し、そこにファイルがあるかどうかを確認します。 これにはHEADリクエストで十分です。 ファイルの整合性は、そのマシンで実行されているデーモンによってチェックされます。 現在のマシンでファイルの整合性が侵害されている場合、すぐに別のディスクからロードされます。 そのドライブにファイルがない場合は、現在のドライブで2番目までいっぱいにします。



最後のケースであるディスクの問題を考慮する必要があります。 監視後、管理者はこれが起こったことを理解します。 ディスクをサービス（読み取り専用）モードにし、2番目のディスクでぼかし手順を開始します。 2番目のディスクのすべてのファイルは、他のペアに散在しています。

結果

最初に戻りましょう。 メールは次のようになりました。









新しい回路に移行した後、18 Pbを節約しました。









メールは32 Pbを占有し始めました（25％-インデックス、75％-ファイル）。 解放された18 Pbにより、長い間、新しい鉄を購入しないことができました。

PS sha1について

コメントには多くの質問があるため、ここに追加します。 現在、SHA-1自体の衝突の既知の公に計算された例はありません。 圧縮関数へのベクトルを初期化するための衝突（SHA-1フリースタート衝突）の例があります。 ランダムな衝突が120億個のファイルで発生する可能性（10 ^ -38未満）。



しかし、これが可能だとします。 この場合、sha1を使用してファイルを要求するとき、アップロード時に特定のレターのインデックスで記憶したサイズとcrc32のコンプライアンスをチェックします。 つまり ファイルがこのレターでアップロードされた場合にのみファイルを提供します。そうでない場合は何も提供しません。