Desarrollo de la tienda de clave / valor portando a C ++ moderno

9

Estoy desarrollando un servidor de base de datos similar a Cassandra.

El desarrollo comenzó en C, pero las cosas se volvieron muy complicadas sin clases.

Actualmente porté todo en C ++ 11, pero todavía estoy aprendiendo C ++ "moderno" y tengo dudas sobre muchas cosas.

La base de datos funcionará con pares clave / valor. Cada par tiene más información: cuándo se crea y cuándo caducará (0 si no caduca). Cada par es inmutable.

La clave es una cadena C, el valor es nulo *, pero al menos por el momento también estoy operando con el valor como cadena C.

Hay IListclases abstractas . Se hereda de tres clases.

  • VectorList - C matriz dinámica - similar a std :: vector, pero usa realloc
  • LinkList - hecho para controles y comparación de rendimiento
  • SkipList - la clase que finalmente se usará.

En el futuro también podría hacer Red Blackárbol.

Cada uno IListcontiene cero o más punteros a pares, ordenados por clave.

Si se IListhizo demasiado largo, se puede guardar en el disco en un archivo especial. Este archivo especial es algo así read only list.

Si necesita buscar una clave,

  • primero en la memoria IListse busca ( SkipList, SkipListo LinkList).
  • Luego, la búsqueda se envía a los archivos ordenados por fecha
    (el archivo más nuevo primero, el archivo más antiguo - el último).
    Todos estos archivos están mmap-ed en la memoria.
  • Si no se encuentra nada, entonces no se encuentra la clave.

No tengo dudas sobre la implementación de las IListcosas.

Lo que me desconcierta actualmente es lo siguiente:

Los pares son de diferente tamaño, se asignan por new()y los han std::shared_ptrseñalado.

class Pair{
public:
    // several methods...
private:
    struct Blob;

    std::shared_ptr<const Blob> _blob;
};

struct Pair::Blob{
    uint64_t    created;
    uint32_t    expires;
    uint32_t    vallen;
    uint16_t    keylen;
    uint8_t     checksum;
    char        buffer[2];
};

La variable miembro "buffer" es la que tiene un tamaño diferente. Almacena la clave + valor.
Por ejemplo, si la clave es de 10 caracteres y el valor es de otros 10 bytes, el objeto completo será sizeof(Pair::Blob) + 20(el búfer tiene un tamaño inicial de 2, debido a dos bytes de terminación nulos)

Este mismo diseño también se usa en el disco, así que puedo hacer algo como esto:

// get the blob
Pair::Blob *blob = (Pair::Blob *) & mmaped_array[pos];

// create the pair, true makes std::shared_ptr not to delete the memory,
// since it does not own it.
Pair p = Pair(blob, true);

// however if I want the Pair to own the memory,
// I can copy it, but this is slower operation.
Pair p2 = Pair(blob);

Sin embargo, este tamaño diferente es un problema en muchos lugares con código C ++.

Por ejemplo no puedo usar std::make_shared(). Esto es importante para mí, porque si tengo 1M de pares, tendría asignaciones de 2M.

Por otro lado, si hago "buffer" a matriz dinámica (por ejemplo, nuevo char [123]), perderé "truco" de mmap, tendré que hacer dos desreferencias si quiero verificar la clave y agregaré un puntero único - 8 bytes a la clase.

También probé a "tirar" a todos los miembros de Pair::Blobdentro Pair, de modo Pair::Blobque sólo la memoria intermedia, pero cuando lo probé, fue bastante lenta, probablemente debido a la copia de los datos de objetos alrededor.

Otro cambio en el que también estoy pensando es eliminar la Pairclase y reemplazarla std::shared_ptrpor "empujar" todos los métodos Pair::Blob, pero esto no me ayudará con la Pair::Blobclase de tamaño variable .

Me pregunto cómo puedo mejorar el diseño del objeto para ser más amigable con C ++.

El código fuente completo está aquí:
https://github.com/nmmmnu/HM3

