Distributed Systems

Question 1

Data Model

Answer 1

In memory data can be accessed using pointers/references.
Over the wire /from file data encoding/decoding has to happen.
Text - JSON, XML, CSV ( http)
Binary - Thrift, ProtoBuf, Avro

Question 2

Schema Evolution

Answer 2

Avro - Backward/Forward

Question 3

Why Replication ?

Answer 3

• To improve high availability
• Faster access
  
  • can move the data closer to the user for faster reads
• To improve read/write throughput
  
  • Multiple followers can serve read requests which improves throughput

Replication Algorithms:
Leader based: ( Master-slave or Active-Passive replication)
     Single-leader
     Multi leader
Leaderless replication

Question 4

Leader based replication

Answer 4

Leader -> followers

• Sync writes
  
  • client response sends back only when data is written into followers also.
• Async writes
  
  • once leader writes data into storage immediately responds back to the client and asynchronously sends data to its followers

Question 5

Replication lag

Answer 5

• Eventual consistency
• Read-after-write consistency
• Monotonic reads

Question 6

Append only Log structured format

Answer 6

SS tables

LSM

Question 7

Update format

Answer 7

B+ tree

Question 8

Partition Types

Answer 8

Partition by Key -value
Partition by Key Range
Partition by Hash

Question 9

Skewed or hot spot ?

Answer 9

When data is not partitioned uniformly, single partition

can have more data that other partitions (Skewed). Because of it single partition will receive high load (hot spot).

Question 10

Disadvantages of Hashed Parition

Answer 10

It naturally supports primary key. But if multiple/columns are to be searched (secondary indexes) , then it might be difficult..

Question 11

Secondary Indexes - local store (document)

Answer 11

Store secondary index pertaining to that partition also in same partition. (local indexes)

Disadvantages:
Since each partition can have secondary index value, All partitions have to be queried to construct end result.
Scatter/gather approach - send requests to all paritions and merge the results.

there could be tail latency problems with scatter gather.

Question 12

Secondary index - term (global)

Answer 12

store secondary indexes in global storage. But partition the global storage also by secondary index key.
for example : if color of the car is secondary key… partition by starting letter of the color or alphabetically…

