parsing - 为分隔符分隔的块缓冲数据

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 等都可以增量解析。您不需要分隔符来进行有用的处理。