Hajussüsteemid

Allikas: Lambda
revolutsioon

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


Endiselt on nüüd ja edaspidi praksid IT kolledzhis ICO-316, mitte Mektorys.

Aeg, koht

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

Loeng (Tanel): esmaspäeval 10:00-11:30 ruumis SOC-414.
Praktikum (Martin): teisipäeval kell 12:00-13:30 ruumis ICO-316.

Plaan on teha enamik loenguid kohapeal ja väiksem osa distantsilt. Praksid toimuvad vähemalt esialgu kohapeal, ja võimalik, et osad hiljem distantsilt. NB! Ei ole garantiid, et teamsi-salvestused alati õnnestuvad.

Kogu info, materjalid ja ülesanded on siinsamas lambda lehel.

Palun liitu kursuse teamsi grupiga: iseregistreerumise võti on q1nrfb2.

Iganädalase teamsi loengu-meeti link.

Iganädalase teamsi praksi-meeti link.


NB! Allpool olev blokkide struktuur on sarnane, kui 2025 aastal, aga mitte päris sama. 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%.

The materials below marked with the red E1 are the main materials for the exam, while E2 materials will also come up, but less and/or in a simpler form.

Nädala ülesanded

Uus nädalaülesanne, tähtaeg 21 aprill. Seekord on ülesanne veidi keerulisem, aga vabatahtlik ja annab ühe lisapunkti.

Sul on vaja koostada eksperimentaalprogramm, mis demonstreerib, et liitmine ei ole atomaarne operatsioon. Ehk siis, kui x=10 ja siis teed x=x+20, siis tulemus ei pruugi olla 30. See saab juhtuda siis, kui sul on kaks reaalselt paralleelselt jooksvat threadi, millel mõlemil ligipääs muutujale x, ning kumbki thread tegutseb xi muutmisega. Selleks, et shanss oleks reaalne, peavad nad seda muutmist pidevalt tegema, ja mingi ajaperioodi jooksul on tõenäosus, et mõni liitmine läheb valesti.

Arusaadavalt on sul vaja kasutada piisavalt low-level keelt, mis samas lubab threade kasutada (või siis forke või lihtsalt kaks eraldi käivitatavat programmi, aga sel juhul peab x olema shared memorys).

Sul on vaja ka välja mõelda, kuidas tuvastada, et liitmine on valesti (näiteks, mingi liitmiste ahela lõpptulemus ei ole oodatav). NB!

  • Optimeerivad kompilaatorid võivad sinu koodi põhjalikult segi pöörata, ole tähelepanelik!
  • See, et teine thread lihtsalt muudab xi suvalt ära (a a la x=100, siis teeme x=100+10 ja x on 110, siis teine thread muudab xi 120ks) ei ole OK näide.


Sinu ülesanne on eksperimenteerida, kuni taoline viga tekib, ja tuvastada umbkaudne tõenäosus, et ta mingi konkreetse ajaühiku jooksul vea annab.


Ülesande vastused saada meiliga nii Tanelile kui Martinile. OK tehtud ülesande eest saab ühe lisapunkti.


Praktikumid

Kokku on praktikumitöid kaks. Ülesanded jaotatakse kohustuslikuks baasosaks ja valikosadeks: igaühel oma punktiarv. Kumbki praktikum täismahus (baasosa + kõik valikosad) tehtuna annab 25 punkti. Võivad lisanduda ekstrapunktid eriti hästi tehtud osade või täienduste eest. Hilinenud kodutöö eest saab pooled muidu saadaolevad punktid.


Praktikumitööd on järgmised:

  • 1 praks on P2P rakendus: distributed ledgeri komponent. Grupitöö 1-3 inimest. See on sarnane esimesele praktikumile eelmisest aastast.

Praktikumitööde tähtajad on :

  • 2. praktikumil - 12. mai 2026. Teise praktikumi ülesandes võib veel tulla väiksemaid muutusi.

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 juhendaja saaks seda repot lugeda: kui ei ole avalik repo, lisa ta developeriks. TTU Gitlabis peab olema developer õigustes, et koodi lugeda.

Praktikumijuhendaja on Martin Verrev.

Loengukava

Kursus jaguneb laias laastus kolmeks teemaks:

  • P2P ja protokollid (neil teemadel - pluss veidi andme-apidest- esimene praks), sh distributed ledger ehk bitcoini alustehnoloogia
  • Paralleelrehkendused ja konsensus, lukustamine, sünkroniseerimine (selle kohta teine praks)
  • Näited reaalsetest hajutatud süsteemidest

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
https://www.scs.stanford.edu/24sp-cs244b/

