Hajussüsteemid 2023

Ainekoodid: ITI0215 Aine nimed: Hajussüsteemid Link: http://lambda.ee/wiki/Hajuss%C3%BCsteemid Punkte: 6 EAP Õppejõud: Tanel Tammet, Radu Irbe Kontakt: tanel.tammet@ttu.ee Olemas on ka 2022 aasta materjalide arhiiv.

Eksamitulemused

Esimene eksam (31 mai):

Eesnime esitäht, tudengikood, eksamil punkte (0-50), kokku punkte (0-100), hinne:
K	221339	34 83 4
T	221266	23 72 3
M	221613	23 72 3
K	221657	33 88 4
R	221523					
K	211598	42 90 5

Teine eksam (5 juuni):

Eesnime esitäht, tudengikood, eksamil punkte (0-50), kokku punkte (0-100), hinne:
R       221523  50 100 5

Eksamiajad ja -kohad

• 31 mai kolmap kell 13-16, ruumis SOC-414 (sotsiaalteaduste maja)
• 5 juuni esmasp kell 11-14, ruumis U04-103 (IV korpus, pikast koridorist)
• 8 juuni neljap kell 12:15-15, ruumis SOC-414 (sotsiaalteaduste maja)

Eksamiks on kokku aega 2.5 tundi, aga enamik peaks saama hakkama ca 1.5 tunniga.

Eksam on kirjalik, samas ruumis/ajal toimub ka teadmiste formaliseerimise kirjalik eksam.

Teemad, mille kohta küsimused eksamil tulevad:

• Protokollid XML-RPC, Rest, SOAP baasosad
• P2P süsteemid, sh klassikalised ning Chord, Bittorrent ja TOR
• Distributed ledger ja Bitcoin
• Konsensus, lukustamine, transaktsioonid
• Fork, thread, shared memory
• Andmebaaside hajutamine ja koondamine: eesmärgid ja põhimeetodid
• Riigi infosüsteem ja Xtee

Sul on vaja nende teemade põhimõtteid/protokolle/algoritme selgitada ja mõnel puhul tuua ise väikeseid näiteid.

Eksamil esitatakse küsimusi viie teema kohta, ja teil tuleb neist valida neli, mida vastata. Kui on vastatud viis, siis õppejõud hindab neist teemadest ikakgi nelja (valides parimate tulemustega neli), mitte ei summeeri kõiki viit.

Aeg, koht

Semester: kevad
Tulemus: eksam
Hindamise meetod: praktikumide tulemused (50%) ja eksam (50%)

Loeng: kolmapäeval 12:00-13:30 ruumis ICT-315
Praktikum: kolmapäeval kell 13:45-15:15 ruumis ICT-315

Kursuse teamsi link

Plaan on teha enamik loenguid kohapeal ja väiksem osa distantsilt. Praksid toimuvad vähemalt esialgu kohapeal, ja võimalik, et osad hiljem distantsilt. Loengute ja prakside salvestused leiad altpoolt vastava loengu/praksi peatüki alt.

Kogu info, materjalid ja ülesanded on lambda lehel.

NB! Allpool olev blokkide struktuur on sarnane, kui 2022 aastal, aga mitte päris sama. Mh on lisandunud stream processingu / Kafka ja andmeladude osa. Toimunud loengute materjalid ja salvestused osaliselt uuendatakse/muudetakse: kogu info veel mitte toimunud loengute ja veel mitte selgitatud/uuendatud prakside kohta on esialgne.

Hindamine

Kursuse edukaks sooritamiseks on sul vaja:

• saada arvestatud mõlemid praktikumid
• teha eksam tasemel vähemalt 1/3 eksami kogupunktidest.
• saada praktikumid + eksam kokku vähemalt 50 punkti.

Kursuse hinde rehkendamisel annavad praktikumid kokku 50% kogupunktidest ning eksam 50%.

Nädala ülesanded

Mõnel nädalal antakse väike kohustuslik ülesanne: õppejõule tuleb kas saata emailiga kokkuvõte/mikroessee.

Praktikumid

Kokku on praktikumitöid 2. Kumbki praktikum täismahus tehtuna annab 20 punkti, sellele võivad lisanduda ekstrapunktid. Puudulikult tehtud töö punktiarv jääb alla 20 punkti. Hilinenud kodutöö eest saab pooled muidu saadaolevad punktid.

