Skanowanie miliarda wierszy w ultraszybkiej bazie danych

tło

Lokalna baza danych zawiera prawie 1,3 miliarda unikalnych wierszy. Każdy rząd jest pośrednio powiązany z określoną szerokością i długością geograficzną (lokalizacją). Każdy wiersz ma datownik.

Przypadek użycia

Problem jest następujący:

1. Użytkownik ustawia datę początkową / końcową oraz zakres wartości (np. Od 100 do 105).
2. System zbiera wszystkie wiersze pasujące do podanej daty, pogrupowane według lokalizacji.
3. System określa lokalizacje, które w tych datach mają statystyczne prawdopodobieństwo wpadnięcia w podany zakres wartości.
4. System wyświetla użytkownikowi wszystkie pasujące lokalizacje.

Jest to problem prędkości i skali.

Pytanie

Jaka jest najtańsza architektura rozwiązania, jaką można sobie wyobrazić, która pozwoliłaby systemowi na uzyskanie wyników dla użytkowników w mniej niż pięć sekund?

Aktualny system

Środowisko jest obecnie:

• PostgreSQL 8.4 (aktualizacja jest możliwa; przełączanie baz danych nie jest opcją)
• R i PL / R
• XFS
• WD VelociRaptor
• 8 GB pamięci RAM (Corsair G.Skill; 1,3 GHz)
• Czterordzeniowy oryginalny Intel 7 (2,8 GHz)
• Ubuntu 10.10

Uaktualnienia sprzętu są dopuszczalne.

Aktualizacja - struktura bazy danych

Miliardy rzędów znajdują się w tabeli przypominającej:

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

• id - klucz podstawowy
• zajęte - data przypisana do wiersza
• location_id - Odniesienie do szerokości / długości geograficznej
• kategoria - opis danych
• wartość1 .. 3 - Inne wartości, które użytkownik może zapytać

takenKolumna jest zazwyczaj za kolejnymi datami location_id, czasem każda lokalizacja ma dane od 1800 do 2010 (około 77000 daty, wiele z nich powielone jak każda lokalizacja ma dane w tym samym przedziale czasowym).

Istnieje siedem kategorii, a tabele są już podzielone według kategorii (przy użyciu tabel potomnych). Każda kategoria zawiera ~ 190 milionów wierszy. W najbliższej przyszłości liczba wierszy na kategorię przekroczy miliard.

Istnieje około 20 000 lokalizacji i 70 000 miast. Lokalizacje są skorelowane z miastem na podstawie szerokości i długości geograficznej. Przypisanie każdej lokalizacji do konkretnego miasta oznacza znalezienie granic miasta, co nie jest łatwym zadaniem.

Pomysły

Oto niektóre pomysły, które mam:

• Znajdź usługę w chmurze, aby hostować bazę danych.
• Utwórz pasek RAID SSD (świetne wideo).
• Utwórz tabelę, która łączy wszystkie lokalizacje według miasta (wstępne obliczenia).

Dziękuję Ci!

Najważniejszą rzeczą jest być absolutnie pewnym, gdzie jest wąskie gardło dla określonej liczby reprezentatywnych żądań, ponieważ nie można przełączać baz danych.

Jeśli wykonujesz pełne skanowanie tabel, potrzebujesz odpowiednich indeksów.

Jeśli czekasz na I / O, potrzebujesz więcej pamięci do buforowania (Jeff Atwood wspomniał ostatnio, że systemy 24 Gb są dostępne na komputerach stacjonarnych).

Jeśli zaczekasz na procesor, musisz sprawdzić, czy Twoje obliczenia można zoptymalizować.

Wymaga to spiczastego kapelusza DBA i kapelusza systemu operacyjnego, ale warto upewnić się, że szczekasz na właściwe drzewo.

Co powiesz na podzielenie tabeli na wiele części na różnych hostach na podstawie datownika? Jest to skalowalne w poziomie i tak długo, jak masz wystarczającą liczbę pól, możesz napisać mały silnik agregacji na tych konfiguracjach.

Jeśli zauważysz, że znacznik daty zmienia się zbyt mocno, możesz podzielić na partycje w oparciu o lokalizacje - ponownie skalowalne w poziomie. (Mam nadzieję, że nie dodają więcej szerokości i długości geograficznej!)

Najgorszym scenariuszem jest zakres dat obejmujący wszystkie daty w bazie danych.

Chcesz odczytać 1,3 miliarda rekordów i przeprowadzić jakąś analizę każdego rekordu w stosunku do wprowadzonych wartości, na jednej maszynie fizycznej, w mniej niż 5 sekund. Rezultatem mogą być wszystkie lokalizacje lub żadne - nic nie wiesz z góry.

