Skanowanie miliarda wierszy w ultraszybkiej bazie danych

9

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!

architecture database geospatial Dave Jarvis
źródło
10
„przełączanie baz danych nie jest opcją”, co praktycznie eliminuje większość rozwiązań. powodzenia!
Steven A. Lowe,
1
Trudno powiedzieć bez dodatkowych informacji o tym, co dokładnie robisz z tymi rekordami. Czy szukasz też najgorszego przypadku na 5 sekund (co prawdopodobnie oznacza, że ​​każdy badany rekord i zero lokalizacji pasują do siebie)?
Guy Sirton,
2
@Dave: Ile czasu zajmuje obecny system? Czy obecny system korzysta z PostGIS ? Czy location_ida geographylub geometryodnosi się do drugiej tabeli? Czy location_idkolumna jest indeksowana?
rwong
1
@ Thorbjørn & @Darknight - W sekcji pomysłów wymieniam wstępne obliczenia, które zmniejszyłyby dane do jednej wartości na miasto dziennie (według kategorii). Obliczenia mogą się powtarzać co roku, a nawet co miesiąc. To był mój plan, gdyby nie było innych możliwości (obliczenia prawdopodobnie potrwają tygodnie).
Dave Jarvis,
1
@Dave, wiele możliwości, ale pytanie dotyczy tego, co jest dla Ciebie ważne. Czy sprawdziłeś już, gdzie są obecne wąskie gardła?

Odpowiedzi:

12

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.


źródło
Jakkolwiek go kroisz i kroisz w kostkę - nawet jeśli każdy wiersz zajmuje tylko 100 bajtów, 1,3 miliarda wierszy = 121 GB. Przy wszystkich indeksach itp. Jestem pewien, że będzie to znacznie więcej. Na pojedynczym pudełku będziesz wolny, chyba że masz jakiś poważny sprzęt wokół SSD + Tony pamięci RAM. Tańszym sposobem jest skalowanie między polami.
Subu Sankara Subramanian
4
@Subu, chcesz przejść do dystrybucji? Teraz masz dwa problemy ...
Heh - z czym się zgadzam :) Ale jest taniej!
Subu Sankara Subramanian
@ Thorbjørn: Dziękujemy za poświęcony czas i całą pomoc. Myślę, że zmniejszy zestaw danych do 25 milionów wierszy na kategorię, a następnie zastosuję indeksy na ten dzień. To powinno zmniejszyć skanowanie do ~ 70000 wierszy (dziennie, z limitem dwóch tygodni dla zakresu), co powinno być dość szybkie.
Dave Jarvis,
@Dave, nadal musisz wiedzieć, gdzie są twoje wąskie gardła. Naucz się tego, kiedy nie musisz .
4

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

Subu Sankara Subramanian
źródło
Dziękuję za pomysły. Istnieje potencjalnie 77 066 dat, a nowe daty będą dodawane w przyszłości. Mam jedną maszynę. Istnieje 20 000 lokalizacji, ale podział według lokalizacji nie pomógłby, ponieważ analizowane dane obejmują wszystkie lokalizacje.
Dave Jarvis,
i czym różni się korzystanie z chmury od powyższego rozwiązania?
Chani,
O tym też myślałem. Jakiś rodzaj partycji poziomej, aby wyszukiwanie mogło odbywać się równolegle we wszystkich partycjach.
davidk01
Podział w ciągu dnia byłby prawdopodobnie najbardziej pomocny, w wyniku czego powstałyby 2562 osobne tabele (366 dni x 7 kategorii).
Dave Jarvis
4

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ą.

Guy Sirton
źródło
Dziękuję za Twoją odpowiedź. Rozważane są aktualizacje sprzętu, zgodnie z wymienionymi pomysłami. Idealne byłoby rozwiązanie o wartości poniżej 750 USD.
Dave Jarvis,
2

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?

Denis de Bernardy
źródło
Dziękuję Ci. Siedem tabel potomnych jest grupowanych według lokalizacji, daty i kategorii za pomocą btree. W zeszłym roku badałem indeksy GIN, które, jak pamiętam, nie pomagały (lub nie pomagały).
Dave Jarvis,
2
Indeksowanie lokalizacji na podstawie B-Tree nie jest w najmniejszym stopniu przydatne, biorąc pod uwagę rodzaj wyszukiwań, w których szukasz. Potrzebujesz odwróconego indeksu, który działa z potrzebnymi operatorami, co w przypadku Postgis zwykle oznacza GIST. Możesz zwrócić uwagę na kilka powolnych zapytań ...
Denis de Bernardy,
1

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ę.

dzikie piki
źródło
0

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.

Mihaela
źródło
Dziękuję za notatkę. Istnieje ponad 70 000 miast, a wiele różnych wartości szerokości i długości geograficznej przypada na określony obszar miasta.
Dave Jarvis,
@Dave: czy możesz zbudować diagram voronoi dla miast i sklasyfikować wartości lat / lon w teselacjach? (tzn. jeśli zabrzmi to przypadkowo, niech tak będzie). Następnie podczas wyszukiwania będziesz szukać wszystkich miast, których teselacja dotyka zakresów długości / długości zapytania. Jeśli teselacja voronoi jest zbyt wolna, warto wypróbować kwadratowe pudełka (np. 5 stopni x 5 stopni).
rwong
0

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.

IanI
źródło
-2

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

anerjan
źródło