• 1 praks on P2P rakendus: distributed ledgeri komponent või anonümiseeriv võrk. Grupitöö 1-3 inimest.

• 2 praks 2023

Praktikumitööde tähtajad on:

• 1. praktikumil - 22. märts 2023,
• 2. praktikumil - 10. mai 2023.

Praktikumitöö esitamiseks tee järgmist:

• Pane oma töö TTÜ gitlabi või avalikku githubi või gitlabi reposse.
• Pane repo esilehele loetav ülevaade protokollidest, mida su töö kasutab, koos töö üldpõhimõtete kirjeldusega.
• Tee nii, et Radu saaks seda repot lugeda: kui ei ole avalik repo, lisa ta developeriks. TTU Gitlabis peab olema developer õigustes, et koodi lugeda.

Praktikumijuhendaja on Radu. Tanel ja Martin assisteerivad ja vajadusel tulevad appi.

Loengukava

Kursus jaguneb laias laastus neljaks teemaks:

• P2P ja protokollid (neil teemadel - pluss veidi andme-apidest- esimene praks), sh distributed ledger ehk bitcoini alustehnoloogia
• Andme-apid ja messaging/stream processing
• Paralleelrehkendused ja konsensus, lukustamine, sünkroniseerimine
• Hajutatud andmebaasid, andmelaod ja X-tee ja riigi IT-korraldus

Päris hea õpiku saad tasuta alla laadida siit. Meie kursuse sisu on sellest õpikust küllalt erinev, samas on ka ühisosi. Hea mõte on lugeda soenduseks läbi jutt hajussüsteemide probleemide ühest valdkonnast (aga neid on veel hulga).

Üldist materjali ja kursusi mujalt:

http://en.wikipedia.org/wiki/Distributed_computing

http://dcg.ethz.ch/lectures/podc_allstars/index.html

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-824-distributed-computer-systems-engineering-spring-2006/index.htm

http://www.stanford.edu/class/cs244b/

Protokollid ja P2P

P2P sissejuhatus, 1. veebruar

loengu ja praksi salvestus teamsis

Kohustuslikud osad lugeda:

loengumaterjal: pikem ülevaade eri P2P tehnoloogiatest

vikipeedia ülevaade

TOR wikipedias

Protokollid: 8 veebruar

Loengusalvestus 2023

Kohustuslikud osad lugeda:

Http ja json: võrgurakenduste protokollid 1

Täiendavalt soovitav lugeda:

Gaffer on games: UDP vs TCP

Veidi seotud asi ad hoc networks vt ka Defendeci ja Jürgo Predeni patent

Http ja json: võrgurakenduste protokollid 1 lõpuosa alates https

Loe lisaks https kohta

Andmekodeerimine/vahetus: http eriteemad + JSON, XML-RPC, SOAP ja sõbrad: 15 veebruar

Loengusalvestus 2023.

võrgurakenduste protokollid 1 eriosad: Same origin policy, push/longpoll ja websockets

xml protokollid xml-rpc, soap ja seotud tehnoloogiad: võrgurakenduste protokollid 2

Vanad tekstid SOAPi probleemidest: veebiteenuste võlu ja valu ja s stands for simple

Data synchronization, DHT-s, start distributed ledger: 22 veebruar

Teamsi loengusalvestus

Sissejuhatus teemasse: andmete sünkroniseerimine.

DHT (distributed hash tables):

• ülevaade wikipedias
• Chord:

Põhimaterjal: Chordi põhimõtted. Täiendavalt võib vaadata seda presentatsiooni visualiseeritud algoritmidega (ppt presentatsioonirezhiimis!) ja eriti detailideks seda presentatsiooni (seda varianti kasutame ka loengus!).

Lisaks tasuks veidi uurida artikleid wikipedia sissekande lõpus (external links)

• Kademlia:

Materjal presentatsioon autoritelt

Täiendavalt autorite artikkel ja eriti hea detailsem presentatsioon

• IPFS

Plokiahel:

• Alustame Kriitiline taust blockchaini mõistmiseks teemadesse. Palun süvene neisse materjalidesse lisaks loengus räägitule.
• detailsem plokiahela ülevaade

Distributed ledger: 1 märts

Loengusalvestus teamsis 2023

Blockchaini funktsioneerimine:

• Jätkame eelmise loengu lõpu materjalidega.

