4

このように構造化された（簡略化された）.protoがあるとしましょう

Message DataItem {
  required string name = 1;
  required int32 value = 2;
}

Message DataItemStream {
  repeated DataItem items = 1;
}

サーバーは を作成しDataItemStream、ディスクに書き込みます。このファイルをロードすると、問題なくすべてが満足しています。

これは私たちにとって非常にうまく機能しましたが、クライアントベースが拡大し、ファイルのストリームを生成するソフトウェアの使用も拡大しました.

問題が発生するのは、繰り返しitemsフィールドに何万ものアイテムを含めることができるが、それらのサブセットのみに関心がある場合です。私たちは少し掘り下げましたが、Google のストリーミングアドバイス(保存されたsにサイズ プレフィックスをDataItem追加し、各メッセージを個別に解析するか、または CodedInputStream/CodedOutputStreamまたはバイナリ ワイヤ フォーマット (base64) をエンコードし、改行で区切ると、関心のあるサブセットだけを非常に簡単に取得できます.

これらのいずれも機能しますが、ファイルの保存方法を変更するには、本番コードにいくつかの変更が必要です (サーバーベースのコードは長い間変更されておらず、管理者によって事実上変更できないと見なされています (彼らの考えでは、ドン壊れていない場合は修正しないでください）...）

メッセージを異なる方法でストリーミングするサーバー用のモジュールを既に再作成しましたが、変更をプッシュすることについてメンテナーから非難を受けています。開発サイクルを完全に制御できるため、必要に応じてコードを変更する方が (政治的に) はるかに簡単です。

この元のメッセージ ストリームを引き続き使用しながら、読み込むメッセージのサブセットのみを賢く選択する方法はありますか? （それが重要な場合、どの言語で作業する必要があるかは本当に気にしません.C ++、Python、Java、および.NETの経験があります（経験の順序で））

4

5 に答える 5

1

私はこれをデータベースの問題と考えます。個々のレコード (DataItems) を持つテーブル (DataItemStream) を表すファイルがあります。テーブルから連続した範囲の DataItems を選択したいようです。これは、DataItemStream 内の DataItems の順序が重要であることを意味し、実際には非表示の主キー (「配列」インデックス、別名 DataItemStream 内の DataItem の行番号) をエンコードします。

ほとんどのデータベースと配列データ構造では、各行 (または配列項目) が同じ量のスペースを占有するため、n 番目の項目へのアクセスは簡単です。ただし、DataItemStream に配置された DataItems は可変長であるため、この単純な方法は機能しません。

データベースの比喩を使用して、レコードを効率的に検索するもう 1 つの方法は、インデックスを作成することです。基本的には別のテーブルですが、メイン データ構造へのポインターを含むはるかに小さいテーブルです。インデックスは通常、(PK、ポインター) タプルのテーブルとして構造化されます。この場合、本質的にメモリ マップされた int32 の配列であるインデックス ファイルを持つことができます。インデックスの各値は、その DataItem レコードが開始するデータ ファイル内のバイト オフセットを指します。

たとえば、データ ファイルの長さが 1m レコードの場合、インデックスは 4MB (1m レコード * len(int32) = 1m * 4 バイト) になります。レコード 777777 から 888888 のデータ ファイルをスキャンする必要がある場合は、次のようにします。

  1. インデックスを読み取って、DataItemStream で対象のバイト範囲を取得します。シーク操作は非常に高速であることに注意してください。
    1. インデックスファイルを開く
    2. 開始インデックス int32 (777777*4) をシークし (たとえば、Java RandomAccessFile.seek() では、Python では fileObject.seek() で)、それを読み取ります。これは開始バイトオフセットです
    3. 終了インデックス int32 (888888*4) を探して読み取ります。これは終了バイトオフセットです
    4. インデックス ファイルを閉じる
  2. インデックスで指定された DataItemStream ファイルのバイト範囲を読み取ります。
    1. DataItemStream ファイルを開く
    2. ファイル内の開始バイトオフセットをシークします
    3. 最後のバイト オフセットまでストリームを読み取ります (1 を引くことを忘れないでください)。
    4. DataItemStream ファイルを閉じます

2. about のわずかに異なるアプローチは、最初に指定されたバイト範囲の新しいファイルを作成することです。このファイルは現在、関心のあるレコードのみで構成されています。

インデックス ファイルはどのように作成されますか?

編集: PB 形式の説明: 実際のインデックス ファイルの構成は、データ ファイルを単純に渡すだけで生成できます。すべてのフィールドはバイトで始まり、メッセージ タイプの後にセグメントが続きます。here で説明されているように、各バイトの MSB を継続信号として使用する「特別な」方法でエンコードされます。これは、データ形式の複雑さをほぼすべて回避できることを意味し、したがってインデクサーを非常に単純にすることができます。

インデックス ファイルをキャッシュとして扱うことができます。コード ライブラリは、存在する場合は最新のインデックスを使用するか、存在しない場合は自動的に作成することができます。

このアプローチにより、インデックスを認識するコードを効率的に処理でき、レガシー プログラムのデータ形式を変更しません。

于 2012-12-10T01:40:21.580 に答える
0

コメントでの私の質問に対するあなたの回答を考えると、ファイルの形式は何ですか? 任意の場所にシーク​​した後、アイテムの先頭に同期できますか?

同様の状況 (ギガバイトを超えるログ ファイル、特定の時間間隔でログ エントリを検索する) に直面したため、最終的にファイルのバイナリ検索を実行しました。これは少しトリッキーで、コードは実際には移植可能ではありませんが、基本的な考え方は、(Unix で使用するか、Windows で同等のものを使用して) ファイルの長さを決定し、( statWindows でバイナリ モードで) ファイルを開くことです。 ; 真ん中にシークし、次のレコードの開始を前方にスキャンしてから、探していたものと比較し、次のシーク位置を、必要な場所の後ろまたは前にあるかどうかによって決定します。これは、任意の場所から開始するときにレコードの開始を見つけることができる場合に機能します (ファイルの形式によって異なります)。

于 2012-12-06T16:48:44.693 に答える
0

残念ながら、外側の PB ストリームのデコードは自分で行う必要があります。アイテムの開始点 (できれば梱包されていないこと) を見つけたら、個々のアイテムに PB を使用できます。その後、文字通り無限のストリームで作業できます。もちろん、いくつかの深刻なテストを行う必要がありますが、試してみたいと思います。

于 2012-12-10T23:34:01.943 に答える
0

適切に正規化されたスキーマで実行されている実際のデータベース エンジンが機能しないと確信している場合 (データベース エンジンの連中は、このようなパズルを解決する方法をしばらくの間考えてきました)。 、次にこれを試してください：

コレクションの最小フィールドのデータが少なくとも大規模な一握りのセクターを占めるように、十分な数のレコードをバッチ処理します。これらのレコード内のフィールドのデータを書き込み、4KB の境界で始まる連続するチャンクを分離します。各セットの先頭に、チャンクの境界を見つける場所を示すヘッダーを付けます。次に、必要なフィールドのチャンクのみを読み取ります。

本当にパフォーマンスが必要であるが、まだスピナーが必要な場合は、チャンクを別のディスクの別のファイルに配置します。スキップは、非常に大きなデータのチャンクをスキップするまで、これらのものを読み取るのと同じくらい遅くなります。

編集：ディスク上のフォーマットを変更したくないようですが、不要なデータの読み取りを回避しようとしているため、実際には選択肢がありません。

于 2012-12-15T04:34:12.080 に答える
0

主なボトルネックがディスク アクセスの速度ではなく RAM である場合、ファイル メッセージ全体 (つまりDataItemメッセージ) を読み取り、関心のある部分のみを保持して転送するプロキシ/フィルターを挿入してみませんか? オーバーフローの危険を冒すことなく、関心のある部分全体をバッファリングできるように思えます。

ストリームの途中でメッセージの開始を検出する方法を理解できれば、バッファ ファイルをシークするようにプロキシをさらに改善できますが、これはパフォーマンスの向上であり、残りの部分へのプロキシのインターフェイスには影響しません。パイプライン、または最大メモリ フットプリント。

あなたの問題は、DataItemメッセージが に埋め込まれているDataItemStreamため、Google API により、一度に全体をロードする必要がDataItemStreamあることです。DataItemStreamこれを回避するには、エンベロープをスキップして、埋め込まれていないかのように のシーケンスを公開する醜いコードを書くことができますDataItem。これは PB シリアライゼーションの内部に依存しますが、クライアントは安定性を重視しているため、すぐには変化しないと期待できます。変更された場合は、好みのメッセージ レイアウトをプッシュして、既に開発したソリューションに切り替える時が来ます。

実際のメッセージ形式が表示されているものよりも大幅に複雑でない場合 (たとえば、オプション フィールドが多すぎたり、複数レベルの埋め込みメッセージが含まれていない場合)、CodedInputStream(現在のファイル レイアウトを変更せずに) を使用してファイル レイアウトをナビゲートするのは簡単です。最初のメッセージを読むには、最初からとを探してから、各メッセージを で読むDataItem だけです。skipRawBytes()skipField()readMessage()

しかし、Google API は単一のストリームから一連のメッセージを読み取るように設計されていないことを理解しています。そのため、これはおそらく単純すぎます。その場合でも、最初の のフィールド 1 へのオフセットを見つけ、 で読み取り、必要に応じてフィールド 2 の先頭まで進みDataItem、 で読み取ることができるはずです。その後、プロキシはメッセージを破棄するか、メッセージを再構築して、それを残りのコードに渡します。readString()readInt32()

あなたはすでにこれらの線に沿って何かを考えていると思いますが、おそらくこのアプローチは何らかの理由で実行不可能または望ましくないのでしょうか? それとも、あまりにも醜いので、ファイル レイアウトを変更するという政治的コストに対処したいのかもしれません...

于 2012-12-06T18:30:40.147 に答える