区切り文字で区切られたブロックのデータのバッファリング

Question

私は長年にわたって疑問に思っていた質問があり、誰かが私の心を休めるための答えをくれることを望んでいました。

入力ストリーム（ファイル/ソケット/パイプなど）があり、受信データを解析したいとします。ほとんどの一般的なインターネットプロトコルのように、着信データの各ブロックが改行で分割されていると仮定しましょう。このアプリケーションは、html、xml、またはその他のスマートデータ構造を解析することもできます。ポイントは、データが固定長ではなく区切り文字によって論理ブロックに分割されることです。デリミタが表示されるのを待つためにデータをバッファするにはどうすればよいですか？

答えは非常に単純なようです。全体を収めるのに十分な大きさのbyte / char配列があれば十分です。

しかし、バッファが一杯になった後に区切り文字が来るとどうなりますか？これは、実際には、データの動的ブロックを固定サイズのブロックに収める方法についての質問です。私は本当にいくつかの選択肢しか考えられません：

1. 必要に応じて、バッファサイズを増やします。これには大量のメモリの再割り当てが必要になる可能性があり、特別に細工されたストリームからリソースが枯渇する可能性があります（または、枯渇攻撃から自分自身を保護し、リソースを枯渇させようとする接続をドロップするソケットの場合は、おそらくサービス拒否も発生する可能性があります...攻撃者が偽の特大パケットを送信して保護をトリガーします。

2. 循環バッファを使用して、古いデータの上書きを開始します。論理ブロックが不完全になるため、おそらく理想的な方法ではありません。

3. バッファがいっぱいになると、新しいデータをダンプします。ただし、この方法では区切り文字は検出されないため、この選択は明らかに適切なオプションではありません。

どちらの場合でも、論理ブロックが特定のサイズを決して超えないと仮定する必要があると思います...

このトピックについて何か考えはありますか？高レベルの言語は readLine（）ストリームメソッドを使用して何らかのバッファリングメカニズムを提供するため、明らかに方法が必要です。

「最善の方法」はありますかこれを解決するには、または常にトレードオフがありますか？この質問は、ある種のパーサーを書く必要があるたびに私を悩ませているので、このトピックに関するすべての考えやアイデアを本当に感謝しています。

Answer 1

これには通常2つの手法があります

1）readlineが使用していると思うこと-バッファがいっぱいになると、最後に区切り文字のないデータが返されます

2）バッファがいっぱいになったら、それを記憶し、区切り文字を取得してエラーを報告するまで（またはバッファサイズでレコードを切り捨てるまで）読み続けます

Answer 2

オプション（2）と（3）は、どちらの場合もデータが失われているため、使用できません。巨大な固定サイズバッファのオプション（4）は、どのサイズが十分に大きいかを知ることができないため、問題を解決しませんか？すべての物理メモリ+スワップスペース+既知の宇宙のすべてのディスクで利用可能な空きスペースですか？

バッファのサイズを変更するのが最適なソリューションのようです。サイズを2倍に再割り当てして、書き込みを続けます。システムをダウンさせようとするDoSのような特別に構築されたストリームの可能性は常にあります。最初に考えたのは、バッファのmax_sizeとして任意の大きなサイズを設定することでした。ただし、それが可能な場合は、それを大きなバッファのサイズとして設定することもできます。したがって、バッファのサイズを変更することは、私にとって最適なオプションのように見えます。

Answer 3

1. プロトコルまたは各ブロックの長さの上限を定義しない場合、メモリ枯渇のエッジケースを防ぐ方法がわかりません。

2. 固定サイズのブロックを使用して上限があると仮定すると、合理的なサイズの制限に適したアプローチのように思えます。

3. 制限が十分に高く、単一の固定バッファーでは効率が悪い場合は、固定サイズのバッファーのリンクリストとして内部的に実装されているデータ構造を使用することをお勧めします。

Answer 4

なぜ処理を開始するのを待つ必要があるのですか？

一般的な代替案4はサウンドです。ただし、「仮定」ではなく、定義を必要とします。ブロックが8Kより小さいことを宣言し、それで完了します。難しいことではありません。

さらに、代替手段5：部分バッファの処理を開始します。これは、ブロックの最後に重要なデータを送信する真に病理学的なプロトコルを設計していない限り機能します。

HTML、XML、JSON / YAMLなどは、すべて段階的に解析できます。有用な処理を行うためにデリミタを必要とする必要はありません。