Almacenamiento de datos para bloques separados por delimitador

Question

Hay una pregunta sobre la que me he estado preguntando durante años y esperaba que alguien pudiera darme una respuesta para descansar.

Supongamos que tengo una secuencia de entrada (como un archivo / socket / tubería) y quiero analizar los datos entrantes. Supongamos que cada bloque de datos entrantes se divide por una nueva línea, como los protocolos de Internet más comunes. Esta aplicación también podría analizar html, xml o cualquier otra estructura de datos inteligente. El punto es que los datos se dividen en bloques lógicos mediante un delimitador en lugar de una longitud fija. ¿Cómo puedo almacenar en búfer los datos para esperar a que aparezca el delimitador?

La respuesta parece bastante simple: solo tiene una matriz byte / char lo suficientemente grande como para adaptarse a todo.

¿Pero qué pasa si el delimitador viene después de que el búfer está lleno? Esta es realmente una pregunta sobre cómo encajar un bloque dinámico de datos en un bloque de tamaño fijo. Solo puedo pensar en algunas alternativas:

1. Aumente el tamaño del búfer cuando sea necesario. Esto puede requerir una reasignación de memoria pesada, y puede conducir al agotamiento de los recursos de las transmisiones especialmente diseñadas (o tal vez incluso a la denegación de servicio en el caso de sockets donde queremos protegernos contra ataques de agotamiento y desconectar conexiones que intentan agotar los recursos ... y un atacante comienza a enviar paquetes falsos y de gran tamaño para activar la protección).

2. Comience a sobrescribir datos antiguos utilizando un búfer circular. Quizás no sea un método ideal ya que el bloque lógico se volvería incompleto.

3. Volcar datos nuevos cuando el búfer está lleno. Sin embargo, de esta manera nunca se encontrará el delimitador, por lo que esta opción obviamente no es una buena opción.

4. Simplemente haga que el búfer de tamaño fijo sea muy grande y suponga que todos los bloques de datos lógicos entrantes están dentro de sus límites ... y si alguna vez se llena, simplemente interprete el búfer completo como un bloque lógico ...

En cualquier caso, creo que debemos suponer que los bloques lógicos nunca excederán un cierto tamaño ...

¿Alguna idea sobre este tema? Obviamente, debe haber una manera, ya que los lenguajes de nivel superior ofrecen algún tipo de mecanismo de almacenamiento en búfer con sus métodos de flujo readLine () .

¿Hay alguna "mejor manera"? para resolver esto o siempre hay una compensación? Realmente aprecio todos los pensamientos e ideas sobre este tema, ya que esta pregunta me ha estado persiguiendo cada vez que necesito escribir un analizador de algún tipo.

Answer 1

Normalmente hay dos técnicas para esto

1) Lo que creo que usa readline: si el búfer se llena devuelve los datos sin el delimitador al final

2) Cuando el búfer se llene, recuerde que está lleno, siga leyendo hasta que obtenga el delimitador e informe un error (o truncar el registro en el tamaño del búfer)

Answer 2

Las opciones (2) y (3) están fuera ya que está perdiendo datos en ambos casos. La opción (4) de un enorme búfer de tamaño fijo no resolvería el problema, ya que simplemente no es posible saber qué tamaño es lo suficientemente grande. ¿Es toda la memoria física + espacio de intercambio + el espacio libre disponible en todos los discos en todas partes del universo conocido?

Cambiar el tamaño del búfer parece la mejor solución. Diga realloc al doble del tamaño y continúe escribiendo. Siempre existe la posibilidad de una secuencia especialmente construida como un DoS que intente derribar el sistema. Mi primer pensamiento fue establecer un tamaño arbitrariamente grande como max_size para el búfer. Sin embargo, si pudiéramos hacer eso, podríamos establecerlo como el tamaño del búfer grande. Entonces, cambiar el tamaño del búfer me parece la mejor opción.

Answer 3

1. Si el protocolo o usted no define un límite superior para la longitud de cada bloque, entonces no veo cómo puede evitar casos extremos de agotamiento de memoria.

2. Asumir que hay un límite superior usando un bloque de tamaño fijo parece un buen enfoque para límites de tamaño razonable.

3. Si los límites son lo suficientemente altos como para que un único búfer fijo sea ineficiente, sugeriría utilizar una estructura de datos que se implementa internamente como una lista vinculada de búferes de tamaño fijo.

Answer 4

¿Por qué tienes que esperar para comenzar a procesar?

Generalmente la alternativa 4 es el sonido. Sin embargo, no requiere una "suposición", más bien una definición. Simplemente declaras que los bloques son más pequeños que 8K y listo. No es difícil de hacer.

Además, hay una alternativa 5: comenzar a procesar buffers parciales. Esto funciona a menos que haya diseñado un protocolo verdaderamente patológico que envíe datos críticos al final del bloque.

HTML, XML, JSON / YAML, etc., se pueden analizar de forma incremental. No requiere un delímetro para realizar un procesamiento útil.