• Kindlasti süvene blockchaini põhimõtete demosse: vajuta üleval "Hash", "Block", "Blockchain" linkidele ja proovi igal lehel ise datat muuta ja "Mine" nupule vajutada. "Mine" teeb proof-of-worki ehk otsib random stringi (nonce) mille lisamisel datale saame mitme nulliga algava hashi. Hea mõte on vaadata ka sama saidi videosid

• Dirk Draheimi materjal samal teemal: mitmete komponentide väga head illustratsioonid

Huvi pärast vaata ka Guardtime AlphaBill projekti: üliskaleeritav plokiahela-süsteem.

Blockchain ja krüptorahad: 8 märts

Teamsi loengusalvestus.

Jätkame blockchaini ja krüptorahadega. Eriti abiks oleks tudengite tähelepanekud ja küsimused.

Mh vaatame hulka Blockchaini materjale.

Keerulisemat soovitavat materjali konsensuseteemal:

• From blockchain consensus back to Byzantine consensus
• A Survey on Blockchain Consensus witha Performance Comparison of PoW, PoS and Pure PoS

Blockchaini ja krüptorahade jätk: 15 märts

Teamsi loengusalvestus

Jätkame blockchaini ja krüptorahadega. Seekord vaatame detailsemalt bitcoini datastruktuure ja teistsuguseid krüptorahasid ja sarnaseid asju.

Mh: programmid vs lihtsad ülekanded / smart contracts (ethereum, bitcoin), proof of stake vs proof of work, ja mõningaid suuremaid siit listist.

Kui jõuame, siis alustame ka API-stiilidega, mis jätkub järgmisel nädalal.

Andme-apid ja stream processing

Erinevad API-stiilid: 22 märts

Salvestused:

• 2021 salvestatud: link loenguvideole (parandatud!): endiselt adekvaatne.
• Lisaks sellele varasemale on siin uus lühike RESTi algus-sissejuhatus teamsi video, mida oleks parem vaadata ehk isegi enne 2021 aasta salvestust.
• Loengu lõpu 20 minutit arutelu salvestus

Lugemiseks:

• Päris alustuseks loe süvenemisega läbi Microsofti REST api design soovitused
• rest wikipedias ja rest tutorial (vt linke all!)
• odata.org: microsoft/oasis recommendations for rest style
• api design book (must register)
• Graphql start and graphql vs rest and similar take on rest vs graphql and wrap rest in graphql

Päris hea ülevaate leiad siit: Moesif API guide

Sul on vaja iseseisval detailsemalt tutvuda (a) REST-stiiliga ja (b) tutvuda natuke graphql päringu/vastustekeelega (need on siis kaks täiesti erinevat asja):

• tutvuda levinumate soovitustega REST-stiilis APi-de ehitamiseks:
  • Kui sa hästi ei mäleta REST-stiili põhipointe, siis sissejuhatuseks vaata üle wikipedia jutt.
    • Põhi-idee on kasutada HTTP harilikke get, put, post "käske", et öelda, kas tahad datat, lisad datat või uuendad datat, identifitseerida data-objekte urli abil stiilis http://miski.org/data/people/25 (siin on variante), anda vigade korral tagasi HTTP veakoode, kodeerida autentimisinfot ja muud metainfot HTTP päistesse ja püüda kodeerida API päringud ja vastused võimalikult kergelt arusaadavalt.
    • Pane tähele, et viisid otsingupäringu (inimesed nimega "Jaan"), vastuste arvu (ntx max 100) ja akna/batchi (ntx alga 200-ndast), sorteerimise jne indikeerimiseks ei ole RESTi-stiilis konkreetselt soovitatud, igaüks teeb kuidas tahab: ODATA allpool pakub oma soovitusi, aga need ei ole arusaadavalt kohustuslikud või "REST" stiili osad.
  • Tutvu siin peatüki alguses juba viidatud Microsofti api design soovitustega, täiendavalt võib uurida lisadetaile
  • Hea mõte on lisaks võtta alternatiivina leiad sellelt urlilt api disaini väike raamat ja sellega tutvuda.
  • Vaata odata veidi eksootilisemaid, aga autoriteetse standardiorganisatsiooni oasis soovitusi REST stiilis API ehitamiseks, konkreetselt alusta kiirsissejuhatusega, siis loe basic tutorial ja lõpuks tutvu kiirelt pika standardidoku peatükiga 5: query options
  • Väike pure-rest/odata/cgi stiilide võrdlus
