General

• Retrospektive as base
• Use anki

Schwerpunkte

• ACID / BASE / theorems
• types of stores
• the things found in the labs
• which one is which
• B-trees

Anki

• image occlusions are nice

CAP, ACID, BASE

• There’s no CA in CAP
• ACID is stronger and harder and more complex
• BASE is AVAILABILITY FIRST
  • recentness comes later

Consistency modes

• Strong - the easiest
• Eventual consistency: everything will be easy after the inconsistency window
• Read-your-writes consistency
• Monotonic read consistency:
  • You’ll never read an earlier version than the one you already read

Key-value stores

• easy but simple, checks client-side
• DONE amazon dynamo example of adding/deleting
  • I had it wrong! “A”’s values are BEHIND A!
• DONE vector clocks with amazon dynamo versioning
  • mostly clear
• Lamport clocks concurrent events:
  • A happens-before B IMPLIES An < Bn
  • An < Bn DOESN"T AUTOMATICALLY MEAN IT HAPPENED BEFROE
    • Either happened before or concurrent
  • !assets/2023-02-07-191934_1177x238_scrot.png !assets/2023-02-07-192406_1159x746_scrot.png

Redis replication:

• !assets/2023-02-07-193648_1097x711_scrot.png
• TODO redis clusters and replication in general, esp availabilityg:
• !assets/2023-02-07-200143_1099x615_scrot.png
• !assets/2023-02-07-200153_1126x658_scrot.png

Doc. stores

• TODO syntax and aggregation framework!!!
• TODO hash- and range-based sharding, review sl. 31 !assets/2023-02-07-210424_1441x870_scrot.png

MongoDB

Replication:

• there’s primary and secondary
• writes go to primary, asynchronously applied to secondaries
  • worked if majority gave the OK
• reads: default go to primary-first
  • otherwise you can do secondary-first, nearest etc.
  • eventual consistency

B-trees

• TODO understand adding elements to it! - kap4 sli 43
• self-balancing thing it uses to access the documents. Not fully balanced (fb is when same legth to all leafs and same num of docs in each index) but going there.
• B-trees in 4 minutes — Intro - YouTube / B-trees in 6 minutes — Properties - YouTube
  • Multiple children in each node
  • goal: reduce height (=disk operations)
  • !assets/2023-02-08-161945_1233x644_scrot.png
    • Each node has n keys and n+1 children.
• bounds / degree of tree t: (TODO is this the same as ORDER M, where it’s nodes who are max 2m and children 2m+1?)
  • uppermost and lowermost bound
  • children: t<n children<2t
  • keys: t-1<n keys<2t-1
  • !assets/2023-02-08-174441_1260x689_scrot.png

Inserting stuff in B-tree

Order m means leaf node has to have <2m element. If it fits it fits, if not create new node pushing the median element to the parent node. !assets/2023-02-08-175735_986x636_scrot.png

!assets/2023-02-08-175847_1157x852_scrot.png

B+ trees

B+ Trees Basics 2 (insertion) - YouTube !assets/2023-02-08-181209_1476x1079_scrot.png

• Resources:
  • Effective MongoDB indexing (part 1) | dbKoda
  • Deeper dive: MongoDB Index: Deep Dive, Understanding Indexes. | by Arun Pratap | The Startup | Medium
  • MongoDB Index: Deep Dive, Understanding Indexes. | by Arun Pratap | The Startup | Medium

CouchDB

• All of it basically TODO especially wrt mapreduce