Digitalizando um bilhão de linhas em um banco de dados ultrarrápido

fundo

Um banco de dados local contém quase 1,3 bilhão de linhas exclusivas. Cada linha é indiretamente associada a uma latitude e longitude específica (local). Cada linha tem um carimbo de data.

Caso de Uso

O problema é o seguinte:

1. O usuário define uma data de início / término e um intervalo de valores (por exemplo, 100 a 105).
2. O sistema reúne todas as linhas que correspondem à data especificada, agrupadas por local.
3. O desempenho do sistema determina os locais que, durante essas datas, têm uma probabilidade estatística de cair no intervalo de valores especificado.
4. O sistema exibe todos os locais correspondentes ao usuário.

Este é um problema de velocidade e escala.

Questão

Qual é a arquitetura de solução mais barata que você pode imaginar que permitiria que esse sistema recuperasse resultados para os usuários em menos de cinco segundos?

Sistema atual

O ambiente é atualmente:

• PostgreSQL 8.4 (a atualização é possível; alternar bancos de dados não é uma opção)
• R e PL / R
• XFS
• WD VelociRaptor
• 8 GB de RAM (Corsair G.Skill; 1,3 GHz)
• Intel Core 7 Quad-core (2,8 GHz)
• Ubuntu 10.10

Atualizações de hardware são aceitáveis.

Atualização - Estrutura do Banco de Dados

Os bilhões de linhas estão em uma tabela semelhante a:

id | taken | location_id | category | value1 | value2 | value3

• id - chave primária
• taken - Data atribuída à linha
• location_id - referência à latitude / longitude
• categoria - Uma descrição dos dados
• valor1 .. 3 - Os outros valores que o usuário pode consultar

A takencoluna é tipicamente datas consecutivas por location_id, às vezes cada local possui dados de 1800 a 2010 (cerca de 77.000 datas, muitas delas duplicadas, pois cada local possui dados no mesmo período).

Existem sete categorias e as tabelas já estão divididas por categoria (usando tabelas filho). Cada categoria contém ~ 190 milhões de linhas. Num futuro próximo, o número de linhas por categoria excederá um bilhão.

Existem aproximadamente 20.000 locais e 70.000 cidades. Os locais são correlacionados à cidade por latitude e longitude. Atribuir cada local a uma cidade específica significa encontrar os limites da cidade, o que não é uma tarefa trivial.

Ideias

Algumas idéias que tenho incluem:

• Encontre um serviço de nuvem para hospedar o banco de dados.
• Crie uma faixa de ataque SSD (ótimo vídeo).
• Crie uma tabela que junte todos os locais por cidade (pré-cálculo).

Obrigado!

O mais importante é ter certeza absoluta de onde o gargalo está agora para um determinado número de solicitações representativas, pois você não pode alternar os bancos de dados.

Se você fizer varreduras completas da tabela, precisará de índices apropriados.

Se você esperar a E / S, precisará de mais memória para armazenar em cache (Jeff Atwood mencionou recentemente que os sistemas de 24 Gb eram acessíveis em sistemas de desktop).

Se você esperar na CPU, precisará ver se seus cálculos podem ser otimizados.

Isso requer um chapéu pontudo de DBA e um chapéu de sistema operacional, mas vale a pena garantir que você esteja latindo na árvore certa.

Que tal particionar a tabela em várias partes localizadas em hosts diferentes com base no carimbo de data? É escalável horizontalmente e, desde que você tenha um número suficiente de caixas, você pode escrever um pequeno mecanismo de agregação sobre essas configurações.

Se você perceber que o carimbo de data está mudando muito, poderá particionar com base nos locais - novamente escalável horizontalmente. (Espero que eles não adicionem muito mais latitudes / longitudes!)

O pior cenário é o período que abrange todas as datas no seu banco de dados.

