-
Notifications
You must be signed in to change notification settings - Fork 0
Home
Ponieważ, celem zabezpieczenia prywatności, aplikacja mobilna nigdy nie zapamiętuje współrzędnych położenia, to obowiązkiem algorytmów po stronie serwera jest odtworzenie tego, gdzie w danej chwili znajdowało się urządzenie pomiarowe. Aby to osiągnąć niezbędne jest posiadanie bazy przystanków (w tej samej wersji co klient), tras po których przemieszczają się pojazdy komunikacji miejskiej, oraz wszystkich rozkładów jazdy.
Dane, generowane i przesyłane do wspólnego repozytorium przez użytkowników aplikacji mobilnej, nie zawsze są wiarygodne. Weźmiemy pod uwagę dwa przypadki: złośliwie sfałszowane w celu zaburzenia poprawności obliczeń, oraz nieprawidłowe funkcjonowanie lub użytkowanie aplikacji.
Każdy pomiar jest obarczony pewnym błędem. Możemy jednak założyć, że w pewnych przypadkach znajdziemy się w posiadaniu wielu, niezależnych pomiarów tego samego kursu. Ich wartość średnia będzie obarczona mniejszym błędem, niż każdy z tych pomiarów.
Preferowaną przez nas metodą na rozwiązanie w/w problemów jest wykonanie obliczeń dopiero wtedy, gdy w systemie będą obecne wszystkie dane wygenerowane w danym dniu (zakładamy pewien czas, przez który dane od użytkowników “spływają” na serwer). Mając na uwadze skalowalność, zakładamy, że ilość danych do przetworzenia każdego dnia, będzie znacząca. Ponieważ całość obliczeń dzieli się na 3 większe, ale zależne od siebie algorytmy, to każdy z nich można zrównoleglić, lecz wszystkich razem już nie.
Naszą ramą projektową (frameworkiem) będzie MapReduce, model programowania do przetwarzania i generowania znacznych ilości danych. Naszym zadaniem jest napisanie jedynie funkcji mapujących, przetwarzających pary klucz-wartość, w celu wygenerowania pośrednich par klucz-wartość oraz ewentualnie funkcji redukujących, które scalą wszystkie pośrednie wartości, posiadające ten sam klucz. Działanie tych funkcji jest podobne do działania metod o tych samych nazwach, popularnych w językach funkcyjnych, takich jak Erlang czy OCaml. Ponieważ algorytm odpowiada za takie zagadnienia jak zrównoleglenie, komunikację pomiędzy wieloma maszynami czy obsługę błędów, my nie musimy już pisać żadnego dodatkowego kodu, który nie jest bezpośrednio odpowiedzialny za rozwiązanie naszego problemu.
Ponieważ standardowy serwer web’owy składa się z tylko jednego fizycznego procesora, co dla naszych obliczeń nie jest wystarczające, postanowiliśmy skorzystać z chmury amazon’a (Amazon Web Services), a konkretnie z web serwisu Amazon Elastic MapReduce. Jest to usługa, dzięki której będziemy mogli w szybki i prosty sposób, poprzez np. interface www lub konsoli, uruchamiać i śledzić nasze funkcje mapujące i redukujące, płacąc jedynie za czas, przez który nasze maszyny wirtualne używały mocy obliczeniowej (do dyspozycji mamy od jednej do dwudziestu jednostek 1 w klastrze). Usługa jest oparta o otwartą implementację algorytmu MapReduce – Apache Hadoop działającą na Amazon Elastic Compute Cloud. Dane wejścia i wyjścia są przechowywane na Amazon Simple Storage Service.
W praktyce możliwe jest uruchomienie identycznego środowiska na dowolnej maszynie lub ich zbiorze, po wcześniejszej instalacji framerorku Apache Hadoop lub np. Cloudera’s Distribution for Hadoop, który jest łatwym w instalacji pakietem RPM, opartym o ten sam, otwarty framework. Do celów testowych najlepiej nadaje się już skonfigurowana maszyna wirtualna VMWare (Cloudera’s Distribution for Hadoop: VM), którą uruchomimy pod dowolnym systemem operacyjnym.
1 z technicznego punktu widzenia jest to maszyna wirtualna działająca na serwerze o wybranych przez nas parametrach. Standardowa konfiguracja (Small Instance) to 1.7 GB pamięci i 1 jednostka EC2 (32-bit). Jedna jednostka EC2 odpowiada procesorowi 1.0-1.2 GHz 2007 Opteron. Dostępne są także bardziej wydajne jednostki do aż 68.4 GB pamięci i 26 jednostek EC2 (64-bit), która odpowiada 8 rdzeniowemu procesorowi o częstotliwości taktowania 4GHz.
Źródło: http://aws.amazon.com/ec2/instance-types/
W wyniku działania programu otrzymujemy informacje o:
- prędkości chwilowej (lub średniej) pojazdu w dowolnym momencie (lub odcinku) trasy,
- wrażliwych (zwalniających) punktach na mapie (globalnie, dla każdej linii),
- faktycznym czasie przejazdów linii X od przystanku A do B (innymi słowy o opóźnieniach w stosunku do rozkładów jazdy),
- długości oczekiwania pasażerów na przystankach,
- trendach w przemieszczaniu się po mieście (zakładając posiadanie dużej i reprezentatywnej ilości danych wejściowych).
MapReduce
- http://labs.google.com/papers/mapreduce-osdi04.pdf
- http://code.google.com/edu/submissions/mapreduce-minilecture/listing.html
- http://code.google.com/edu/submissions/mapreduce/listing.html
- http://sites.google.com/site/mriap2008/
Hadoop