• tutvuda lühidalt graphql-ga: tegu siis hoopis teistsuguse asjaga kui REST: graphql ei ole stiil, vaid täiesti konkreetne päringute/vastuste keel a la sql, mille töötas välja facebook:
  • Alusta wikipedia kiirülevaatest
  • Tähelepanek: graphql ülesseadmine oma data peale ei ole lihtne ülesanne: ilmselt ei jaksa sa ise programmeerida päringukeele parserit/otsimootorit jne. Levinud lahendused on seada üles Apollo server, ja progeda sinna juurde päringud oma andmebaasi, või seada üles graphql.js server ja teha sinna juurde päringud. Kumbki on suurem töö, kui lihtsa REST api ehitamine.
  • Loe läbi rest-vs-graphql jutt
  • Loe läbi grapqhl kiirtutorial (lehekülgede lõpus link järgmisele)

Vt ka suured avalikud andme-apid:

google api explorer

google api style guidelines

Andme-apide näiteid

facebook api limitations/shutdowns in 2018

Teise praktikumi sissejuhatus, ülejõu koormus ja skaleerimine: 29 märts

Seminari vormis loeng 2022 aastast: salvestus ja loengu hajussüsteemid: skaleerimise märkmed

Stream processing, message queues ja Apache Kafka: toimus varem

Materjalid ilmuvad hiljem.

Paralleelrehkendused ja konsensus ja reaalsed hajutatud süsteemid

Konsensus hajutatud süsteemides: 5 aprill

Teamsi loengusalvestus 2023

Siin blokis asume tegelema keerumakate teooria-teemade lugemisega: infovahetus ja konsensus hajutatud süsteemides, kus midagi võib rikki minna. Ehk, kuidas saavutada, et hajutatud süsteem funktsioneeriks ok, kui mingid osad on katki või kui mõni osa teeb meelega jama, et teisi segada? See on üks fundamentaalsemaid hajutatud süsteemide küsimusi üldse.

Bitcoini plokiahela mehhanism ongi üks konkreetne võimalik mehhanism konsenuse saavutamiseks mitte-üleni-usaldusväärses hajutatud süsteemis.

• Soenduseks loe läbi väga praktilisi hajussüsteemide probleeme kirjeldav jutt Amazonilt (siin otselink pdf-le).

• Lisaks tasub veidi vaadata kiirülevaadet konsensuseteema eri harudest (mh hea pilt) ja sarnaselt wikipedia kiirülevaadet harudest ja terminitest. Uuri kindlasti välja, mis tähendab sünkroonne/asünkroonne, partition tolerant/nontolerant, permissioned/permissionless.

• Seejärel - põhiasjana - tööta süvenemisega läbi hea presentatsioon põhjalikumaks arusaamiseks. Sinu põhiülesanne on see presentatsioon väga aeglaselt läbi töötada ja järjest slaididest ja asjadest aru saada. Lõpupoole läheb keeruliseks. King algoritmi detaile ei pea oskama, aga põhiideest tuleks aru saada. Ca lk 73 läheb värk päris keeruliseks ja sealt edasi võid katki jätta. Abiks võib olla see coursera loeng mis juhatab sama probleemi aeglaselt sisse, aga ei jõua veel selle lahendusvariantideni. järgmine loeng selgitab juba ühte lahendusvarianti analoogiliselt powerpoindile.

Kui jõuad ja sul tekib ekstrahuvi teema vastu, siis siit leiad põhjaliku kogu keerukamate artiklite lühikokkuvõtetega edasiuurimiseks (see ei ole üldse kohustuslik).

Konsensuse jätk - Raft - ning fork ja thread algus: 12 aprill

2023 loengusalvestus

Fork/thread loengumaterjal: Processes_fork_thread.pptx, Processes_fork_thread.pdf.

Selle nädala teemaks on

• Rafti konsensusalgoritm
  • raftist vt ka head visualisatsiooni ja originaalartikkel ja detailsemalt selgitav sari osa 1, osa 2, osa 3.
  • ja vbl veidi ka Raft/Paxos võrdlust.
  • ja veidi byzantine fault tolerance teemal.
  • ja misasi on CAP theorem