NB! Allolevad loengumaterjalid tuleviku kohta on pärit 2024 aastast, neid kursuse käigus uuendatakse ja muudetakse. Juba toimunud või antud nädala loengumaterjalid on uuendatud 2025 aasta jaoks.

Protokollid ja P2P

Protokollid, 2. veebruar

Kohustuslikud osad lugeda:
Http ja json: võrgurakenduste protokollid 1 E1
Täiendavalt soovitav lugeda:
Gaffer on games: UDP vs TCP ja täiendavalt
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
Võrgunduse baasprotokollide kohta on soovitav lugeda (aga, need ei ole meie kursuse fookuses) siit: Beej's guides:

P2P sissejuhatus, 9. veebruar

loengumaterjal: pikem ülevaade eri P2P tehnoloogiatest E1
vikipeedia ülevaade E2
TOR wikipedias E2

Andmekodeerimine/vahetus: JSON-based tech, REST and API styles 16 veebruar

Old XML-based tech:

Mainstream: REST, JSON, Graphql:

Lugemiseks:

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

Lihtsa REST-tüüpi APIde head näited on LLMide apid:

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
    • Tutvu Google soovitustega: AIP.
    • 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

Paralleelrehkendused ja konsensus

Data synchronization, DHT, start distributed ledger: 2.märts

Sissejuhatus teemasse: andmete sünkroniseerimine. E1

Plokiahel:

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

Kasulikke linke spetsiifilise infoga: market cap, blockchain explorer, Bitcoin wiki


Blockchain continues ja DHT: 9 märts

Algul jätkame eelmise loengu lõpu materjalidega.

Seejärel distributed hash tables (DHT) :

Põhimaterjal: Chordi põhimõtted E2. 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
  • Kademliat kasutav hajutatud failisüsteem: IPFS
  • Natuke sarnase ideega mõõdukalt lihtne andmestruktuur (mitte hajutatud): skip list

Konsensus hajutatud süsteemides: 16. märts.

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.


  • 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 E1 up to page 73 (allikas siin. 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.

Kui sul rohkem huvi, siis on olemas näiteks põhjalik õpik ja meie kasutatud presentatsiooni autoril on põhjalik kursus hajutatud süsteemidest (viimane sait paistab hetkel olevat maas: ehk taastub?)

Konsensus hajutatud süsteemides jätkub 23. märts

Selle nädala teemaks on

Taustaks oluline: Phase king vs raft vs paxos vs zookeeper

Pluss:

Fork ja thread: 30 märts

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

Loengunäited paralleelvärkidest 2026

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:

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.

Distributed databases and e-government IT systems: 6. april

We will jump into the examples of distributed systems before coming back to low-level stuff such as locking/transactions next week.

Themes:


Lukustamine ja paralleelprotsessid ja transaktsioonid: 13. aprill

NB! See nädal loengut ei toimu: selle asemel iseõpe Priidu videosalvestusega: siin.

Vt ka ülal "nädala ülesanded" blokki: seal on uus ülesanne konkreetselt selle nädala teema kohta.

Nädala eesmärk on aru saada lukustamise baasmehhanismidest ja andmebaasi-transaktsioonidest.

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.

Paralleelsus andmebaasides: hulk probleeme ja mitmeid lahendusviise, mis alusena kasutavad baas-lukustamismehhanisme.

Loe selles järjekorras:

Optsionaalselt võib olla abi nendest lukustamist seletavatest videotest:

Lisaks võib lugeda:

Introduction to Transactions (slaidid) E2
Sünkroniseerimisprimitiivid: slaidid

Näited hajutatud süsteemidest

Nädalaülesandest, X-road / UXP and EU digital passport and the CIRPASS project: 20 April

Kõigepealt paar tähelepanekut viimase nädalaülesande kohta.

Then for X road see

For the digital product passport architecture, ideas and politics around it see:


Topic to be decided: 27 April

Concrete topic to be decided.

Combined machine learning: 4 May

Lecture by Priit Järv, focusing on applied research in combining machine learning by different hospitals / medical facilities.

Microservices, scaling large systems: 11 May

Your task is to look through the whole lecture recording from 2023 about scaling large distributed systems. Slides in English, speech in Estonian.

Consultation for the exam: 18 May

Overview of the exam and consultation.

Pärit leheküljelt "http://lambda.ee/w/index.php?title=Hajussüsteemid&oldid=22941"