Estou desenvolvendo um servidor de banco de dados semelhante ao Cassandra.
O desenvolvimento foi iniciado em C, mas as coisas se tornaram muito complicadas sem classes.
Atualmente, eu portado tudo em C ++ 11, mas ainda estou aprendendo C ++ "moderno" e tenho dúvidas sobre muitas coisas.
O banco de dados funcionará com pares de chave / valor. Cada par tem mais informações - quando é criado também quando expira (0 se não expirar). Cada par é imutável.
A chave é a cadeia C, o valor é nulo *, mas pelo menos no momento estou operando com o valor como a cadeia C também.
Há IList
classe abstrata . É herdado de três classes
VectorList
- matriz dinâmica C - semelhante ao std :: vector, mas usarealloc
LinkList
- feito para verificações e comparação de desempenhoSkipList
- a classe que finalmente será usada.
No futuro, eu também poderia fazer Red Black
árvores.
Cada um IList
contém zero ou mais ponteiros para pares, classificados por chave.
Se IList
ficar muito tempo, ele pode ser salvo no disco em um arquivo especial. Esse arquivo especial é meio que read only list
.
Se você precisar procurar uma chave,
- o primeiro na memória
IList
é pesquisado (SkipList
,SkipList
ouLinkList
). - Em seguida, a pesquisa é enviada para os arquivos classificados por data
(primeiro arquivo mais recente, arquivo mais antigo - último).
Todos esses arquivos são mmap-ed na memória. - Se nada for encontrado, a chave não será encontrada.
Não tenho dúvidas sobre a implementação das IList
coisas.
O que está me intrigando atualmente é o seguinte:
Os pares têm tamanhos diferentes , são alocados por new()
e std::shared_ptr
apontaram para eles.
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];
};
A variável de membro "buffer" é aquela com tamanho diferente. Ele armazena a chave + valor.
Por exemplo, se a chave tiver 10 caracteres e o valor tiver outros 10 bytes, o objeto inteiro será sizeof(Pair::Blob) + 20
(o buffer terá tamanho inicial de 2, devido a dois bytes de terminação nulos)
Esse mesmo layout também é usado no disco, para que eu possa fazer algo assim:
// 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);
No entanto, esse tamanho diferente é um problema em muitos lugares com código C ++.
Por exemplo, eu não posso usar std::make_shared()
. Isso é importante para mim, porque se eu tiver pares de 1 milhão, eu teria alocações de 2 milhões.
Por outro lado, se eu fizer "buffer" em um array dinâmico (por exemplo, novo char [123]), perderei o "truque" do mmap, terei duas desreferências se quiser verificar a chave e adicionarei um ponteiro único - 8 bytes para a classe.
Também tentei "puxar" todos os membros para Pair::Blob
dentro Pair
, Pair::Blob
para ser apenas o buffer, mas quando o testei, era bastante lento, provavelmente por causa da cópia dos dados do objeto.
Outra mudança que também estou pensando é remover a Pair
classe e substituí-la por std::shared_ptr
e "empurrar" todos os métodos de volta Pair::Blob
, mas isso não vai me ajudar com a Pair::Blob
classe de tamanho variável .
Eu estou querendo saber como posso melhorar o design do objeto para ser mais amigável ao C ++.
O código fonte completo está aqui:
https://github.com/nmmmnu/HM3
fonte
std::map
oustd::unordered_map
? Por que os valores (associados às chaves) são algunsvoid*
? Você provavelmente precisaria destruí-los em algum momento; como e quando? Por que você não usa modelos?IList::remove
ou quando o IList é destruído. Leva muito tempo, mas vou fazer em um tópico separado. Será fácil porque o IList serástd::unique_ptr<IList>
assim mesmo. então poderei "alternar" com a nova lista e manter o objeto antigo em algum lugar onde eu possa chamar d-tor.C string
e os dados sempre são um buffervoid *
ouchar *
, portanto, você pode passar o array de caracteres. Você pode encontrar similar emredis
oumemcached
. Em algum momento, eu poderia decidir usarstd::string
ou fixar a matriz de caracteres para a chave, mas sublinhe que ainda será uma string C.Respostas:
A abordagem que eu recomendaria é focar na interface do seu armazenamento de valores-chave, de modo a torná-lo o mais limpo possível e o mais irrestrito possível, o que significa que deve permitir a máxima liberdade para os chamadores, mas também a máxima liberdade para escolher como implementá-lo.
Então, recomendo que você forneça uma implementação o mais simples possível e o mais limpa possível, sem nenhum problema de desempenho. Para mim, parece que
unordered_map
deve ser sua primeira escolha, ou talvezmap
se algum tipo de pedido de chaves deve ser exposto pela interface.Portanto, primeiro faça com que funcione de maneira limpa e minimalista; depois, use-o em um aplicativo real; ao fazer isso, você encontrará os problemas que precisa resolver na interface; então, vá em frente e resolva-os. A maioria das chances é de que, como resultado da alteração da interface, você precisará reescrever grandes partes da implementação; portanto, sempre que já tiver investido na primeira iteração da implementação além do tempo mínimo necessário para obtê-la apenas mal trabalho é perda de tempo.
Em seguida, crie um perfil e veja o que precisa ser aprimorado na implementação, sem alterar a interface. Ou você pode ter suas próprias idéias sobre como melhorar a implementação, antes mesmo de criar um perfil. Tudo bem, mas ainda não há razão para trabalhar nessas idéias em um momento anterior.
Você diz que espera fazer melhor que
map
; há duas coisas que podem ser ditas sobre isso:a) você provavelmente não;
b) evitar otimização prematura a todo custo.
No que diz respeito à implementação, seu principal problema parece ser alocação de memória, pois você parece estar preocupado com a forma de estruturar seu design, a fim de solucionar os problemas que você prevê ter em relação à alocação de memória. A melhor maneira de resolver os problemas de alocação de memória no C ++ é implementando um gerenciamento de alocação de memória adequado, não distorcendo e dobrando o design ao seu redor. Você deve considerar-se sortudo por estar usando C ++, o que permite que você faça seu próprio gerenciamento de alocação de memória, em oposição a linguagens como Java e C #, nas quais você está praticamente preso ao que o runtime de linguagem tem a oferecer.
Existem várias maneiras de lidar com o gerenciamento de memória em C ++, e a capacidade de sobrecarregar o
new
operador pode ser útil. Um alocador de memória simplista para o seu projeto pré-alocaria uma enorme matriz de bytes e a usaria como um heap. (byte* heap
.) Você teria umfirstFreeByte
índice, inicializado em zero, que indica o primeiro byte livre no heap. Quando uma solicitação deN
bytes chega, você retorna o endereçoheap + firstFreeByte
e adicionaN
afirstFreeByte
. Portanto, a alocação de memória se torna tão rápida e eficiente que praticamente não se torna problema.Obviamente, pré-alocar toda a sua memória pode não ser uma boa ideia; portanto, talvez seja necessário dividir sua pilha em bancos alocados sob demanda e continuar atendendo solicitações de alocação do banco a qualquer momento.
Como seus dados são imutáveis, esta é uma boa solução. Ele permite que você abandone a idéia de objetos de comprimento variável e que cada
Pair
um contenha um ponteiro para seus dados como deveria, pois a alocação de memória extra para os dados não custa praticamente nada.Se você deseja descartar objetos da pilha, para recuperar sua memória, as coisas ficam mais complicadas: você precisará usar não ponteiros, mas ponteiros para ponteiros, para poder sempre mover objetos nos montes, de modo a recuperar o espaço dos objetos excluídos. Tudo se torna um pouco mais lento devido à indireção extra, mas tudo ainda é muito rápido em comparação ao uso de rotinas de alocação de memória da biblioteca de tempo de execução padrão.
Mas é claro que tudo isso é realmente inútil para se preocupar, se você não criar primeiro uma versão simples e simples do seu banco de dados e usá-la em um aplicativo real.
fonte