Armazenamento ideal da estrutura de dados para pesquisa rápida e persistência

Question

Cenário

Eu tenho os seguintes métodos:

public void AddItemSecurity(int itemId, int[] userIds)
public int[] GetValidItemIds(int userId)

Inicialmente estou pensando em armazenamento no formulário:

itemId -> userId, userId, userId

e

userId -> itemId, itemId, itemId

AddItemSecurity é baseado em como obtenho dados de uma API de terceiros, GetValidItemIds é como eu quero usá-lo em tempo de execução.

Existem potencialmente 2.000 usuários e 10 milhões de itens.Os IDs dos itens estão no formulário:2007123456, 2010001234 (10 dígitos onde os quatro primeiros representam o ano).

AddItemSecurity não precisa ter um desempenho super rápido, mas GetValidIds precisa ser subsegundo.Além disso, se houver uma atualização em um itemId Preciso remover esse itemId para usuários que não estão mais na lista.

Estou tentando pensar em como devo armazenar isso da maneira ideal.De preferência em disco (com cache), mas quero que o código possa ser mantido e limpo.

Se o ID do item começasse em 0, pensei em criar uma matriz de bytes com o comprimento de MaxItemId / 8 para cada usuário e defina um bit verdadeiro/falso se o item estava presente ou não.Isso limitaria o comprimento do array a pouco mais de 1 MB por usuário e proporcionaria pesquisas rápidas, bem como uma maneira fácil de atualizar a lista por usuário.Ao persistir isso como Arquivos mapeados na memória com a estrutura .Net 4, acho que também obteria um cache decente (se a máquina tiver RAM suficiente) sem implementar a lógica de cache sozinho.Analisar o ID, eliminar o ano e armazenar uma matriz por ano pode ser uma solução.

A lista ItemId -> UserId[] pode ser serializada diretamente no disco e leitura/gravação com um normal FileStream para persistir a lista e diferenciá-la quando houver alterações.

Cada vez que um novo usuário é adicionado, todas as listas também devem ser atualizadas, mas isso pode ser feito todas as noites.

Pergunta

Devo continuar a experimentar esta abordagem ou existem outros caminhos que também deveriam ser explorados?Estou pensando que o SQL Server não terá um desempenho rápido o suficiente e causaria uma sobrecarga (pelo menos se estiver hospedado em um servidor diferente), mas minhas suposições podem estar erradas.Qualquer pensamento ou visão sobre o assunto é apreciado.E quero tentar resolver isso sem adicionar muito hardware :)

[Atualização 31/03/2010]

Agora testei com o SQL Server 2008 nas seguintes condições.

• Tabela com duas colunas (userid, itemid) ambas são Int
• Índice clusterizado nas duas colunas
• Adicionados aproximadamente 800.000 itens para 180 usuários – total de 144 milhões de linhas
• 4 GB de RAM alocados para servidor SQL
• Notebook Dual Core 2,66 GHz
• Disco SSD
• Use um SqlDataReader para ler todos os itens em uma lista
• Loop sobre todos os usuários

Se eu executar um thread, a média será de 0,2 segundos.Quando adiciono um segundo thread, ele sobe para 0,4 segundos, o que ainda está ok.A partir daí os resultados vão diminuindo.Adicionar um terceiro tópico traz muitas consultas para até 2 segundos.Um quarto thread, de até 4 segundos, um quinto aumenta algumas das consultas em até 50 segundos.

A CPU está funcionando enquanto isso acontece, mesmo em um thread.Meu aplicativo de teste demora um pouco devido ao loop rápido e sql o resto.

O que me leva à conclusão de que não será muito bem dimensionado.Pelo menos não no meu hardware testado.Existem maneiras de otimizar o banco de dados, digamos, armazenando uma matriz de inteiros por usuário em vez de um registro por item.Mas isso torna mais difícil a remoção de itens.

[Atualização 31/03/2010 nº 2]

Fiz um teste rápido com os mesmos dados colocando-os como bits em arquivos mapeados na memória.Ele tem um desempenho muito melhor.Seis threads produzem tempos de acesso entre 0,02s e 0,06s.Puramente ligado à memória.Os arquivos mapeados foram mapeados por um processo e acessados ​​por outros seis simultaneamente.E como a base sql ocupava 4gb, os arquivos em disco ocupavam 23mb.

Answer 1

Depois de muitos testes acabei usando Memory Mapped Files, marcando-os com o bit esparso (NTFS), usando o código do Arquivos esparsos NTFS com C#.

A Wikipedia tem uma explicação sobre o que é um arquivo esparso é.

Os benefícios de usar um arquivo esparso é que não preciso me preocupar com o intervalo em que meus IDs estão.Se eu escrever apenas IDs entre 2006000000 e 2010999999, o arquivo alocará apenas 625.000 bytes do deslocamento 250.750.000 no arquivo.Todo o espaço até esse deslocamento não será alocado no sistema de arquivos.Cada ID é armazenado como um bit definido no arquivo.Tipo de tratado como uma matriz de bits.E se a sequência de id mudar repentinamente, ela será alocada em outra parte do arquivo.

Para recuperar quais IDs estão definidos, posso realizar uma chamada do sistema operacional para obter as partes alocadas do arquivo esparso e, em seguida, verifico cada bit nessas sequências.Verificar também se um ID específico está definido é muito rápido.Se estiver fora dos blocos alocados, então não está lá; se estiver dentro, é apenas uma leitura de byte e uma verificação de máscara de bits para ver se o bit correto está definido.

Portanto, para o cenário específico em que você tem muitos IDs que deseja verificar com o máximo de velocidade possível, esta é a maneira mais ideal que encontrei até agora.

E a parte boa é que os arquivos mapeados na memória também podem ser compartilhados com Java (o que acabou sendo necessário).Java também oferece suporte para arquivos mapeados em memória no Windows, e implementar a lógica de leitura/gravação é bastante trivial.

Answer 2

Eu realmente acho que você deveria tentar um bom banco de dados antes de tomar sua decisão.Algo assim será um desafio de manter no longo prazo.Na verdade, sua base de usuários é bem pequena.O SQL Server deve ser capaz de lidar com o que você precisa sem problemas.

Answer 3

2.000 usuários não é tão ruim, mas com 10 mil itens relacionados você realmente deveria considerar colocar isso em um banco de dados.Os bancos de dados fazem todo o armazenamento, persistência, indexação, cache, etc.que você precisa e eles funcionam muito bem.

Eles também permitem melhor escalabilidade no futuro.Se de repente você precisar lidar com dois milhões de usuários e bilhões de configurações, ter um bom banco de dados em vigor tornará o dimensionamento um problema.