Armazenamento de lista dupla com dupla ligação (ou outro) em disco para o sistema de fila; opções de como armazenar

5

Estou pensando em criar uma biblioteca de enfileiramento de mensagens no Go, que será usada como parte de um aplicativo maior. Uma lista duplamente vinculada parece ser uma abordagem sensata para uma estrutura de dados em memória, mas digamos que essa lista cresça para 4 milhões de itens e cada item seja 10k, as coisas não terão mais garantia de caber na memória, mais eu preciso disso para ser persistente nas reinicializações.

A maior parte da atividade na fila estará gravando no final e lendo e excluindo desde o início, no entanto, há casos em que o consumo de uma mensagem pode falhar por motivos não relacionados à fila e o item precisa ser movido para a fila. fim da fila.

Estou familiarizado com algumas estruturas de dados que funcionam bem no disco para outros casos específicos. Uma árvore de mesclagem estruturada em log parece ser ótima para dados de acesso aleatório, mas não quando as leituras e gravações são localizadas no final e no início da árvore (com base em meu entendimento). B Trees e B + Trees também parecem mais destinados ao acesso aleatório e ao percurso.

Curioso que existem algoritmos ou abordagens que já estão adaptados para este problema.

NOTA: Em relação ao SQLite, uma das minhas preocupações é o tempo de compactação. É provável que o conteúdo da fila seja de alta rotatividade e é importante que qualquer tipo de compactação que precise ser feita possa acontecer em um conjunto de dados bastante grande sem um impacto muito grande no desempenho. Ou seja se houver 4G de mensagens sentadas na fila, não quero um cenário em que as coisas fiquem bloqueadas por 2 minutos enquanto ele faz compactação, que é o que eu suspeito que acontecerá com o SQLite.

    
por Brad Peabody 01.06.2017 / 21:36
fonte

3 respostas

3

Acho que tenho informações suficientes para fornecer uma resposta. Pode não ser o que você está procurando, no entanto.

Do que discutimos e entendemos, temos o seguinte cenário:

  • Grande número de mensagens a serem processadas;
  • Persistência necessária para lidar com reinicializações limpas (não estou falando de picos de energia ou falta de energia);
  • Tamanho inconsistente de cada mensagem;
  • A necessidade de estrutura FIFO;
  • Possibilidade de usar o sistema de arquivos como armazenamento;
  • Precisa ser portátil, dentro de ambientes suportados (MacOS, Linux, Windows);
  • Precisa ser auto-hospedado, não pode usar um provedor de fila externo;

Dito isso, eu arquiterei algo que dependesse 100% do sistema de arquivos.

Armazene cada mensagem como um único arquivo, nomeie-as com um timestamp ou um contador que você pode controlar de uma fonte confiável e aproveite os recursos do sistema de arquivos para você.

Você seria limitado pelo que o sistema de arquivos pode fazer por você (número de arquivos por diretório, número de diretórios por disco, tamanho máximo por arquivo, etc.), mas é muito flexível, fácil de depurar e monitorar e extremamente portátil e flexível, permitindo que você aumente a velocidade do seu IO mudando apenas o hardware (HD - > SSD - > Raid - > Storage Server, etc.).

Você terá que estudar diferentes sistemas de arquivos para empurrar cada um para os limites, mas o os mais comuns podem lidar com estes requisitos muito bem:

Os dados abaixo são copiados da excelente resposta no StackOverflow :

FAT32 :

  • Número máximo de arquivos: 268.173.300
  • Número máximo de arquivos por diretório: 2 16 - 1 (65,535)
  • Tamanho máximo do arquivo: 2 GiB - 1 sem LFS , 4 GiB - 1 com

NTFS :

  • Número máximo de arquivos: 2 32 - 1 (4.294.967.295)
  • Tamanho máximo do arquivo
    • Implementação: 2 44 - 2 6 bytes (16 TiB - 64 KiB)
    • Teórico: 2 64 - 2 6 bytes (16 EiB - 64 KiB)
  • Tamanho máximo do volume
    • Implementação: 2 32 - 1 clusters (256 TiB - 64 KiB)
    • Teórico: 2 64 - 1 clusters