Biorąc pod uwagę te parametry, powiedziałbym, że prawdopodobnie niemożliwe.

Wystarczy spojrzeć na dysk twardy: maksymalna szybkość utrzymywania się wynosi mniej niż 150 MB / s. Odczyt 1,3 miliarda rekordów zajmie więcej niż 5 sekund. Pod względem procesora nie będziesz w stanie przeprowadzić żadnej analizy statystycznej na 1,3 miliarda rekordów w 5 sekund.

Jedyną nadzieją (tm :-)) jest znalezienie funkcji wyszukiwania na podstawie wartości wprowadzonych przez użytkownika, która zawęzi wyszukiwanie (o kilka rzędów wielkości). Możesz obliczyć tę funkcję wyszukiwania offline. Nie wiedząc więcej o dokładnych kryteriach dopasowania, nie sądzę, aby ktokolwiek mógł ci powiedzieć, jak to zrobić, ale przykładem może być podzielenie zakresu wartości na jakiś dyskretny przedział i utworzenie wyszukiwania, które da ci wszystkie rekordy w tym przedziale. Dopóki odstęp jest wystarczająco mały, możesz wykonać w nim prawdziwą pracę, np. Przycinać wpisy, które nie pasują do wartości wprowadzonej przez użytkownika. Zasadniczo handel przestrzenią na czas.

Może być możliwe przechowywanie wszystkich zapisów (lub przynajmniej ważnej części) w pamięci. Prawdopodobnie nie w 8 GB. To przynajmniej wyeliminuje część dyskową we / wy, chociaż nawet przepustowość pamięci może być niewystarczająca do przeskanowania wszystkiego w ciągu 5 sekund. W każdym razie jest to kolejna technika przyspieszania tego rodzaju aplikacji (w połączeniu z moją poprzednią sugestią).

Wspominasz o użyciu usługi w chmurze. Tak, jeśli zapłacisz za wystarczającą liczbę procesorów i operacji we / wy i podzielisz bazę danych na wiele serwerów, możesz użyć siły / podzielić i podbić ją.

Drugi komentarz rwonga do pytania: PostgreSQL oferuje odpowiednie typy indeksów i narzędzia (indeksy GIST, indeksy GIN, Postgis, typy geometryczne) w taki sposób, że dane geodezyjne i dane związane z czasem i datą powinny być przeszukiwane według tych kryteriów bez większych problemów.

Jeśli twoje zapytania dotyczące tych kryteriów zajmują kilka sekund, prawdopodobnie oznacza to, że nie są używane takie indeksy. Czy możesz potwierdzić, że sprawdziłeś je odpowiednio?

Biorąc pod uwagę, że korzystasz z PostgreSQL oraz danych dotyczących szerokości i długości geograficznej, zdecydowanie powinieneś również użyć PostGIS, w ten sposób możesz dodać indeks przestrzenny GiST do swojej bazy danych, aby przyspieszyć.

Mam taką tabelę (z 350 tys. Wierszy) o konfiguracji znacznie mniejszej niż twoja (2 rdzenie i zaledwie 2 GB pamięci RAM), ale wyszukiwanie zajmuje mniej niż sekundę.

Być może mógłbyś przełamać model relacyjny, jak Essbase z ich architekturą OLAP: Essbase Wikipedia

Chodzi mi o to, aby utworzyć jeden stół na miasto, a tym samym uzyskać ponad 1000 stołów. Nie jeden stół jak sugerowałeś, ale wiele. Indeksuj każdą tabelę według daty i lokalizacji. Wiele tabel, wiele indeksów -> szybciej.

Jeśli chodzi o pomysł znalezienia usługi w chmurze do obsługi bazy danych, czy natrafiłeś już na SimpleGeo ? Po prostu przecięli wstęgę w usłudze pamięci masowej, która najwyraźniej „została specjalnie dostosowana do przechowywania i wyszukiwania danych o lokalizacji naprawdę, naprawdę szybko” - chociaż koszt przechowywania i zapytania w odniesieniu do ponad miliarda wierszy może uniemożliwić takie podejście.

spodziewasz się, że rower przejedzie po autostradzie. obecnie szukasz rozwiązania tylko dla rozwiązania tego problemu, nie przewidujesz problemu, co jeśli masz 2 miliardy rekordów? należy zająć się skalowalnością. odpowiedzią są proste, obiektowe bazy danych. np. pamięć podręczna Intersystems

i uwierzcie mi, że nie jestem z systemów wewnętrznych ;-)