powrót

Zadanie 3 (Map-Reduce)


To zadanie zostało wykonane w dwuosobowym zespole o składzie Łukasz Mielewczyk oraz Marek Białousz.
Do rozwiązania zadania została wykorzystana baza danych mongoDB.
Każdy z nas pracował na swoich kompterach, a na końcu porównywaliśmy wyniki.

Informacje o danych

Dane zawierają informacje o transakcjach. Pobierz.

Kolumny:


Rozmiar: 230 MB
Ilość: 1000001


Instalacja i konfiguracja oprogramowania

mongoDB

Do rozwiązania zadania użyto bazy mongoDB. Należy ją pobrać ze strony i zainstalować. Następnie aby uruchomić bazę danych, należy w konsoli cmd i wydać polecenie:

mongod


Map-Reduce

Map-Reduce to najbardziej zaawansowany mechanizm przetwarzania zawartości bazy danych, ale jednocześnie najwolniejszy. Na proces Map-Reduce składa się kilka etapów.
Na etapie mapowania (ang. map) funkcja użytkownika wywoływana dla każdego dokumentu emituje dowolną liczbę (0 lub więcej) par klucz-wartość. W efekcie otrzymujemy olbrzymią ilość par klucz-wartość, przy czym klucz często powtarza się w wielu parach.
Na etapie tasowania (ang. shuffle) pary o tym samym kluczu są agregowane w parę klucz-tablica_wartości.
Funkcja redukcji (ang. reduce) napisana przez użytkownika pobiera na wejściu parametry klucz, tablica_wartości i redukuje tablicę do jednego elementu. Funkcja reduce musi mieć taką własność, że jej wynik może być użyty jako element tablicy przekazanej jako drugi argument do kolejnego wywołania reduce.

schemat Map-Reduce

Schemat wywołania procesu Map-Reduce:
{
  "result": "result", //miejsce w którym został zapisany wynik obliczeń umieszczony
  "timeMillis": 1, //czas obliczeń w milisekundach
  "counts": {
    "input": 1000001, //ilość danych
    "emit": 0, //ilość wygenerowanych par klucz-wartość
    "reduce": 0, //ilość odpowiedzi na główny problem
    "output": 0 //ilość elementów kolekcji wynikowej
  },
  "ok": 1
}

mongoDB

import danych

Następnie aby zaimportować z pliku do bazy danych (oczywiście baza danych musi być uruchomiona) należy wydać w cmd polecenie:

mongoimport --db test --collection test --file trades.json
Import powinien powodować duże zużycie zasobów (ilustracja niżej):

Procesor podczas importu danych do mongoDB


Pamięć podczas importu danych do mongoDB


Dysk podczas importu danych do mongoDB


Wykonanie trwało ok. 2 minut.
Wyniki były podobne na komputerach Łukasza i Marka.
Ostatecznie powinien pojawić się komunikat: "imported 1000001 documents"


przykładowy rekord

Przed wykonaniem czynności upewnij się czy dane zostały zaimportowane. Jeśli nie: przeczytaj jak to zrobić.

Aby zobaczyć przykładowy rekord przy pomocy Map-Reduce, należy:
Strzworzyć poniższą funcję map:
var mapFun = function() {
  emit(null, this);
};
Strzworzyć poniższą funcję reduce:
var reduceFun = function(key, emits) {
  return emits[0];
};
Wywołać proces Map-Reduce:
mr = db.test.mapReduce(
  mapFun,
  reduceFun,
  { out: "exampleRecord" }
)
Proces Map-Reduce - przykładowy rekord
Aby zobaczyć wynik należy wykonać polecenie:
db[mr.result].find();
Wynik wykonania Map-Reduce - przykładowy rekord

Map-Reduce nie jest najlepszym narzędziem do wyświetlania przykładowego rekordu.


ilość kluczy

Przed wykonaniem czynności upewnij się czy dane zostały zaimportowane. Jeśli nie: przeczytaj jak to zrobić.

Aby poznać listę oraz ilość kluczy, należy:
Strzworzyć poniższą funcję map:

var mapFun = function() {
  for( var key in this ) {
    emit( key, { count: 1 });
  }
};
Strzworzyć poniższą funcję reduce:
var reduceFun = function(key, emits) {
  total = 0;
  for( var i in emits ) {
    total += emits[i].count;
  }
  return { "count": total };
};
Wywołać proces Map-Reduce:
mr = db.test.mapReduce(
  mapFun,
  reduceFun,
  { out: "quantityKeys" }
)
Proces Map-Reduce - ilość kluczy
Aby zobaczyć wynik należy wykonać polecenie:
db[mr.result].find();
Wynik wykonania Map-Reduce - ilość kluczy

Można zaobserwować, że ilość danych wynosi 1000001 (klucz _id) oraz wszystkie elementy zawierają wszystkie klucze.

suma cen jednego biletu

Przed wykonaniem czynności upewnij się czy dane zostały zaimportowane. Jeśli nie: przeczytaj jak to zrobić.

Aby poznać sumę cen biletu z385, należy:
Strzworzyć poniższą funcję map:

