NoSQL and Beyond

; Key-value store: just an association list.

(define store (list))

(define (kv-set key value)
  (set! store (cons (cons key value)
    (filter (lambda (p) (not (string=? (car p) key))) store))))

(define (kv-get key)
  (let ((found (assoc key store)))
    (if found (cdr found) #f)))

(define (kv-delete key)
  (set! store (filter (lambda (p) (not (string=? (car p) key))) store)))

(kv-set "user:1" "Alice")
(kv-set "user:2" "Bob")
(kv-set "session:abc" "user:1")

(display "GET user:1 = ") (display (kv-get "user:1")) (newline)
(display "GET session:abc = ") (display (kv-get "session:abc")) (newline)

(kv-delete "user:2")
(display "GET user:2 = ") (display (kv-get "user:2"))

# Document store simulation
import json

class DocumentStore:
    def __init__(self):
        self.docs = {}
        self.next_id = 1

    def insert(self, doc):
        doc_id = str(self.next_id)
        self.next_id += 1
        self.docs[doc_id] = doc
        return doc_id

    def find(self, query):
        """Find docs matching all key-value pairs in query."""
        results = []
        for doc_id, doc in self.docs.items():
            if all(doc.get(k) == v for k, v in query.items()):
                results.append((doc_id, doc))
        return results

db = DocumentStore()
db.insert({"name": "Alice", "age": 30, "tags": ["admin", "dev"]})
db.insert({"name": "Bob", "age": 22, "dept": "sales"})
db.insert({"name": "Carol", "age": 30, "tags": ["dev"]})

# Different documents have different shapes - that is fine
print("All docs:")
for doc_id, doc in db.docs.items():
    print("  " + doc_id + ": " + json.dumps(doc))

print()
print("Find age=30:")
for doc_id, doc in db.find({"age": 30}):
    print("  " + doc_id + ": " + doc['name'])

; Graph database: nodes and edges with traversal.

(define nodes
  (list (cons "alice" "person")
        (cons "bob" "person")
        (cons "carol" "person")
        (cons "proj1" "project")))

(define edges
  (list (list "alice" "knows" "bob")
        (list "alice" "knows" "carol")
        (list "bob" "works-on" "proj1")
        (list "carol" "works-on" "proj1")))

; Traverse: who does Alice know?
(define (neighbors node rel)
  (map caddr
    (filter (lambda (e)
      (and (string=? (car e) node)
           (string=? (cadr e) rel)))
      edges)))

(display "Alice knows: ")
(display (neighbors "alice" "knows")) (newline)

; Two-hop: what projects do Alice's friends work on?
(display "Projects of Alice's friends:") (newline)
(for-each
  (lambda (friend)
    (let ((projects (neighbors friend "works-on")))
      (for-each (lambda (p)
        (display "  ") (display friend)
        (display " -> ") (display p) (newline))
        projects)))
  (neighbors "alice" "knows"))

; CAP theorem: pick two.
; CP systems: consistent but unavailable during partition (e.g., HBase)
; AP systems: available but may return stale data (e.g., Cassandra)
; CA systems: not partition-tolerant (single-node relational DB)

(define systems
  (list
    (list "PostgreSQL (single)" "CA" "No partition tolerance")
    (list "HBase / MongoDB"     "CP" "Blocks during partition")
    (list "Cassandra / DynamoDB" "AP" "Eventual consistency")
    (list "Spanner"             "CP" "Uses TrueTime for global consistency")))

(for-each
  (lambda (s)
    (display (car s))
    (display " [") (display (cadr s)) (display "] - ")
    (display (caddr s))
    (newline))
  systems)

# Eventual consistency simulation: three replicas

import random

class Replica:
    def __init__(self, name):
        self.name = name
        self.data = {"x": 0}
        self.pending = []

    def write(self, key, value):
        self.data[key] = value
        print("  " + self.name + ": wrote " + key + "=" + str(value))

    def sync_to(self, other):
        for k, v in self.data.items():
            if other.data.get(k) != v:
                other.data[k] = v

replicas = [Replica("R1"), Replica("R2"), Replica("R3")]

# Write to R1 only
print("Write x=42 to R1:")
replicas[0].write("x", 42)

print()
print("Before sync:")
for r in replicas:
    print("  " + r.name + ": x = " + str(r.data['x']))

# Sync propagates
print()
print("Syncing...")
replicas[0].sync_to(replicas[1])
replicas[0].sync_to(replicas[2])

print()
print("After sync (eventual consistency achieved):")
for r in replicas:
    print("  " + r.name + ": x = " + str(r.data['x']))