Distributed DB Design & Access Control: Schemas, Fragmentation, Replication & Security

TAKEAWAYS:

• Distributed databases fragment data horizontally (row-wise) or vertically (column-wise) to optimize access, but require careful placement to minimize inter-site communication.
• Replication improves availability but introduces consistency challenges (e.g., read/write conflicts in eSewa’s transaction logs).
• Access control uses discretionary (owner-based) or mandatory (role-based) models—Ncell’s SIM registration enforces mandatory access via government-issued IDs.
• Denormalization in distributed systems trades storage for speed (e.g., Daraz’s product catalog caches).
• Two-phase commit (2PC) ensures atomicity across sites but can deadlock; alternatives like saga patterns are used in Pathao’s ride-matching.
• Security layers (authentication → authorization → auditing) mirror OSI’s layered defense (e.g., NEPSE’s stock data uses TLS + role-based access).

---

1. Distributed Database Design: Fragmentation and Allocation

Distributed databases split data into fragments to distribute across sites. The goal is to minimize data movement during queries while maintaining consistency and availability.

A. Fragmentation Types

Fragmentation divides a relation into smaller, manageable parts. Two primary types:

1. Horizontal Fragmentation (Row-wise Partitioning)
   • Splits tuples based on a predicate (e.g., CUSTOMER.CITY = 'Kathmandu').
   • Example: Fragment Orders by region for NTC’s billing system.
   • Worked Example: Table: Orders(OrderID, CustomerID, ProductID, Amount, City)
     • Fragment F1: City = 'Kathmandu'
     • Fragment F2: City = 'Pokhara'
     • Query: "Show orders > Rs. 50,000 in Kathmandu" → Only F1 is scanned, reducing I/O.

2. Vertical Fragmentation (Column-wise Partitioning)

   • Splits attributes into projected relations (e.g., CustomerID, Name in one fragment; Address, Phone in another).
   • Used in data warehouses (e.g., Daraz’s inventory vs. sales data).
   • Disadvantage: Joins may be required to reconstruct original tuples.

   Original Table (Employee)	Fragment F1 (EmpID, Name, Dept)	Fragment F2 (EmpID, Salary, Bonus)
   EmpID, Name, Dept, Salary, Bonus	EmpID, Name, Dept	EmpID, Salary, Bonus

   When to Use:

   • Horizontal: Geographic distribution (e.g., bank branches).
   • Vertical: Security/compliance (e.g., hiding salaries in HR systems).

B. Allocation Strategies

After fragmentation, decide where to place fragments (sites). Key strategies:

1. Centralized Allocation

   • All fragments at one site (e.g., a single data center).
   • Pros: Simple, no replication overhead.
   • Cons: Single point of failure (e.g., NEPSE’s 2019 crash).

2. Replicated Allocation

   • Copies of fragments at multiple sites (e.g., eSewa’s transaction logs in Kathmandu and Lalitpur).
   • Pros: High availability, faster reads.
   • Cons: Write conflicts, storage overhead.

3. Partitioned Allocation

   • Each fragment at a different site (e.g., Daraz’s inventory split by warehouse).
   • Pros: Balanced load, no redundancy.
   • Cons: Slower queries requiring inter-site communication.

4. Hybrid Allocation

   • Combines replication and partitioning (e.g., hot fragments replicated, cold fragments partitioned).
   • Example: Khalti’s transaction history is replicated globally, but user profiles are partitioned by region.

C. Derived vs. Materialized Fragments

• Derived Fragments: Computed on-the-fly (e.g., SUM(Sales) per district).
• Materialized Fragments: Pre-computed and stored (e.g., NTC’s daily usage reports).
  • Trade-off: Storage vs. query speed.

---

2. Replication Strategies

Replication copies data across sites to improve availability and fault tolerance. However, it introduces consistency challenges.

A. Types of Replication

B. Replication Control Protocols

1. Primary Copy Approach
   • One primary site handles all writes; others are read-only backups.
   • Example: Google’s Spanner uses TrueTime for globally consistent clocks.

2. Update Propagation

   • Changes are propagated to replicas after commit.
   • Conflict Resolution:
     • Timestamp Ordering: Rejects late updates (e.g., double-spending in crypto).
     • Version Vectors: Tracks causality (used in Riak DB).

3. Two-Phase Commit (2PC)

   • Ensures atomicity across distributed transactions.
   • Phases:
     1. Prepare: Coordinator asks all sites to lock data.
     2. Commit: If all agree, data is updated; else, rollback.
   • Problem: Blocking (sites may wait indefinitely).
     • Solution: Three-Phase Commit (3PC) or Saga Pattern (used in Pathao’s ride allocation).

   sequenceDiagram
     participant Coordinator as "Transaction Coordinator"
     participant Site1 as "Site A"
     participant Site2 as "Site B"
     Coordinator->>Site1: Prepare()
     Coordinator->>Site2: Prepare()
     loop If both OK
       Site1-->>Coordinator: ACK
       Site2-->>Coordinator: ACK
     end
     Coordinator->>Site1: Commit()
     Coordinator->>Site2: Commit()