Advantages : read efficient.. no scatte gather..
disadvantages : slow write, as data might have to be written into different partitions ( primary can into 1 partition, secondary index might go into other partitions

Question 13

Partition rebalancing

Answer 13

moving data to another node ( rebalance)

• to upgrade the node
• node removed…

Rebalancing
-

Question 14

Service discovery or request routing

Answer 14

3 different ways to achieve is

1. Client connects to any server , the server routes the request from right node and replies back
2. Routing tier / partition aware load balancer can be used to route the client requests to the right node . This layer is just a routing layer
3. Client aware of the server to connect to.

Question 15

How to Handle partition changes in request routing ??

Answer 15

• can use distributed coordinator systems like zookeeper to keep the upto date information
  Node can connect to zk and update the latest Information.

systems like Kafka , Hbase uses zk as metadata coordinator system

• other than external systems , can use discovery protocol like gossip to update the metadata . Cassandra uses gossip protocol
  
  • disadvantage is more work on the node. Advantage is avoiding external system

Question 16

Service discovery frameworks

Answer 16

Consul

Eureka

Question 17

Map reduce - batch processing

Answer 17

Mapreduce jobs Hdfs

Mapper - collects all the data local to the machine
Reducer - brings in all sorted keys together based on partition key

Question 18

SS table

Answer 18

It is append only log structure
No random writes
Key , value will be maintained in the memory called memtable.
Once memtable reaches its size , flushed into disk sstable
Reads will be scanned in memory first , then disk . So always updated value will retrieved from memory

Question 19

Ss table compaction

Answer 19

As updates are not happening , if same record has multiple updates over multiple ss tables , then compaction process will create a new sstable by discarding old values

Question 20

Bloomfilters

Answer 20

To check whether given element in the set or not

• bloomfilter guarantees there will not any false negatives
• but there could be false positives. I e element may or may not be present
• implemented using bit vector and set of hash functions
• as bit vector gets filled larger, more false positives will happen

Question 21

LSM

Answer 21

Log structured merge trees

Question 22

Distributed System Characteristics

Answer 22

• Scalability
• Reliability
• Availability
• Manageability
• Efficiency

Question 23

Scalability

Answer 23

• As system grows with data volume or transactions, it has to be scaled to handle the volume without impacting performance.

Horizontal Scalability:
Adding more nodes to the cluster to handle additional traffic.
MongoDB/Cassandra DB supports horizontal scaling.

Vertical Scalability:
Scale single machine by adding more CPU cores, Memory or Disk.
- This kind of scaling needs downtime and also high cost for single resource.

Question 24

Reliability

Answer 24

Systems should continue to work even when 1 or few components/systems fail.
To make the system reliable, we can either replicate the data or system.
It will cost more to make the system reliable.

Question 25

Availability

Answer 25

Systems is available to function over a period of time. If the system is under maintenance, then it will not be available to the user. Thus reduces the availability. Even though the system is available, it should be reliable to provide the functionalities. If it is not reliable, it will impact system availability.

Question 26

Manageability

Answer 26

How easy to maintain the system ? ex: how easy to replace failed node ? How easy to upgrade the system without downtime ? Diagnosing the problems and taking action.

Question 27

Efficiency

Answer 27

Latency/Response Time | Throughput

Question 28

Load Balancing

Answer 28

Load balancing helps to distribute the requests across servers. even if one server fails users does not have the impact. Load balancing also used for health checks. Load Balancing Algorithms: - Least Connection Method - Least response Time - Least Bandwidth - server serving with less bandwidth/sec - Round Robin - Weighted Round Robin - Ip Hash ``` Hardware Load balancers: - F5, Cisco Software Load balancers: HAProxy, Amazon ELB, Envoy - ```

Question 29

Caching

Answer 29

Caching helps to access most used data without going to disk(which is always takes time). - Application can maintain data in its local memory, thus avoids disk seek/network call. - CDN provides a set of servers to store the data. If the same data is accessed it can deliver it. - It is also important to invalidate the cache when data modified in the database. How to keep the cache match with database: - Write Through Cache - writing to cache and database before returning the response to the client. It maintains data consistency. But it adds additional latency. - Write Around Cache - data is written into db alone. Cache gets built up with cache misses. Cache misses leads to higher latency and pressure on the database. - Write back cache - write happens only to cache. in background data will be written into database. - Even though it gives higher throughput and response time, it poses the risk of data loss in case cache system failure. ``` Caching Eviction Algorithms: FIFO LIFO Least Recently Used Most Recently Used Least Frequently Used Most Frequently Used Random Replacement ```

Question 30

Front End - Server communications

Answer 30

Http Request XMLHttpRequest (Ajax) WebSocket ( Full duplex communciation) - chat SSE - Server can push data to the browser. Http2 - Server Push

Question 31

ACID - Isolation

Answer 31

Read Committed: - No dirty reads - updates are not available to read if transaction is not committed - No Dirty writes - uncommitted data will not be over written - guarantees no concurrent transactions running on the same row by applying row level lock. Only one transaction can hold the lock. - It avoids dirty reads by holding old value and uncommitted value. Returns old value for read queries. - Default in Oracle, PostgresQL, SQL Server, MemSQL. Snapshot Isolation and Repeatable Read:

Question 32

Distributed Tracing

Answer 32

Why ? - As single request can expand into multiple levels of request calls to different services, there should be a way to monitor the requests and able to find out the time taken at each level. Design goals : - Low-overhead - negligible overhead to the processing. - Application-Level transparency : Application should not write their own tracing format. It should be transparent/common so that it avoids bugs. - Scalability - Tracing system should be scalable enough. Adaptive Sampling - Instead of sending each and every request to tracing system, we can sample requests. This helps for latency sensitive applications. Instrumentation libraries should exist for - HTTP requests, RPC, SQL queries to give uniform in tracing. -> trees, spans, annotations. In trace tree consists of spans and relationship between spans are edges denotes relation to parent span. Span - is a record of timestamped log denotes start/end and app specific annotations. spanid , parentId RootSpan - span without parent. Span - span name, id , traceId, parentId, app annotations, client, server send/recv timestamps. trace context - stores info about span attributes. usually stores in thread-local storage. trace data should be language-independent. trace collection can be: - stores log files > daemons can pull logs files and store to databases. - daemons can be part of image itself. Overheads to consider: - trace generation overhead - Trace collection overhead Tune sampling frequency to reduce tracing overhead. Access patterns: - trace Id - service name Components: - Reporter - Collector - Storage - UI

Question 33

Data Migration

Answer 33

Application Dual writes: Application which writes to database also responsible for writing the change to external systems. Even though it is easy to implement, it poses consistency risks. database and external systems should have lock(PAXOS - 2 phase commit) to make sure writes are written in same order as database. Database log: - Using database log as Single source of truth and using that log to send changes to external systems. - Oracle GoldenGate - MySQL commit log