缓冲分隔符分隔块的数据

Question

有一个问题我多年来一直想知道，我希望有人能给我一个答案，让我安心。

假设我有一个输入流（如文件/套接字/管道）并且想要解析传入的数据。我们假设每个传入数据块都由换行符分隔，就像大多数常见的互联网协议一样。该应用程序也可以解析 html、xml 或任何其他智能数据结构。重点是数据是通过分隔符而不是固定长度分割成逻辑块的。如何缓冲数据以等待分隔符出现？

答案似乎很简单：只需有一个足够大的字节/字符数组即可容纳整个内容。

但是如果分隔符出现在缓冲区已满之后怎么办？这实际上是一个关于如何将动态数据块放入固定大小块中的问题。我只能想到几个替代方案：

1. 需要时增加缓冲区大小。这可能需要大量内存重新分配，并可能导致特制流的资源耗尽（或者在我们想要保护自己免受耗尽攻击并丢弃试图耗尽资源的连接的套接字的情况下甚至可能导致拒绝服务......并且攻击者开始发送虚假的超大数据包来触发保护）。

2. 使用循环缓冲区开始覆盖旧数据。也许不是一个理想的方法，因为逻辑块会变得不完整。

3. 当缓冲区满时转储新数据。然而，这样就永远找不到分隔符，所以这个选择显然不是一个好的选择。

4. 只需将固定大小的缓冲区设置得非常大，并假设所有传入的逻辑数据块都在其范围内...并且如果它被填满，只需将完整的缓冲区解释为逻辑块...

无论哪种情况，我认为我们必须假设逻辑块永远不会超过一定的大小......

对这个话题有什么想法吗？显然，必须有一种方法，因为高级语言提供了某种缓冲机制 readLine() 流方法。

是否有任何“最佳方法”来解决这个问题，或者总是需要权衡？我真的很感激关于这个主题的所有想法和想法，因为每次我需要编写某种解析器时这个问题都困扰着我。

Answer 1

通常有两种技术可以实现此目的

1）我认为 readline 的用途 - 如果缓冲区填满则返回数据，末尾不带分隔符

2）当缓冲区填满时，记住它已填满，继续阅读，直到得到分隔符并报告错误（或按缓冲区大小截断记录）

Answer 2

选项（2）和（3）不适用，因为在这两种情况下都会丢失数据。巨大的固定大小缓冲区的选项（4）无法解决问题，因为不可能知道什么大小足够大？是所有物理内存+交换空间+已知宇宙中所有磁盘中可用的可用空间吗？

调整缓冲区大小看起来是最好的解决方案。说重新分配到两倍大小并继续写入。总是有可能出现像 DoS 之类的专门构建的流，试图破坏系统。我的第一个想法是设置任意大的大小作为缓冲区的 max_size 。但是，如果我们可以做到这一点，我们可以将其设置为大缓冲区的大小。因此，调整缓冲区大小对我来说似乎是最好的选择。

Answer 3

1. 如果协议或您没有定义每个块的长度上限，那么我不知道如何防止内存耗尽边缘情况。

2. 假设使用固定大小的块存在上限似乎是合理大小限制的好方法。

3. 如果限制足够高，以至于单个固定缓冲区效率低下，那么我建议使用在内部实现为固定大小缓冲区的链接列表的数据结构。

Answer 4

为什么必须等待才能开始处理？

一般来说，替代方案 4 是合理的。然而，它不需要“假设”，而是需要定义。您只需声明块小于 8K 即可完成。这并不难做到。

此外，还有替代方案5：开始处理部分缓冲区。除非您设计了一个真正病态的协议，该协议在块的最后发送关键数据，否则这种方法是有效的。

HTML、XML、JSON/YAML 等都可以增量解析。你不 要求 进行有用处理的分隔符。