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

9

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!

Dave Jarvis
fonte
10
"alternar bancos de dados não é uma opção", que praticamente elimina a maioria das soluções. boa sorte!
Steven A. Lowe
11
É difícil dizer sem mais informações sobre o que exatamente você está fazendo com esses registros. Além disso, você está procurando o pior caso de 5 segundos (o que provavelmente significa que todos os registros examinados e zero locais coincidem)?
Guy Sirton 25/05
2
@ Dave: Quanto tempo leva o sistema atual? O sistema atual está usando o PostGIS ? É location_idum geographyou geometry, ou se refere a uma segunda tabela? A location_idcoluna está indexada?
rwong 25/05
11
@ Thorbjørn e @Darknight - Na seção de idéias, listo o pré-cálculo, que reduziria os dados a um valor por cidade por dia (por categoria). O cálculo pode se repetir anualmente, ou até mensalmente, suponho. Esse era meu plano se não houvesse outras possibilidades (os cálculos provavelmente levarão semanas).
Dave Jarvis
11
@ Dave, muitas possibilidades, mas a questão é o que é relevante para você. Você já investigou onde estão os gargalos atuais?

Respostas:

12

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.


fonte
Seja como for, você o corta e corta - mesmo que cada linha use apenas 100 bytes, 1,3 bilhão de linhas = 121 GB. Com todos os seus índices, etc., tenho certeza que isso será muito mais. Em uma única caixa, você ficará lento, a menos que tenha algum hardware sério em torno de SSD + toneladas de RAM. A maneira mais barata é escalar as caixas.
Subu Sankara Subramanian
4
@ Subu, você quer ir distribuído? Agora você tem dois problemas ...
Heh - com quem concordo :) Mas é mais barato!
Subu Sankara Subramanian
@ Thorbjørn: Obrigado pelo seu tempo e toda a sua ajuda. Acho que vou reduzir o conjunto de dados para 25 milhões de linhas por categoria e depois aplicar índices na data. Isso deve reduzir a varredura para ~ 70000 linhas (por dia, com um limite de duas semanas para o intervalo), o que deve ser bastante rápido.
Dave Jarvis
@ Dave, você ainda precisa saber onde estão os seus gargalos. Aprenda enquanto você não precisa .
4

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!)

Subu Sankara Subramanian
fonte
Obrigado pelas idéias. Há potencialmente 77.066 datas e novas datas serão adicionadas daqui para frente. Eu tenho uma única máquina. Existem 20.000 locais, mas a divisão por local não ajudaria porque os dados a serem analisados ​​abrangem todos os locais.
Dave Jarvis
e como o uso da nuvem é diferente da solução acima?
Chani 25/05
Foi nisso que pensei também. Algum tipo de partição horizontal para que a pesquisa possa ocorrer paralelamente em todas as partições.
Davidk01 25/05
A divisão no dia provavelmente seria a mais útil, resultando em 2562 tabelas separadas (366 dias x 7 categorias).
Dave Jarvis
4

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.

Guy Sirton
fonte
Obrigado pela resposta. As atualizações de hardware são uma consideração, de acordo com as idéias que listei. Uma solução abaixo de US $ 750 seria o ideal.
Dave Jarvis
2

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?

Denis de Bernardy
fonte
Obrigado. As sete tabelas filhas estão agrupadas no local, data e categoria usando uma btree. Eu pesquisei índices GIN no ano passado e eles não ajudaram (ou não ajudariam), pelo que me lembro.
Dave Jarvis
2
A localização de indexação com base no B-Tree não é nem um pouco útil, considerando o tipo de pesquisa em que você está pesquisando. Você precisa de um índice invertido que funcione com os operadores necessários, o que no caso do Postgis geralmente significa GIST. Você pode querer destacar algumas das consultas lentas ...
Denis de Bernardy
1

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.

picos selvagens
fonte
0

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.

mihaela
fonte
Obrigado pela observação. Existem mais de 70.000 cidades e muitos valores diferentes de latitude / longitude se enquadram em uma área específica da cidade.
Dave Jarvis
@ Dave: você pode criar um diagrama de voronoi para cidades e classificar os valores de lat / lon em mosaicos? (ou seja, se parecer aleatório, deixe estar.) Em seguida, durante a pesquisa, você pesquisará todas as cidades cujo mosaico toque nos intervalos de lat / lon da consulta. Se o mosaico de voronoi for muito lento, vale a pena tentar caixas quadradas (por exemplo, 5 graus lat x 5 graus lon).
rwong 25/05
0

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.

IanI
fonte
-2

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 ;-)

anerjan
fonte