Przetwarzanie dużych danych i programowanie na klastrach

obowiązkowe

Zaprezentujemy techniki i narzędzia przetwarzania dużych zbiorów danych (ang. Big data) przy pomocy klastrów złożonych z prostych maszyn. Najważniejsze omawiane narzędzia to Hadoop i Spark. Przedstawimy architekturę tych systemów oraz stosowane modele programistyczne MapReduce i Resilient Distributed Dataset. Omówimy najważniejsze techniki algorytmiczne oraz metody analizy i porównywania algorytmów. Zwrócimy uwagę na typowe problemy (np. synchronizacja zegarów maszynowych) i wąskie gardła (np. ograniczenia pamięciowe fazy redukcji w modelu MapReduce) oraz pokażemy najważniejsze metody radzenia sobie z nimi. Przedmiot będzie łączył zagadnienia praktyczne z wybranymi wynikami teoretycznymi.

1. Hadoop Distributed File System (HDFS)

2. Model MapReduce

3. Podstawowe techniki algorytmiczne dla modelu MapReduce i metody analizy algorytmów na przykładzie typowych problemów (mnożenie macierzy i wielozłączenia; algorytmy minimalne: sortowanie, ranking i idealny podział; zliczanie trójkątów w dużych grafach)

- koszt obliczenia vs koszt komunikacji

- całkowity vs mijający koszt komunikacji (ang. total vs elapsed communication cost)

- metody ograniczania pamięci reducera

- metody radzenia sobie ze skew

4. Metody efektywnej i uniwersalnej serializacji danych (na przykładzie systemu Avro)

5. Chmury obliczeniowe Amazon, Google, Microsoft, IBM

6. Rozproszone przetwarzanie dużych grafów (model BSP i Pregel)

7. Przykłady najważniejszych problemów na dużych grafach, np. PageRank i community detection

8. Spark i model Resilient Distributed Dataset

9. Kolumnowy format danych (na przykładzie Parquet)

10. Spark SQL i optymalizator Catalyst"

wymaganiami określonymi dla poziomu B2+ Europejskiego Systemu Opisu Kształcenia Językowego, w szczególności: identyfikuje główne i poboczne tematy wykładów, pogadanek, debat akademickich, dyskusji, czyta ze zrozumieniem i krytycznie analizuje teksty akademickie, zabiera głos w dyskusji lub debacie naukowej, streszcza ustnie informacje, wyniki badań, opinie i argumenty autora zawarte w tekście naukowym [K_U14].

4. Potrafi dokonać analizę złożoności algorytmu rozproszonego, porównać takie algorytmy oraz dobrać właściwy w zależności od problemu.

5. Potrafi wyrażać problemy w modelach obliczeń rozproszonych takich jak MapReduce.

6. Potrafi diagnozować wąskie gardła w algorytmach rozproszonych.

7. Posługuje się technologiami Hadoop i Spark.

8. Potrafi serializować/deserializować dane w przy pomocy frameworków sekwencyjnych i kolumnowych jak Avro i Parquet (KU_08)6. Potrafi skonfigurować klaster obliczeniowy przy pomocy frameworków Hadoop i Spark.

9. Potrafi uruchamiać programy na chmurze obliczeniowej.

10. Potrafi posługiwać się przewodnikami dla programistów dotyczącymi technologii rozproszonych.

Kompetencje

1. Zna najważniejsze biblioteki z algorytmami do przetwarzanie dużych danych, np. Spark GraphX, Spark MLlib, Apache Mahout

2. Potrafi odnajdywać informacje o przyczynach problemów i błędów na internetowych serwisach jak Stack Overflow

- Data-Intensive Text Processing with MapReduce, Jimmy Lin and Chris Dyer. Morgan & Claypool Publishers, 2010

- Mining of Massive Datasets. Anand Rajaraman, WalmartLabs, Jeffrey David Ullman, Stanford University, California

- Hadoop: The Definitive Guide, 4th Edition, Storage and Analysis at Internet Scale, Tom White, O'Reilly Media, 2015

Wiedza:

1. Zna techniki synchronizacji procesów i komunikacji międzyprocesowej w scentralizowanym i rozproszonym modelu programu współbieżnego [K_W04].

2. Zna algorytmy wzajemnego wykluczania i uzgadniania w systemach rozproszonych [K_W05].

3. Potrafi wyrazić w modelu MapReduce podstawowe operacje na danych takie jak operacje algebry relacji czy mnożenia macierzy przez wektor.

4. Ma wiedzę na temat analizy złożoności algorytmów rozproszonych i algorytmów przetwarzających duże dane.

5. Ma wiedzę na temat podstawowych technik algorytmicznych związanych z algorytmami rozproszonymi takich jak algorytmy minimalne.

6. Ma wiedzę na temat ogólnodostępnych chmur obliczeniowych.

7. Ma wiedzę na temat przenośnych metod serializacji danych.

Umiejętności

1. potrafi zastosować mechanizmy synchronizacji procesów i wątków w wybranych technologiach w zależności od architektury i możliwości konkretnego komputera [K_U06].

2. posługuje się nowoczesnymi technologiami rozpraszania i zrównoleglania obliczeń [K_U08].

3. ma umiejętności językowe w zakresie informatyki zgodne z wymaganiami określonymi dla poziomu B2+ Europejskiego Systemu Opisu Kształcenia Językowego, w szczególności: identyfikuje główne i poboczne tematy wykładów, pogadanek, debat akademickich, dyskusji, czyta ze zrozumieniem i krytycznie analizuje teksty akademickie, zabiera głos w dyskusji lub debacie naukowej, streszcza ustnie informacje, wyniki badań, opinie i argumenty autora zawarte w tekście naukowym [K_U14].

4. Potrafi dokonać analizę złożoności algorytmu rozproszonego, porównać takie algorytmy oraz dobrać właściwy w zależności od problemu.

5. Potrafi wyrażać problemy w modelach obliczeń rozproszonych takich jak MapReduce.

6. Potrafi diagnozować wąskie gardła w algorytmach rozproszonych.

7. Posługuje się technologiami Hadoop i Spark.

8. Potrafi serializować/deserializować dane w przy pomocy frameworków sekwencyjnych i kolumnowych jak Avro i Parquet (KU_08)6. Potrafi skonfigurować klaster obliczeniowy przy pomocy frameworków Hadoop i Spark.

9. Potrafi uruchamiać programy na chmurze obliczeniowej.

10. Potrafi posługiwać się przewodnikami dla programistów dotyczącymi technologii rozproszonych.

Kompetencje

1. Zna najważniejsze biblioteki z algorytmami do przetwarzanie dużych danych, np. Spark GraphX, Spark MLlib, Apache Mahout

2. Potrafi odnajdywać informacje o przyczynach problemów i błędów na internetowych serwisach jak Stack Overflow

Laboratorium zaliczane jest na podstawie dużych zadań programistycznych oraz punktów za prace na zajęciach. Do egzaminu w pierwszym terminie dopuszczone są osoby, które otrzymały przynajmniej połowę punktów z programistycznych zadań zaliczeniowych. Duże zadania programistyczne oddawane po terminie będą karane obcięciem części punktów lub, w przypadku dużego spóźnienia, pozostawiane bez oceny. Ocena z pierwszego terminu wystawiana jest za punkty z labu i egzaminu w sumie. Ocena z drugiego terminu wystawiana jest tylko za punkty z egzaminu.

Dla doktorantów dodatkowym warunkiem zaliczenia jest przeczytanie i zreferowanie świeżej pracy naukowej z tematyki przedmiotu (wybór pracy należy uzgodnić z prowadzącym przedmiot).