C. Real-World Example: eSewa’s Transaction Logs

• Problem: High availability for fund transfers during Dashain.
• Solution:
  • Replicated logs across 3 data centers (Kathmandu, Lalitpur, Biratnagar).
  • Synchronous writes to primary + 2 backups.
  • Conflict Handling: If a user transfers Rs. 10,000 twice, the timestamp ensures only the first succeeds.

---

3. Distributed Database Design Trade-offs

---

4. Access Control in Distributed Databases

Access control ensures authorized users can only access approved data. Two models:

A. Discretionary Access Control (DAC)

• Owner sets permissions (e.g., file systems, social media).
• Example: A Daraz seller can grant their assistant access to inventory but not orders.
• Mechanism: Access Control Lists (ACLs).

B. Mandatory Access Control (MAC)

• Central authority (e.g., government) enforces rules.
• Example: Ncell’s SIM registration requires citizen ID verification.
• Mechanism: Security levels (e.g., Top Secret > Confidential > Public).
  • Used in military databases or health records (e.g., Nepal’s COVID-19 data).

C. Role-Based Access Control (RBAC)

• Permissions tied to roles (e.g., Admin, Customer, Auditor).
• Example: Khalti’s dashboard shows different options for:
  • User: View balance.
  • Admin: Freeze accounts.
  • Auditor: Export transaction logs.

D. Multi-Level Security

Combines MAC + DAC for layered security:

1. Authentication: Prove identity (e.g., OTP in eSewa).
2. Authorization: Check permissions (e.g., "Can this user see this order?").
3. Auditing: Log access (e.g., NEPSE’s trade logs).

---

5. Security Threats and Countermeasures

---

In the Real World

1. eSewa’s Transaction System

   • Idea Used: Replicated primary-copy replication + quorum-based consistency.
   • How: During Dashain, when millions transact, eSewa’s primary database in Kathmandu replicates writes to backups in Lalitpur and Biratnagar. A quorum of 2 out of 3 sites must acknowledge a transfer before it’s confirmed, preventing double-spending.

2. Ncell’s Customer Data

   • Idea Used: Mandatory Access Control (MAC) + vertical fragmentation.
   • How: Ncell stores CustomerID, PhoneNumber, and PlanDetails in separate fragments. Only employees with verified clearance (MAC) can access PlanDetails, while customer service agents (DAC) see only PhoneNumber and Balance.

3. Daraz’s Inventory Management

   • Idea Used: Horizontal fragmentation by warehouse + denormalization.
   • How: Inventory is split by warehouse (e.g., Kathmandu, Pokhara). To speed up "low-stock" alerts, Daraz denormalizes by storing ProductID, Stock, and LastUpdated in one table, even though it violates 3NF.

4. NEPSE’s Stock Trading

   • Idea Used: Two-phase commit (2PC) for atomic trades + audit logs.
   • How: When you buy shares, NEPSE’s system:
     1. Locks your account (Prepare phase).
     2. Deducts funds and updates the seller’s shares (Commit phase). If either fails, both roll back. Every trade is logged for MAC auditing.

---

Exam Tip

1. Fragmentation Questions:

   • Always show how a query benefits from fragmentation (e.g., "This reduces I/O by 70%").
   • For horizontal fragmentation, write the predicate explicitly (e.g., Age > 30).
   • For vertical fragmentation, list which attributes go where in a table.

2. Replication:

   • Compare synchronous vs. asynchronous with availability vs. consistency trade-offs.
   • For 2PC, draw the sequence diagram and label blocking as a drawback.
   • Quorum systems: Memorize W + R > N (e.g., W=2, R=2, N=3 for 3 replicas).

3. Access Control:

   • DAC vs. MAC: DAC = owner-controlled (e.g., Dropbox folders); MAC = system-enforced (e.g., military data).
   • RBAC: Always list roles and permissions in a table.
   • Multi-level security: Order as Authentication → Authorization → Auditing.

4. Worked Examples:

   • Always tie to a real system (e.g., "Like eSewa’s logs, this design ensures...").
   • For conflict resolution, describe timestamp ordering or version vectors.

5. Common Pitfalls:

   • Don’t assume replication = high consistency (asynchronous replication sacrifices consistency for speed).
   • Don’t ignore allocation costs (e.g., "Replicating to 5 sites doubles storage").
   • Security: Never say "encryption is enough"—always mention authentication + authorization.

---