Buena estructura de datos instantáneos para un índice en memoria

Estoy diseñando una base de datos de objetos en memoria para un caso de uso muy específico. Es un escritor único, pero debe admitir lecturas concurrentes eficientes. Las lecturas deben estar aisladas. No hay lenguaje de consulta, la base de datos solo admite:

obtener objeto / -s por atributo / conjunto de atributos (puede haber soporte para expresiones, por ejemplo x.count < 5)
obtener el atributo del objeto

Una consulta es un script imperativo compuesto por un número arbitrario de las operaciones anteriores. El tamaño de los datos será << memoria, por lo que todos los objetos e índices de la mayoría de los atributos deben ajustarse cómodamente sin intercambiarse.

Lo que necesito es una estructura de datos para el índice de atributos del objeto, que puede ser O (n) en escrituras, no admite concurrencia de escritura, pero idealmente debería admitir instantáneas O (1) (tal vez copiar en escritura) y acceso O (logN). Idealmente, permitiría una alta concurrencia en las lecturas con el máximo intercambio estructural entre las versiones.

Estaba mirando CTries , BST concurrentes y árboles de reproducción simultánea, pero no estoy seguro de si realmente estoy mirando en la dirección correcta aquí. Las estructuras anteriores prestan mucha atención a la complejidad de los insertos que no me importan.

La pregunta : ¿existe una estructura de datos conocida que se ajuste bien a mi caso de uso fuera de la caja?

EDITAR : después de pensar un poco más, parece que un árbol BST / Splay persistente funcionaría. El escritor actualizaría la copia 'maestra' y las consultas obtendrían el árbol al comienzo de la ejecución y lo tirarían después de que hayan terminado. Sin embargo, todavía estoy interesado si hay una mejor solución.

data-structures concurrency databases dm3
fuente

¿Necesita instantáneas en la memoria o necesita guardarlas en el disco / red? Una estructura de datos puramente funcional le brinda automáticamente instantáneas en memoria, por lo que si eso es lo que necesita, es su mejor opción.

Gilles 'SO- deja de ser malvado'

Todo está en la memoria. Me preguntaba si tal vez hay una versión mutable eficiente con una instantánea de tiempo constante (como CTrie, solo sin escrituras concurrentes).

dm3

Su problema puede ser menos la elección de la estructura de datos, sino el tipo de control de concurrencia.

Raphael

Bien podría ser, ¿podría explicar un poco más sobre eso?

dm3

Respuestas:

Utilice cualquier tipo de estructura de datos basada en árbol persistente / inmutable (es decir, funcional). La clave está en el bloqueo correcto, como señaló @Raphael en los comentarios.

Lo bueno de las estructuras de datos basadas en árboles funcionales / persistentes es que obtienes "instantáneas" de forma gratuita. Supongamos que usa un treap (árbol de búsqueda binaria aleatorio) para su estructura de datos. Aquí hay un ejemplo de uno escrito en Go: https://github.com/steveyen/gtreap . El autor lo describe así:

Por inmutable, cualquier actualización / eliminación de un treap devolverá un nuevo treap que puede compartir nodos internos con el treap anterior. Todos los nodos en esta implementación son de solo lectura después de su creación. Esto permite a los lectores concurrentes operar de manera segura con los escritores concurrentes, ya que las modificaciones solo crean nuevas estructuras de datos y nunca modifican las estructuras de datos existentes. Este es un enfoque simple para lograr MVCC o control de concurrencia de versiones múltiples.

$O(\log n)$

Utiliza un bloqueo para proteger el puntero a la raíz. Dado que la estructura de datos es inmutable, las lecturas se pueden realizar de forma simultánea y puede guardar punteros en instantáneas antiguas. Una lectura es:

lock
tmp = ptr_to_root
unlock
value = search(tmp, <value to search for>)
return value

Aunque la búsqueda puede demorar un tiempo, solo mantiene presionado el bloqueo mientras copia el puntero, por lo que las búsquedas pueden realizarse simultáneamente.

Una escritura es:

lock
old_ptr_to_root = ptr_to_root
ptr_to_root = insert(old_ptr_to_root, <new key/value pair>)
unlock

En esta versión, las escrituras deben mantener el bloqueo durante todo el proceso de creación de la nueva versión del árbol. Puede mejorar el rendimiento de lectura (a costa de que a veces falle la transacción de escritura) cambiando la escritura a algo como esto:

top:
  lock
  old_ptr_to_root = ptr_to_root
  unlock
  new_ptr_to_root = insert(old_ptr_to_root, <new key/value pair>)
  lock
  if (ptr_to_root == old_ptr_to_root)   # make sure no other write happened in the interim
    ptr_to_root = new_ptr_to_root
    unlock
  else                                  # transaction fails, try again
    unlock
    goto top

Es posible que pueda hacerlo incluso un poco mejor (hacerlo "sin bloqueo") si su lenguaje de programación tiene variables atómicas con una operación atómica de comparar e intercambiar. (Por ejemplo, usando C ++ 11's atomic<T*>).

Lógica Errante
fuente

Gracias por la elaborada respuesta. Como que lo sabía, tal vez no lo puse lo suficientemente claro en la pregunta misma. Sin embargo, la respuesta sigue siendo genial.

dm3

Su versión "mejorada" depende del modelo de memoria del sistema en uso. Es posible que necesite que los dispositivos verables se declaren volátiles en algún sistema y que necesite una gran habilidad para obtener la codificación correcta.

Ian Ringrose

Microsoft ha publicado detalles sobre su nueva base de datos en memoria, tiene índices que no bloquean las lecturas mientras se realizan las escrituras.

Por ejemplo:

Justin Levandoski, David Lomet y Sudipta Sengupta, The Bw-Tree: A B-tree for New Hardware, en 2013 29a Conferencia Internacional IEEE sobre Ingeniería de Datos (ICDE), Conferencia Internacional sobre Ingeniería de Datos, 8 de abril de 2013.

Consulte http://research.microsoft.com/en-us/projects/main-memory_dbs/ para obtener una lista de sus publicaciones.

Ian Ringrose
fuente