Você está procurando ler 1,3 bilhão de registros e fazer algum tipo de análise em cada registro versus os valores inseridos, em uma máquina física, em menos de 5 segundos. O resultado pode ser em todos os locais ou nenhum - você não sabe nada com antecedência.

Dados esses parâmetros, eu diria que provavelmente é impossível.

Basta olhar para o seu disco rígido: a taxa máxima sustentada é inferior a 150 MB / s. A leitura de 1,3 bilhão de registros levará mais de 5 segundos. Em termos de CPU, você não poderá fazer nenhum tipo de análise estatística em 1,3 bilhão de registros em 5 segundos.

Sua única esperança (tm :-)) é encontrar algum tipo de função de pesquisa com base nos valores inseridos pelo usuário que restringirão a pesquisa (em algumas ordens de magnitude). Você pode calcular essa função de pesquisa offline. Sem saber mais sobre os critérios de correspondência exata, acho que ninguém pode lhe dizer como fazer isso, mas um exemplo seria particionar o intervalo de valores em algum intervalo discreto e criar uma pesquisa que fornece todos os registros nesse intervalo. Contanto que o intervalo seja pequeno o suficiente, você poderá fazer um trabalho real, por exemplo, remover as entradas que não correspondem ao valor inserido pelo usuário. Basicamente trocando espaço por tempo.

Pode ser possível manter todos os registros (ou pelo menos a parte importante) na memória. Provavelmente não em 8GB. Isso eliminará pelo menos a parte de E / S do disco, embora até a largura de banda da memória seja insuficiente para verificar tudo em 5 segundos. De qualquer forma, essa é outra técnica para acelerar esse tipo de aplicativo (combine com minha sugestão anterior).

Você menciona o uso de um serviço em nuvem. Sim, se você pagar por CPU e IO suficientes e particionar seu banco de dados em muitos servidores, poderá forçar / dividir brutalmente e conquistá-lo.

Em segundo lugar, comentei o comentário de rwong à pergunta: O PostgreSQL oferece tipos e ferramentas de índices apropriados (índices GIST, GIN, Postgis, tipos geométricos) de forma que os dados geodados e os dados relacionados à data e hora sejam pesquisáveis ​​por esses critérios sem muitos problemas.

Se suas consultas sobre esses critérios levarem segundos, provavelmente significa que nenhum índice está sendo usado. Você pode confirmar que as investigou conforme apropriado?

Como você usa o PostgreSQL e os dados de latitude / longitude, você também deve definitivamente usar o PostGIS, para adicionar um índice espacial do GiST ao seu banco de dados para ajudar a acelerar as coisas.

Eu tenho uma tabela desse tipo (com linhas de 350k) com uma configuração muito menor que a sua (2 núcleos e apenas 2 GB de RAM), mas as pesquisas demoram menos de um segundo.

Talvez você possa quebrar um modelo relacional como o Essbase fez com sua arquitetura OLAP: Essbase Wikipedia

O que quero dizer é criar uma tabela por cidade, terminando assim com mais de 1000 tabelas. Não é uma tabela como você sugeriu, mas muitas. Indexe cada tabela por data e local. Muitas tabelas, muitos índices -> mais rápidos.

Quanto à sua ideia de encontrar um serviço em nuvem para hospedar o banco de dados, você já encontrou o SimpleGeo ? Eles apenas cortaram a faixa de opções em um serviço de armazenamento aparentemente "especificamente ajustado para armazenar e consultar dados de localização muito, muito rápido" - embora o custo para armazenar e consultar mais de um bilhão de linhas possa inviabilizar essa abordagem.

você está esperando uma bicicleta correr na estrada. Atualmente, você está procurando uma solução para resolver esse problema apenas, não está prevendo o problema, e se você tiver 2 bilhões de registros? escalabilidade deve ser tratada. resposta é simples usar bancos de dados de objetos. por exemplo, cache Intersystems

e acredite em mim eu não sou de intersistemas ;-)