• Parallelismi baasmehhanismid tavaprogrammides, konkreetselt fork, thread ja shared memory. Uurime neid asju C/opsüsteemi tasemel: abstraktsemates keeltes kasutatakse neidsamu C/opsüsteemi mehhanisme. Sul on vaja (a) aru saada, mida need mehhanismid teevad, (b) panna käima näited:
  • fork
  • threads tutorial ja sarnane tutorial
  • shared memory
  • Thread, Queue ja Lock Pythonis
  • Beej's guide to interprocess communication, vaata ka multithreading chapter in Beej's guide to C programming

Viimaste taustaks on kasulik vaadata korra protsesside managementi linuxis.

Näidete käimapanekuks on väga soovitav kasutada linuxit või maci: threadid ja shared memory (aga mitte fork) on olemas ka windowsis, aga ülaltoodud materjalide näited on linuxi (üldisemalt, unixi) näited. Logi sisse dijkstrasse, kasuta mõnda muud linuxi masinat, millel sulle ligipääs, või pane windows 10s käima wsl (windows subsystem for linux). Kui sul juba ei ole installeeritud C kompilaatorit, installeeri gcc või clang.

Soovitus kuulata Jim Kelleri episoodi "Moore's Law, Microprocessors, Abstractions, and First Principles" heast ja populaarsest ai podcastist: Jim räägib mh pikemalt protsessori-sisesest parallelismist ja automaatsest branchi-ennustamisest.

Thread/fork ja lukustamine: 19 aprill

Priidu loeng.

Loengusalvestus.

Selle nädala eesmärk on (a) jätkata thread/fork teemaga (b) aru saada lukustamise baasmehhanismidest.

Lukustamine on vajalik paralleelsete protsesside juures, mis kasutavad ühist mälujuppi / muutujat, kas siis näiteks threadide ühises mäluosas või shared memorys.

Lukustamise jaoks on mitu erinevat mehhanismi ja kasutusstenaariumi ning nad vajavad veidi tuge protsessorilt spetsiifiliste atomaarsete käskude näol.

Järgmine nädal liigume lukustamise juurest edasi paralleelsusse andmebaasides: seal on jällegi hulk võimalikke probleeme ja mitmeid lahendusviise, mis alusena kasutavad baas-lukustamismehhanisme.

Loe selles järjekorras ja vaata läbi ka need kolm lühikest loengut:

• Lukustamise sissejuhatav presentatsioon: räägib alustuseks praktilistest vajadustest ja põhimehhanismidest (andmebaaside paralleelsuse teemasse süveneme järgmine nädal).
• Detailsem konspekt lukustamise kohta: semafor, mutexid ja detailselt spinlockist. Loe seda aeglaselt!
• spinlocki loeng arusaamise hõlbustamiseks
• spinlocki riistvara-tuge seletav loeng
• loeng semafor vs mutex: mis on mis

Lisaks võib lugeda:

Introduction to Transactions (slaidid)

Sünkroniseerimisprimitiivid: slaidid

Mittekohustuslik lisalugemine:

Konspekt pikemalt ja põhjalikumalt loengus läbitud teemadest.

Riigi infosüsteem: 26 aprill iseõpe

26 aprill loengut ei toimu: palun vaata läbi eelmise aasta loengusalvestus ja tutvu siin allpool olevate materjalidega.

link 2021 loengusalvestusele: olemas

Lisaks: veidi seotud taust on suur valdkond: Hajutatud andmebaaside teema lahtikirjutus ja lugemisülesanded

Esialgu antud link 2022 loengusalvestus järelvaatamiseks: mis paistab olema ekspireerunud ja kadunud!

Suured praktilised hajussüsteemid: arhitektuur, probleemid, lahendused: 3 mai

Loeng Ukult Wisest.

Loengusalvestus 2023

Varuteemad: otsustame loengus. 10 mai

Loengusalvestus 2023

Teemad:

• Täienduseks 26. aprilli iseõppe nädalale: riigi IT haldamise süsteem, poliitika ja praktika. Selle taustaks Lühiülevaade riigi infosüsteemist ja x-tee märkmed loengust
• Hajutatud andmebaasidest edasi: Hajutatud andmebaaside teema lahtikirjutus ja lugemisülesanded

Eksamikonsultatsioon: 17 mai

Kuidas eksam toimub, mida küsitakse, kuidas ja kust õppida.