c++ c++11 pointers smart-pointer Mella
fuente
2
¿Por qué no usas std::mapo std::unordered_map? ¿Por qué algunos valores (asociados a claves) son algunos void*? Probablemente necesite destruirlos en algún momento; ¿como cuando? ¿Por qué no usas plantillas?
Basile Starynkevitch
No uso std :: map, porque creo (o al menos lo intento) hacer algo mejor que std :: map para el caso actual. Pero sí, en algún momento estoy pensando en envolver std :: map y verificar su rendimiento como IList también.
Nick
La desasignación y la llamada a d-tors se realiza donde está el elemento IList::removeo cuando se destruye IList. Lleva mucho tiempo, pero lo voy a hacer en hilo separado. Será fácil porque IList lo será de std::unique_ptr<IList>todos modos. así que podré "cambiarlo" con una nueva lista y guardar el objeto antiguo en algún lugar donde pueda llamar a d-tor.
Nick
Intenté plantillas. No son la mejor solución aquí, porque esta no es una biblioteca de usuario, la clave siempre es C stringy los datos siempre son algún búfer void *o char *, por lo que puede pasar la matriz de caracteres. Puedes encontrar similar en rediso memcached. En algún momento, podría decidir usar std::stringuna matriz de caracteres fija o fija para la clave, pero subrayar que seguirá siendo una cadena C.
Nick
66
En lugar de agregar 4 comentarios, debe editar su pregunta
Basile Starynkevitch

Respuestas:

3

El enfoque que recomendaría es centrarse en la interfaz de su tienda de valores clave, para que sea lo más limpia posible y lo más restrictiva posible, lo que significa que debería permitir la máxima libertad a las personas que llaman, pero también la máxima libertad para elegir cómo implementarlo

Luego, recomendaría que proporcione una implementación lo más simple posible y lo más limpia posible, sin ninguna preocupación de rendimiento. Para mí, parece que unordered_mapdebería ser su primera opción, o tal vez mapsi la interfaz debe exponer algún tipo de orden de teclas.

Entonces, primero haga que funcione de manera limpia y mínima; luego, póngalo en uso en una aplicación real; al hacerlo, encontrará qué problemas debe abordar en la interfaz; luego, adelante y diríjase a ellos. La mayoría de las posibilidades son que, como resultado de cambiar la interfaz, necesitará reescribir grandes partes de la implementación, por lo que cada vez que haya invertido en la primera iteración de la implementación más allá del tiempo mínimo necesario para llevarla a cabo apenas el trabajo es tiempo perdido.

Luego, perfílelo y vea qué necesita mejorar en la implementación, sin alterar la interfaz. O puede tener sus propias ideas sobre cómo mejorar la implementación, incluso antes de perfilar. Eso está bien, pero todavía no es motivo para trabajar en estas ideas en ningún momento anterior.

Dices que esperas hacerlo mejor que map; Hay dos cosas que se pueden decir al respecto:

a) probablemente no lo harás;

b) evitar la optimización prematura a toda costa.

Con respecto a la implementación, su problema principal parece ser la asignación de memoria, ya que parece estar preocupado por cómo estructurar su diseño para solucionar los problemas que prevé que tendrá con respecto a la asignación de memoria. La mejor manera de abordar los problemas de asignación de memoria en C ++ es implementar una gestión de asignación de memoria adecuada, no torciendo y doblando el diseño a su alrededor. Debería considerarse afortunado de estar usando C ++, lo que le permite hacer su propia administración de asignación de memoria, a diferencia de los lenguajes como Java y C #, donde está bastante atrapado con lo que el tiempo de ejecución del lenguaje tiene para ofrecer.

Hay varias formas de administrar la memoria en C ++, y la capacidad de sobrecargar al newoperador puede ser útil. Un asignador de memoria simplista para su proyecto preasignaría una gran variedad de bytes y lo usaría como un montón. ( byte* heap.) Tendría un firstFreeByteíndice, inicializado a cero, que indica el primer byte libre en el montón. Cuando Nllega una solicitud de bytes, devuelve la dirección heap + firstFreeBytey agrega Na firstFreeByte. Por lo tanto, la asignación de memoria se vuelve tan rápida y eficiente que prácticamente no es un problema.

Por supuesto, la asignación previa de toda su memoria puede no ser una buena idea, por lo que es posible que tenga que dividir su montón en bancos que se asignan a pedido y seguir atendiendo las solicitudes de asignación del banco más nuevo en cualquier momento.

Como sus datos son inmutables, esta es una buena solución. Le permite abandonar la idea de los objetos de longitud variable y hacer que cada uno Paircontenga un puntero a sus datos como debería, ya que la asignación de memoria adicional para los datos no cuesta prácticamente nada.

Si desea poder descartar objetos del montón, para poder recuperar su memoria, entonces las cosas se vuelven más complicadas: necesitará usar no punteros, sino punteros a punteros, para que siempre pueda mover objetos. alrededor en los montones para reclamar el espacio de los objetos eliminados. Todo se vuelve un poco más lento debido a la indirección adicional, pero todo sigue siendo extremadamente rápido en comparación con el uso de rutinas de asignación de memoria de biblioteca de tiempo de ejecución estándar.

Pero, por supuesto, todo esto es realmente inútil si no se construye primero una versión de su base de datos, sencilla y mínima, y ​​se pone en uso en una aplicación real.

Mike Nakis
fuente