Estamos obsesionados con las pruebas en Qumulo.
Enviar una nueva versión de un sistema de archivos distribuido y escalable cada dos semanas significa que tenemos que estar seguros de que cada compromiso con nuestro código base está libre de errores. Para ese fin, tenemos decenas de miles de pruebas unitarias, miles de pruebas de integración y muchos cientos de pruebas completas del sistema que superan cada compilación para verificar que no hemos introducido una regresión.
Si bien este tipo de pruebas son importantes, queríamos ir más allá. Queríamos una forma de ejecutar cada ruta posible a través de un fragmento de código en particular para poder verificar que, sin importar qué, el comportamiento del código era correcto y las invariantes del sistema se mantenían. Un enfoque tradicional para este problema podría ser inspeccionar manualmente los informes de cobertura de código y elaborar pruebas individuales para ejercer cada rama del código, pero esto es frágil porque requiere que un ser humano inspeccione la cobertura del código y, a menudo, involucra una prueba compleja, a veces complicada Para ejercitar el código descubierto. Alternativamente, podríamos escribir pruebas fuzz que exploren probabilísticamente cada rama del código, pero son difíciles de elaborar y, por su naturaleza, pueden no explorar todos los casos interesantes. Pensamos que podríamos hacerlo mejor.
Un ejemplo motivador.
Imagina que tenemos una función que des-serializa una orden de kumquat de un formato binario a una estructura. kumquat_order</var/www/wordpress>:
struct kumquat_order {nombre de carácter [100]; cantidad sin firmar; }; int deserialize_kumquat_order (struct istream * input, struct kumquat_order * out) {int error_code = istream_read (entrada, salida-> cantidad, tamaño de salida-> cantidad); if (error_code! = 0) return error_code; bool anónimo; error_code = istream_read (entrada, & anónimo, tamaño de anónimo); if (error_code! = 0) return error_code; if (anónimo) strcpy (orden-> nombre, "anónimo"); else istream_read (entrada, salida-> nombre, tamaño de salida-> nombre); return 0; }
Una de las invariantes de esta función es que si alguna llamada al istream devuelve un error, la función también debe devolver un error. Como puede ver, ese invariante ha sido violado cuando leemos el nombre de la orden, donde el código de error de istream_read()</var/www/wordpress> is completely ignored:
istream_read(input, out->name, sizeof out->name);</var/www/wordpress>
En este caso, no sería inimaginablemente difícil escribir una prueba unitaria para descubrir este error, pero a medida que agregamos más campos al kumquat_order y más complejidad al formato binario, sería cada vez más difícil elaborar pruebas de unidades individuales para verificar Nuestro invariante y proteger contra esta clase de error. Lo que realmente nos gustaría es una implementación de la interfaz istream que pueda devolver un error de forma determinista en cada punto que se llame.
Introduciendo rseq
Para manejar estas exhaustivas pruebas de cobertura, creamos un componente que llamamos rseq, que significa "secuencia aleatoria" (aunque es un poco erróneo, no hay nada "aleatorio" sobre rseq). La interfaz fundamental para rseq es notablemente simple:
struct rseq; bool rseq_flip_coin (struct rseq *); bool rseq_next_simulation (struct rseq *);
rseq se basa en el concepto de una simulación de una prueba. Cada vez que la prueba llega a un punto de decisión que quiere ser parte del conjunto de decisiones bajo simulación, llama a rseq_flip_coin()</var/www/wordpress>, which returns a boolean that the test can use to influence the behavior of this simulation of the test. At the end of each simulation, the test calls rseq_next_simulation()</var/www/wordpress>, which will return false when there are no more simulations with unique paths through the decision space. Let’s look at a simple example:
estructura rseq * rseq = rseq_new (); hacer {printf ("% c", rseq_flip_coin (rseq)? 't': 'f'); printf ("% c", rseq_flip_coin (rseq)? 't': 'f'); printf ("% c,", rseq_flip_coin (rseq)? 't': 'f'); } while (rseq_next_simulation (rseq));
La salida de este código es el conjunto completo de combinaciones de decisiones:
fff, fft, ftf, ftt, tff, tft, ttf, ttt,</var/www/wordpress>
Es importante destacar que rseq puede trabajar incluso si las llamadas a rseq_flip_coin()</var/www/wordpress> are conditional. For example, if we only make the second call to rseq_flip_coin()</var/www/wordpress> if the first call returns true:
estructura rseq * rseq = rseq_new (); hacer {if (rseq_flip_coin (rseq)) {printf ("a"); printf ("% c", rseq_flip_coin (rseq)? 'b': 'c'); } else printf ("d"); printf ("% c,", rseq_flip_coin (rseq)? 'e': 'f'); } while (rseq_next_simulation (rseq));
La salida sería:
df, de, acf, ace, abf, abe</var/www/wordpress>
Las decisiones no binarias (p. Ej., Elegir entre cinco opciones diferentes) se pueden implementar mediante el lanzamiento de monedas, pero rseq proporciona una función útil para usted:
unsigned rseq_roll_die(struct rseq *, unsigned sides);</var/www/wordpress>
rseq internals
Como te habrás dado cuenta, rseq realiza una especie de búsqueda de "falso primero" a través del espacio de decisión. Esto se logra de una manera relativamente simple: al realizar un seguimiento de un script de decisiones de devolución, implementado con un vector de valores booleanos que representan decisiones de lanzamiento de moneda y un cursor para realizar un seguimiento de la posición actual en el script.
Como llamadas a rseq_flip_coin()</var/www/wordpress> are made, the decision at the current cursor is returned. If the cursor is at the end of the script when the call is made, we append a false decision to the script and return false from the rseq_flip_coin()</var/www/wordpress> call.
Cuándo rseq_next_simulation()</var/www/wordpress> is called, we trim trailing true decisions from the end of the script, which represent decision paths that have been fully explored, and flip the last false decision in the script to true and rseq_next_simulation() returns true. If the script is empty after trimming trailing true decisions, the decision tree has been fully explored and rseq_next_simulation()</var/www/wordpress> returns false.
En caso de que el inglés no fuera claro, creamos un versión básica interactiva de Python de rseq en repl.it, con el que puedes jugar para ayudarte a entender cómo funciona.
Examinando exhaustivamente el kumquat_order</var/www/wordpress> deserializer
Una forma común en que usamos rseq en Qumulo es en una implementación de prueba doble de una interfaz que es la dependencia inyectada en el sistema bajo prueba (SUT).
Volviendo al ejemplo anterior, lo que nos gustaría es una versión de la interfaz istream que devuelva un error o caiga en otra implementación de istream que haga el trabajo real. Por razones que se aclararán más adelante, también vamos a querer saber que alguna llamada a este istream con reconocimiento de rseq ha devuelto un error. Aquí hay una implementación de ejemplo que utiliza un poco de magia de interfaz de Qumulo C:
struct rseq_error_istream {a_implements (istream); // ¡Qumulo magia! struct rseq * rseq; bool return_error; // Inicializado en false struct istream * delegate; }; int rseq_error_istream_read (struct rseq_error_istream * self, void * data, unsigned c) {if (rseq_flip_coin (self-> rseq)) {self-> return_error = true; return -1; } else return istream_read (self-> delegate, data, c); }
Al usar rseq aquí, tenemos la garantía de que en el momento rseq_next_simulation()</var/www/wordpress> returns false, every call into istream_read made by the SUT will have returned an error in at least one of the simulations. Using such an implementation of istream, we can now write a test which will fail when run against our kumquat_order</var/www/wordpress> deserializer:
estructura rseq * rseq = rseq_new (); do {// Configuración del aparato struct file_istream * order_istream = file_istream_new ('test_order')); struct rseq_error_istream * rseq_istream = rseq_error_istream_new (rseq, istream_from_file_istream (order_istream)); // Ejercicio SUT struct kumquat_order order; int error = deserialize_kumquat_order (istream_from_rseq_error_istream (rseq_istream), & order); // Verifica si (rseq_istream-> return_error) assert (error == -1); de lo contrario aserrar (kumquat_order_is_correct (& order)); // Desmontaje del accesorio rseq_error_istream_free (rseq_istream); file_istream_free (order_istream); } while (rseq_next_simulation ());
Lo realmente increíble de esta prueba es que es completamente independiente de cómo deserialize_kumquat_order()</var/www/wordpress> uses the istream. As we add more complexity to the deserialization code, this test will continue to exercise every possible error path through the SUT, verifying our invariant without us having to write a new test for each new path. We could even extend the invariant to say that no calls should be made into the istream after it returns an error with relative ease by making the following modification:
int rseq_error_istream_read (struct rseq_error_istream * self, void * data, unsigned c) {assert (! self-> return_error); if (rseq_flip_coin (self-> rseq)) {self-> return_error = true; return -1; } else return istream_read (self-> delegate, data, c); }
Otros usos para rseq.
La verificación de fallos rápidos es uno de los muchos usos de rseq en Qumulo. Otras cosas interesantes que hemos hecho con rseq incluyen:
- Simular todos los pedidos posibles de RPC que se envían simultáneamente a un nodo en nuestro clúster
- Simulando cada posible intercalado de subprocesos cooperativos de espacio de usuario (sí, ¡hemos escrito nuestra propia biblioteca de subprocesos de espacio de usuario!) Utilizando rseq en el programador para seleccionar el siguiente subproceso que se ejecutará cuando ceda un subproceso.
- Simular todos los estados posibles de un sistema complejo y demostrar que nuestro código puede proceder de ese estado (por ejemplo, recuperación de transacciones distribuidas)
trampas rseq
Si bien rseq es extremadamente útil, tiene sus dificultades:
- rseq no funciona bien con el no determinismo porque se basa en el orden de las llamadas a rseq_flip_coin () que es determinista para cada simulación. Por ejemplo, si el SUT usa un rand () para decidir si realizar una llamada que finalmente se convierta en rseq, se confundirá rápidamente. Para solucionar esto, encapsulamos esta aleatoriedad en una interfaz de inyección de dependencia que tiene una implementación de producción que llama a rand () pero puede ser sustituida por un doble de prueba que usa rseq cuando se ejecuta en pruebas.
- Del mismo modo, es peligroso usar rseq en un entorno de subprocesos múltiples. Si varios subprocesos pueden actuar en la misma instancia de rseq durante una simulación, esto introduce el no determinismo en el orden de llamada a rseq. Por esta y muchas otras razones, nos esforzamos mucho por mantener la gran mayoría de nuestro código de un solo hilo, utilizando patrones de llamada asíncronos en lugar de generar hilos siempre que sea posible.
- Cuando el SUT es complejo, rseq puede entrar en una explosión de estado causando que la cantidad de simulaciones que se deben ejecutar para buscar exhaustivamente el espacio de decisión aumente exponencialmente. No hemos tenido demasiados problemas con esto en la práctica, pero afortunadamente, rseq se presta muy bien para funcionar de manera distribuida con trabajadores que toman parte del espacio de búsqueda si alguna vez queremos hacerlo.
