Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Coding Interview Prep > Distributed Systems > Flashcards

Distributed Systems Flashcards

1
Q

Data Model

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Schema Evolution

A

Avro - Backward/Forward

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Why Replication ?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Leader based replication

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Replication lag

A
  • Eventual consistency
  • Read-after-write consistency
  • Monotonic reads
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Append only Log structured format

A

SS tables

LSM

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Update format

A

B+ tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Partition Types

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Skewed or hot spot ?

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Disadvantages of Hashed Parition

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Secondary Indexes - local store (document)

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Secondary index - term (global)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Partition rebalancing

A

moving data to another node ( rebalance)

  • to upgrade the node
  • node removed…

Rebalancing
-

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Service discovery or request routing

A

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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

How to Handle partition changes in request routing ??

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Service discovery frameworks

A

Consul

Eureka

17
Q

Map reduce - batch processing

A

Mapreduce jobs Hdfs

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

18
Q

SS table

A

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

19
Q

Ss table compaction

A

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

20
Q

Bloomfilters

A

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
21
Q

LSM

A

Log structured merge trees

22
Q

Distributed System Characteristics

A
  • Scalability
  • Reliability
  • Availability
  • Manageability
  • Efficiency
23
Q

Scalability

A
  • 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.

24
Q

Reliability

A

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.

25
Q

Availability

A

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.

26
Q

Manageability

A

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.

27
Q

Efficiency

A

Latency/Response Time

Throughput

28
Q

Load Balancing

A

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
     -
29
Q

Caching

A

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
30
Q

Front End - Server communications

A

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

31
Q

ACID - Isolation

A

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:

32
Q

Distributed Tracing

A

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
33
Q

Data Migration

A

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

Coding Interview Prep (21 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions