Almacén de clave-valor ordenado

Un almacén de clave-valor ordenado (OKVS) es un paradigma de almacenamiento de datos que admite bases de datos multimodelo . Un OKVS es una asignación ordenada de bytes a bytes. Un OKVS mantiene los pares clave-valor ordenados según el orden lexicográfico de la clave. Los sistemas OKVS ofrecen diferentes conjuntos de características y compensaciones de rendimiento. La mayoría se distribuyen como una biblioteca sin interfaces de red, para poder integrarse en otro proceso. La mayoría de los OKVS admiten garantías ACID . Algunos OKVS son bases de datos distribuidas . Los almacenes de clave-valor ordenados se han incorporado a muchos sistemas de bases de datos modernos, incluidos los sistemas de bases de datos NewSQL .

El origen del almacenamiento ordenado de clave-valor se remonta al trabajo de Ken Thompson en dbm en 1979. Posteriormente, en 1991, se lanzó Berkeley DB , que presentaba un backend de árbol B que permitía que las claves permanecieran ordenadas. Se decía que Berkeley DB era muy rápido y se incorporó a varios productos comerciales. Se incluyó en la biblioteca estándar de Python hasta la versión 2.7. ^{[ 1 ]} En 2009, se lanzó Tokyo Cabinet, que fue reemplazado por Kyoto Cabinet , que admite tanto claves transaccionales como ordenadas. En 2011, se creó LMDB para reemplazar a Berkeley DB en OpenLDAP . También existe LevelDB de Google , que fue bifurcado por Facebook en 2012 como RocksDB . En 2014, WiredTiger , sucesor de Berkeley DB, fue adquirido por MongoDB y desde 2019 es el backend principal de la base de datos MongoDB.

Otras implementaciones destacadas del paradigma OKVS son Sophia ^{[ 2 ]} y la extensión SQLite3 LSM. Otro uso notable del paradigma OKVS es el sistema de base de datos multimodelo llamado ArangoDB ^{[ 3 ],} basado en RocksDB.

Algunas bases de datos NewSQL son compatibles con almacenes de clave-valor ordenados. JanusGraph , una base de datos de grafos de propiedades, cuenta con un backend tanto de Berkeley DB como de FoundationDB .

Las siguientes abstracciones o bases de datos se construyeron sobre almacenes de clave-valor ordenados superiormente:

• Base de datos de series temporales,
• Base de datos de registros, ^{[ 5 ]} también conocidas como bases de datos de almacenamiento de filas, se comportan de manera similar a lo que se denomina RDBMS ,
• Almacenes de tuplas, también conocidos como Almacén triple o Almacén cuádruple, pero también Almacén de tuplas genérico, ^{[ 6 ] [ 7 ]}
• Base de datos de documentos, ^{[ 8 ]} que imita la API de MongoDB,
• Búsqueda de texto completo ^{[ 9 ]}
• Sistemas de Información Geográfica ^{[ 10 ]}
• Gráfico de propiedades ^{[ 11 ]}
• Datos versionados ^{[ 12 ]}
• Base de datos de espacio vectorial para el vecino más cercano aproximado ^{[ 13 ]}

Todas esas abstracciones pueden coexistir con la misma base de datos OKVS y, cuando se admite ACID, las operaciones se realizan con las garantías que ofrece el sistema de transacciones.

OKVS resulta útil para implementar dos estrategias: optimizar una característica menor, por ejemplo, para lograr una mejora del 10 % en la latencia de lectura o escritura; la segunda estrategia consiste en aprovechar la naturaleza distribuida de FoundationDB y TiKV, para las cuales no existe un equivalente a gran escala en cuanto a resiliencia. Ambos usuarios necesitan reimplementar las abstracciones de alto nivel necesarias, ya que no existen bibliotecas portátiles listas para usar de abstracción de alto nivel. Aún existe un complejo equilibrio entre complejidad, mantenibilidad, ajuste fino y características fácilmente disponibles, lo que lo convierte en una opción para expertos. En ocasiones, las estructuras de datos más especializadas pueden ser más rápidas que una abstracción de alto nivel sobre un OKVS.

Otro aspecto interesante del paradigma OKVS radica en su interfaz sencilla y versátil, lo que lo convierte en un objetivo interesante para algoritmos de almacenamiento experimentales y estructuras de datos.

• Base de datos clave-valor
• Tienda de columnas anchas
• Base de datos multimodelo