var mapFun = function() {
  emit(this.ticket, this.price);
};
Strzworzyć poniższą funcję reduce:
var reduceFun = function(key, emits) {
  return Array.sum(emits);
};
Wywołać proces Map-Reduce:
mr = db.test.mapReduce(
  mapFun,
  reduceFun,
  {
    query: { ticket: "z385" },
    out: "sumPrices"
  }
)
Proces Map-Reduce - suma cen jednego biletu
db[mr.result].find();
Wynik wykonania Map-Reduce - suma cen jednego biletu

średnia ilość biletów

Przed wykonaniem czynności upewnij się czy dane zostały zaimportowane. Jeśli nie: przeczytaj jak to zrobić.

Aby poznać średnią ilość biletów wydaną przez abcd, należy:
Strzworzyć poniższą funcję map:

var mapFun = function() {
  emit(this.ticker, this.shares);
};
Strzworzyć poniższą funcję reduce:
var reduceFun = function(key, emits) {
  return Array.sum(emits)/emits.length;
};
Wywołać proces Map-Reduce:
mr = db.test.mapReduce(
  mapFun,
  reduceFun,
  {
    query: { ticker: "abcd" },
    out: "averageQuantity"
  }
)
Proces Map-Reduce - średnia ilość biletów
db[mr.result].find();
Wynik wykonania Map-Reduce - średnia ilość biletów

Pomimo podobnego zastosowanie Map-Reduce jak suma cen jednego biletu, czas jest dużo gorszy.
Powodem najpradopodobniej jest większa ilość wystąpienia abcd niż biletu z385

średnia cen sprzedaży

Przed wykonaniem czynności upewnij się czy dane zostały zaimportowane. Jeśli nie: przeczytaj jak to zrobić.

Aby poznać sumę cen biletu z385, należy:
Strzworzyć poniższą funcję map:

var mapFun = function() {
  emit(this.ticket, { count: this.shares, price: this.price });
};
Strzworzyć poniższą funcję reduce:
var reduceFun = function(key, emits) {
  reducedVal = { count: 0, price: 0 };
  for (var i = 0; i < emits.length; i++) {
    reducedVal.count += emits[i].count;
    reducedVal.price += emits[i].price;
  }
  return reducedVal;
};
Strzworzyć poniższą funcję finalize - taka funckja zostanie wykonana po wyponaniu Map-Reduce:
var finalizeFun = function (key, reducedVal) {
  reducedVal.avg = reducedVal.price/reducedVal.count;
  return reducedVal;
};
Wywołać proces Map-Reduce:
mr = db.test.mapReduce(
  mapFun,
  reduceFun,
  {
    out: "averagePrices",
    finalize: finalizeFun
  }
)
Proces Map-Reduce - średnia cen sprzedaży
db[mr.result].find();
Wynik wykonania Map-Reduce - średnia cen sprzedaży

Wnioski

pomiar

Pomiar został wykonany podczasz wywołania procesu Map-Reduce.
Tabela przedstawia podsumowanie pomiaru.

Map-Reduce Ł. Mielewczyk M. Białousz
Przykładowy rekord 15616 ms 16011 ms
Ilość kluczy 56238 ms 57885 ms
Suma cen jednego biletu 1382 ms 1496 ms
Średnia ilość biletów 14377 ms 16355 ms
Średnia cen sprzedaży 19599 ms 21013 ms

Porównanie egzekucji zapytań na obu komputerach.

Egzekucja zapytań na obu komputerach (w ms).

Widać, że dla każdego zapytania Łukasz otrzymuje zawsze minimalnie szybciej wynik.

informacje o komputerach

Każdy z nas pracował na komputerze o parametrach przedstawionych w poniższej tabeli.

Nazwa Wartosć
Ł. Mielewczyk M. Białousz
Procesor Core(TM) i3-4005U CPU 1,7 GHz 1,7 GHz Intel Core i7-4510U 2.0 GHz
RAM 12 GB 8,0 GB
Dysk HDD Toshiba MQ01ABD025 1TB
System operacyjny Windows 10 64-bit Windows 8.1 x64
Wersje mongoDB mongoDB 3.2.6 mongoDB 3.2.6

podsumowanie

Każdy z pomiarów na komputerze Łukasza są minimalnie lepsze niż u Marka. Prawdopodobne przyczyny takie zachowania: Mimo różnicy w posiadanej pamięci RAM oba komputery zużywały maksimum dostępnej pamięci podczas importu, agregacji i pozostałych badań.
Zasoby żużycia - Ł. Mielewczyk
Zasoby żużycia - M. Białousz

Okazuje się, że pojemność pamięci RAM ma kluczowy wpływ na oceny uzystkiwane w teście RAM i bez względu na szybkość transmisji determinuje maksymalny możliwy rezultat.
Komputer oferujący wyższą wydajność oraz większy komfort pracy z otwartymi kilkoma aplikacjami równocześnie, oraz komputer dla gracza, powinien dysponować minimum 8 GB RAM.
Pamięć RAM jaką posiada komputer Marka jest zatem wymaganym minimum potrzebnym do tych badań, jednak przy pamięci Łukasza, różnica jest zauważalna (tylko przy sprawdzeniu czasu zapytania, gdyż czynności niekiedy trwają kilka sekund).

powrót