ext2 :

  • Número máximo de arquivos: 10 18
  • Número máximo de arquivos por diretório: ~ 1,3 × 10 20 (problemas de desempenho após 10.000)
  • Tamanho máximo do arquivo
    • 16 GiB (tamanho do bloco de 1 KiB)
    • 256 GiB (tamanho do bloco de 2 KiB)
    • 2 TiB (tamanho do bloco de 4 KiB)
    • 2 TiB (tamanho do bloco de 8 KiB)
  • Tamanho máximo do volume
    • 4 TiB (tamanho do bloco de 1 KiB)
    • 8 TiB (tamanho do bloco de 2 KiB)
    • 16 TiB (tamanho do bloco de 4 KiB)
    • 32 TiB (tamanho do bloco de 8 KiB)

ext3 :

  • Número máximo de arquivos: min (volumeSize / 2 13 , numberOfBlocks)
  • Tamanho máximo do arquivo: igual ao ext2
  • Tamanho máximo do volume: o mesmo que ext2

ext4 :

  • Número máximo de arquivos: 2 32 - 1 (4.294.967.295)
  • Número máximo de arquivos por diretório: ilimitado
  • Tamanho máximo do arquivo: 2 44 - 1 bytes (16 TiB - 1)
  • Tamanho máximo do volume: 2 48 - 1 bytes (256 TiB - 1)
por 02.06.2017 / 18:34
fonte
1

Outra maneira de abordar isso é basicamente armazenar as mensagens em blocos de tamanho razoável, e cada bloco é armazenado em um arquivo no disco e lido (ou possivelmente mapeado por mem) para uso na memória quando necessário .

Blocos podem ter, por exemplo, 64MB cada. Cada um é um arquivo, nomeado com timestamp e número aleatório. A finalidade de agrupar as mensagens é evitar que uma proliferação de pequenas mensagens crie um gargalo no nível do sistema de arquivos. Se a contagem de mensagens chegar aos milhões, pode ser difícil navegar com eficiência no FS para encontrar a primeira e a última mensagem. Os tamanhos dos blocos devem ser maiores que a maior mensagem possível e devem ser garantidos para caber na memória pelo menos alguns de cada vez.

O prefixamento de pastas pode ser usado para simplificar a navegação. Ou seja se o registro de data e hora do arquivo for 201706021852, ele poderá estar na pasta 20170602/18. O prefixo poderia ser configurável para diferentes volumes de mensagens previstas, se necessário.

Quando os blocos são lidos na memória, uma lista duplamente vinculada funcionaria como a representação na memória. O primeiro eo último bloco devem ser facilmente encontrados no disco, rastreando a estrutura da pasta, esses blocos são carregados na memória e, em seguida, as versões na memória funcionaram - mensagens sendo empurradas para trás e estouradas da frente. Mensagens em um bloco quando consumidas podem simplesmente ser sinalizadas como tal e quando todas as mensagens no bloco são consumidas, o bloco é deletado.

A intervalos que forem apropriados, os blocos carregados serão liberados para o disco e tudo o que for executado fsync (). As operações com garantia de serem atômicas (renomear) seriam usadas para saber com segurança se sua gravação foi bem-sucedida.

A estrutura acima deve funcionar bem se você nunca precisar encontrar uma mensagem no meio da fila (o que exigiria uma varredura completa de todos os blocos).

    
por 03.06.2017 / 05:57
fonte
0

E outra solução seria usar apenas uma tabela SQLite. Internamente, o SQLite usa árvores binárias para os dados e índices da tabela (não especificamente otimizados para leituras e gravações de cabeçalhos e margens, mas também não são particularmente ineficientes). E vai reutilizar páginas que ficam completamente disponíveis. Pode muito bem ser que o SQLite faça o trabalho com desempenho razoável e nunca exija compactação (uma vez que uma fila consumida em seqüência deve, teoricamente, remover completamente as páginas completas, já que todos os registros serão excluídos em seqüência). Precisa ser testado.

    
por 03.06.2017 / 06:08
fonte