System Design Note 汇总

最近在准备面试，特别是System Design之前没准备过，看了很多网上资料自己准备了个note，在这里分享给大家，希望对大家有所帮助。note我直接贴下面了，format，表格和图片都没有了，附件export的PDF看着会好一些（但好像手机上看不了附件？sorry我论坛小白...）
自己也准备开始面试了，如果对大家有帮助也求点大米我用来看面经啥的，谢谢





Database


Database considerations


Log File

- File format - binary format
- Delete record - append a special deletion record (also called tombstone) to the end, then it will be removed when doing file compaction
- Crash recovery - rebuild index in memory, or write index on disk to fast load
- Partially written records - include checksums
- Concurrency control - only one writer thread, and log file are append-only, multiple readers

SSTable (Sorted String Table)

- Log file, with keys sorted
- No need to story index for all keys (to save RAM space). You can find the key close to what you want, and scan from there
- write memtable (in memory balanced tree) out to disk as SSTable file
- No update after written to disk

B-Tree

- Use disk as a set of fixed-size pages that can be overwritten and update.
- Root page of index points to another page of indexes with smaller range, keep going until we reach leaf, which is the data page. Normally only 4~5 levels down.
- Being used in most relational databases

OLTP (Online Transactional Processing) VS OLAP (Online Analytic Processing)

- OLTP has small data set, random access, only store latest data. OLAP is on the opposite to serve as historical database
- Normally have OLTP DB to serve customer, then add a transform layer to move data to OLAP system
- The index needed might be different, and index might not be useful in OLAP when you query millions of data
- In OLTP DB most like you will read all data and rewrite them all together. However, in OLAP you probably only need a few columns for analysis out of a few hundred columns. So sometimes each column is stored in separate file, to avoid loading the entire row every time even when we just need a few column.

Relational database management system (RDBMS)


ACID (atomicity, consistency, isolation, durability)

- Atomicity: each transaction is treated as a single "unit" that succeeds or fails completely. It also applies to big single object, which should not be partially written.
- Consistency: transactions maintain database invariants, i.e. matching all defined rules, including constraints, cascades, triggers etc
- Isolation: Concurrent execution of transactions leaves the database in the same state that would have been obtained if they were executed sequentially
- Durability: Completed transactions are recorded in non-volatile memory


Database isolation levels

Normally use either range lock, or take a snapshot (multiversion concurrency control)  to achieve isolation levels


- Issues
- Prevent Dirty Write  (override uncommitted data)
  - Row level lock, transaction needs to wait for first transaction to be committed or aborted before it can continue
- Prevent Dirty Read
  - Row level lock can work, but not idea in practice with long running transaction locking many rows
  - Database normally hold both old and new value, and other transaction only read old value before the transaction is committed. This is also called multi-version concurrency control (MVCC)
- Lost Update: two transaction do read-modify-write and one of them might be override and lost, for example, two transaction write ID = ID + 1
  - Ways to implement:
   - Atomic write operations: UPDATE counter SET value = value + 1 WHERE xxx
   - Explicit locking: SELECT xxx FOR UPDATE; xxx; UPDATE xxx
   - Automatically detecting lost updates and retry
   - Compare and set: UPDATE xx SET content = new WHERE content = old, this fails if old changes
   - Conflict resolution: above method won't work well with replications. In that case, need to use application code or special data structure to resolve an merge different versions. Pattern: 1. SELECT, 2. check condition, 3. MODIFY DB.
- Non-repeatable reads: Needed for cases like back up or integrity checks
- Phantoms (Write Skew): Assume we need A + B > 1. A = B = 1 now. A and B do check A + B > 1, then Set A/B = 0 at the same time. We will end up with A = B = 0 if transaction happens concurrently, but it will be fine if one goes after the other.
- Isolation Leve
- Snapshot Isolation:
  - each row has create_by or delete_by, each transaction is assigned a unique and always-increasing id. Any update is treat as delete and create
  - Readers never block writers, and writers never block readers
- Serializable
  - Ways to implement
   - Actual Serial Execution
    - Each transaction must be small and fast, can also use Stored Procedure to save I/O with application
    - Only useful when active dataset can fit in memory (otherwise too slow)
    - Write throughput must be low to be handled by single CPU core
    - Can partition the data to leverage multi-core, but it has a limit given each core needs to coordinate
   - Two-phase locking
    - reader/writer block each other (which is different than snapshot isolation)
    - Implement as a row level reader-writer lock. Normally this is implemented as an index level lock for a range (might not be a row)
    - Automatically detect deadlock, abort and retry
   - Serializable Snapshot Isolation
    - Optimistic concurrency control (as opposed to the two above as pessimistic concurrency control, which blocks if there is potential to be wrong). It allows all transaction to proceed, and check on commit then abort if bad thing happened.
    - Compared to Two-phase locking: no read lock needed thus higher throughput for read heavy application
    - Compared to serial execution: not limited to single CPU core
    - The rate of aborts significantly affects the overall performance

Snapshot Isolation VS Serializable

Snapshot Isolation
Serializable
In Snapshot, the SQL server avoids locks by making use of row versioning.
In Serializable, the SQL server makes use of locks and holds them until the transaction is committed or aborted.
Follows optimistic concurrency control.
Follows pessimistic concurrency control.
The concurrency level is high in comparison to serializable.
Low-level of concurrency is achieved as one transaction needs to wait for the completion of another transaction.
Since no locks are imposed on data when it is read, other concurrent transactions are allowed to write data at the same time without any conflicts.
If two transactions try to read and write data at the same time then a deadlock occurs and one of the transactions is killed or rolled back as a deadlock victim.
If two transactions try to update the same record at the same time then an update conflict occurs and the SQL server had to kill one of the transactions.
If two transactions try to update the same record then the second transaction will wait for the first transaction to either rollback or commit.

Partition


Partition

. - Partitioning is the database process where very large tables are divided into multiple smaller parts, mainly for scalability

Vertical Partitioning (Federation)

- some column is big blob that can be put in separate table
- put sensitive data (password) to a separate table

Sharding

- Sharding means Horizontal Partitioning
- Benefits:
- Reduce index size
- Distribute database over multiple machines
- Segment data by geography, or by time (historical db)
- Drawback: SQL complexity, additional software, fail-over server complexity, backup complexity, operational complexity.

How To Partition

- By key range
- Downside: certain access patterns can lead to hot spots
- By Hash of Key
- A good hash function takes skewed data and makes it uniformly distributed
- Downside: not able to do efficient range queries
- Relieving Hot Spots
- celebrity user might cause hot spot on one key
- Add random number 1~100 before the key, so the write is evenly distributed to 100 partitions
- However, the read needs to read all 100, then combine

Partition Secondary Indexes

- By Document: each partition has it's own secondary index. Need to search all partition when search secondary index
- By Term: maintain a global index of secondary index, then partition is across node
- easy to read, can read by range
- harder to write, one write might impact multiple nodes
- need to use distributed transaction to make it right. In practical updates to global secondary indexes are often async

Rebalancing

- Don't simply use mod, this will cause most data to move
- Can set fixed high number of partitions. 10 machines, 1000 partitions, the 11th machine will just steal a few partition
- Dynamic partitioning: split into two partition when partition size exceeds config. Merge if it shrinks below config. Each node handles multiple partitions.
- Set # partitions related to number of nodes

Service Discovery

- To help client find the right partition
- Three ways
- client send to any node, the node then forward (gossip protocol)
- client send to a routing tier
- client knows the partition and directly send over
- Normally rely on separate coordination service like ZooKeeper

DB Proxy

Used to query distributed data

Denormalization

- Denormalization attempts to improve read performance at the expense of some write performance.
- Redundant copies of the data are written in multiple tables to avoid expensive joins.
- Once data becomes distributed with techniques such as federation and sharding, managing joins across data centers further increases complexity. Denormalization might circumvent the need for such complex joins.
- Disadvantage(s): denormalization
- Data is duplicated.
- Constraints can help redundant copies of information stay in sync, which increases complexity of the database design.
- A denormalized database under heavy write load might perform worse than its normalized counterpart.

NoSQL

NoSQL is a collection of data items represented in a key-value store, document store, wide column store, or a graph database. Data is denormalized, and joins are generally done in the application code. Most NoSQL stores lack true ACID transactions and favor eventual consistency.
Normally only support atomic update to single document. No transaction across multiple document.

BASE Theory

- Basically available - the system guarantees availability.
- Soft state - the state of the system may change over time, even without input.
- Eventual consistency - the system will become consistent over a period of time, given that the system doesn't receive input during that period.

Key-value store (Redis, Memcached)

Key-value stores provide high performance and are often used for simple data models or for rapidly-changing data, such as an in-memory cache layer. Since they offer only a limited set of operations, complexity is shifted to the application layer if additional operations are needed.
- O(1) reads and writes
- backed by memory or SSD
- maintain keys in lexicographic order, allowing efficient retrieval of key ranges
- Works as a giant hashtable

Document store (MongoDB, CouchDB, DynamoDB)

- centered around documents (XML, JSON, binary, etc), where a document stores all information for a given object.
- provide APIs or a query language to query based on the internal structure of the document itself.
- documents are organized by collections, tags, metadata, or directories. Although documents can be organized or grouped together, documents may have fields that are completely different from each other.
- Some document stores like MongoDB and CouchDB also provide a SQL-like language to perform complex queries. DynamoDB supports both key-values and documents.
- Document stores provide high flexibility and are often used for working with occasionally changing data.

Wide column store (Bigtable, Cassandra, HBase)

- basic unit of data is a column (name/value pair).
- A column can be grouped in column families (analogous to a SQL table). Super column families further group column families.
- You can access each column independently with a row key, and columns with the same row key form a row.
- Each value contains a timestamp for versioning and for conflict resolution.
- Wide column stores offer high availability and high scalability. They are often used for very large data sets.

Graph database (Neo4j, FlockDB)

Can handle complicated many-to-many relationship. Normally SQL database can handle it as well, but just very complicated queries to represent the relationships
- each node is a record and each arc is a relationship between two nodes.
- Graph databases are optimized to represent complex relationships with many foreign keys or many-to-many relationships.
- Graphs databases offer high performance for data models with complex relationships, such as a social network. They are relatively new and are not yet widely-used; it might be more difficult to find development tools and resources. Many graphs can only be accessed with REST APIs.

.google  иSQL or NoSQL

Although a relational database can do almost all the storage work, please remember do not save a blob, like a photo, into a relational database, and choose the right database for the right service. For example, read performance is important for follower service, therefore it makes sense to use a key-value cache. Feeds are generated as time passes by, so HBase / Cassandra’s timestamp index is a great fit for this use case. Users have relationships with other users or objects, so a relational database is our choice by default in an user profile service. Start with SQL and only move to NoSQL when necessary

Difference

- Document databases target use cases where data comes in self-contained documents and relationships between one document and another are rare, mostly one-to-many.
- Relational database handles many-to-many, but might be complicate
- Graph databases go in the opposite direction, targeting use cases where anything is potentially related to everything.

Reasons for SQL

- Structured data
- Strict schema
- Relational data
- Need for complex joins
- Transactions
- Clear patterns for scaling
- More established: developers, community, code, tools, etc
- Lookups by index are very fast

Reasons for NoSQL

- Semi-structured data
- Dynamic or flexible schema - schema changes on relational database can be slow and require downtime
- Non-relational data
- No need for complex joins
. From 1point 3acres bbs- Store many TB (or PB) of data
- Very data intensive workload
- Very high throughput for IOPS

Sample data well-suited for NoSQL

- Rapid ingest of clickstream and log data
- Leaderboard or scoring data
- Temporary data, such as a shopping cart
- Frequently accessed ('hot') tables
- Metadata/lookup tables

SQL VS NoSQL in Practice

- Start with a SQL database instead of a NoSQL database.
- The suggestion is to start with a SQL database.
- The technology is established.
- There’s lots of existing code, communities, support groups, books, and tools.
- You aren’t going to break a SQL database with your first 10 million users. Not even close. (unless your data is huge).
- Clear patterns to scalability.
- When might you need start with a NoSQL database?
- If you need to store > 5 TB of data in year one or you have an incredibly data intensive workload.
- Your application has super low-latency requirements.
- You need really high throughput. You need to really tweak the IOs you are getting both on the reads and the writes.
- You don’t have any relational data.

Cache

Putting a cache in front can help absorb uneven loads and spikes in traffic.

When to update the cache

- Cache-aside (lazy loading)
- Process
  - Look for entry in cache, resulting in a cache miss
  - Load entry from the database
  - Add entry to cache
  - Return entry
- Disadvantage(s)
  - Each cache miss results in three trips, which can cause a noticeable delay.
  - Data can become stale if it is updated in the database. This issue is mitigated by setting a time-to-live (TTL) which forces an update of the cache entry, or by using write-through.
  - When a node fails, it is replaced by a new, empty node, increasing latency.
- Write-through
- Slow on write but fast on read
- Process
  - Application adds/updates entry in cache
  - Cache synchronously writes entry to data store
  - Return
- Disadvantage(s)
  - When a new node is created due to failure or scaling, the new node will not cache entries until the entry is updated in the database. Cache-aside in conjunction with write through can mitigate this issue.
  - Most data written might never be read, which can be minimized with a TTL.
- Write-behind (write-back)
- Process
  - Add/update entry in cache
  - Asynchronously write entry to the data store, improving write performance
- Disadvantage(s)
  - There could be data loss if the cache goes down prior to its contents hitting the data store.
  - It is more complex to implement write-behind than it is to implement cache-aside or write-through.
- Refresh-ahead
- Automatically refresh any recently accessed cache entry prior to its expiration.
- Disadvantage(s)
  - Not accurately predicting which items are likely to be needed in the future can result in reduced performance than without refresh-ahead.

Redis VS Memcached

Feature
Redis
Memcached
Store key value pair in memory, NoSQL Data Store
Y
Y
Open source
Y
Y
Support different data types natively
Support String, List, Hash, Set, Sorted Set, etc
Only String
Support native persistence
Write-ahead log, or Redis Database Backup File
Third party tool
Data Eviction
LRU, TTL, Never etc
Only LRU
Replication
Natively
Third party tool
Clustering
Y
N
Support multithreading
Only in recent versions
Natively
When to use
Preferred
Only if extremely simple and only need strings

Distributed System


Resource needed


bottlenecks

- requests per second (rps)
- bandwidth
Number of required servers = max(HostNeededForRequests, HostNeededForBandwidth)

CAP


CAP Theory

- Consistency - Every read receives the most recent write or an error
- Availability - Every request receives a response, without guarantee that it contains the most recent version of the information
- Partition Tolerance - The system continues to operate despite arbitrary partitioning due to network failures
- CA
- Not practical
- CP
- Waiting for a response from the partitioned node might result in a timeout error.
- Good choice if your business needs require atomic reads and writes.
- AP
- Responses return the most readily available version of the data available on any node, which might not be the latest. Writes might take some time to propagate when the partition is resolved.
- Good choice if the business needs allow for eventual consistency or when the system needs to continue working despite external errors.

Consistency patterns

- Weak consistency
- After a write, reads may or may not see it. A best effort approach is taken.
- Weak consistency works well in real time use cases such as VoIP, video chat, and realtime multiplayer games.
- Eventual consistency
- After a write, reads will eventually see it (typically within milliseconds). Data is replicated asynchronously.
- This approach is seen in systems such as DNS and email. Eventual consistency works well in highly available systems.
- Strong consistency
- After a write, reads will see it. Data is replicated synchronously.
- This approach is seen in file systems and RDBMSes. Strong consistency works well in systems that need transactions.
- linearizability: make a system appear as if there is only a single copy of data, that is once returned a data, all following read needs to return it even if write is not finished yet across replicas
- Two-Phase Locking and Serial Execution provides linearizability, but Serializable Snapshot Isolation does not.
- Things like distributed locking and leader election must be linearizable
- Cross-channel timing dependencies: if there are two communication channels between A and B, linearizability is needed to prevent race condition.
- Replication and Lineraziability:
  - Single-leader replication - potentially lineraziable (if know leader)
  - Consensus Algorithems - linearizable
  - Multi-leader replication - not linearizable
  - Leaderless replication - probably not linearizable - Writer write on node 1, Reader1 read from 1,2, get new value, Reader 2 read from 2,3, get old value.
- Causal Consistency
- Weak than Linearizability (all events can compare), where Causal Consistency only ensure none concurrent events preserve causal dependencies. It's similar to a GIT revision tree where we branch and then merge.
- Lamport Timestamps: A pair of (Counter, NodeId) in all request/response. Counter is node level, but node will always update counter to the max it's seen in any response/request. Thus it can provide causal consistency between nodes.
- Consensus algorithm
- 1. Uniform agreement, 2. Integrity, 3. Validity, 4. Termination (algo cannot wait for node to come back, thus 2-phase commit does not satisfy)
- Important for cases like: 1. Leader Election, 2. Atomic Commit (all nodes to agree succeed or failure)
. ----- Atomic
- Easy to achieve on single node with write ahead log
- Two-phase commit: 1. asks all participants if ok to commit, 2. send commit if all ok, or abort the transaction.
  - Once the decision is made, coordinator needs to retries indefinitely to make sure it happens.
.--  - Coordinator needs to write decision to WAL to recover if it crashes, because participant needs to wait for instruction after phase one
- ZooKeeper
- Linearizable atomic operations - implement a lock using atomic compare-and-set
- Total ordering of operations - using monotonically increasing transaction ID and version number
- Failure detection - ephemeral nodes
- Change notifications - client to subscribe to notifications

Availability patterns

- Fail-over
- Active-passive: Only the active server handles traffic, the passive server takes over heartbeat stops. Downtime depends on how long to warm up.
- Active-active: Load spread between both servers. No downtime, but DNS/Application logic needs to know about both servers.
- Disadvantage(s)
  - Fail-over adds more hardware and additional complexity.
  - There is a potential for loss of data if the active system fails before any newly written data can be replicated to the passive.
- Replication
- Master-slave
  - The master serves reads and writes, replicating writes to one or more slaves, which serve only reads.
  - Slaves can also replicate to additional slaves in a tree-like fashion.
  - If the master goes offline, the system can continue to operate in read-only mode until a slave is promoted to a master (needs to redirect clients to connect to new leader) or a new master is provisioned.
  - Sync/Async replication: Impractical for all slave to be sync, otherwise any node outage would cause system halt. Normally only async (most common) or semi-sync (a few slave sync other async)
  - Potential lost of data (weakened durability) if leader failed before async write to follower (which becomes the new leader)
  - Eventual Consistency: not guarantee consistency with async replication
  - Monotonic reads: < strong consistency, > eventual consistency. Make sure user does get older data than last read. Can always point same user to same replica to achieve.
  - Consistent prefix reads: guarantees reader see the same sequence of how data is written. Achieve by putting related data in same database partition.
  - Split Brain: old leader back to work after new leader promoted
   - Fencing Token: a number that increases when a new leader selected. The leader should pass it's token with request to prevent split brain
- Master-master
  - Rarely used, since the benefits is not worth the added complexity, it only makes sense in a multi-datacenter setup with one leader in each datacenter, or for clients with offline operation to have a local leader db.
  - Both masters serve reads and writes and coordinate with each other on writes. If either master goes down, the system can continue to operate with both reads and writes.
  - Google doc can be treat as doing replication and conflict resolution between two leader db from two client
  - Disadvantage(s): master-master replication
   - You'll need a load balancer or you'll need to make changes to your application logic to determine where to write.
   - Most master-master systems are either loosely consistent (violating ACID) or have increased write latency due to synchronization.
   - Without consistent prefix reads, leader 1 -> leader 3, leader 2-> leader 3, leader 3 might receive those replication in reversed order thus keep the wrong value.
   - Conflict resolution comes more into play as more write nodes are added and as latency increases.
- Leaderless
  - Can handle multi-datacenter case
  - Client directly sends writes to several replicas, or a coordinator node does this on behalf of the client.
  - To fix wrong data, there is 1. read repair (client always read from several node, and update wrong data if it detects). 2. anti-entropy process, background process to detect/fix data
  - Quorums: w + r > n, so we read at least one up-to-date value. Normally n is odd (3, 5, 7), w=r=(n+1)/2. We can tweak w and r to achieve app need. Normally we keep w < n and r < n, otherwise one node failure cause system failure (impact availability)
   - Even with quorum consistency, it is not guaranteed to get latest value, application better to be tolerant to eventual consistency
    - 1. sloppy quorum is used, 2. two writes occur concurrently, 3. write happen concurrently with a read, 4. if write succeed on less than w notes, it is not rolled back, 5. if node with new value fails, quorum condition breaks
   - In a distributed system, a decision must rely on a quorum, because of all possible network issue and things like garbage collection. If quorum decides a node is dead, it is considered dead even if it is running healthy.
  - Sloppy Quorum: still write/read from w/r machines, but might not be the "home" node for that value when some home node is down.
   - Hinted Handoff, send the write info temporarily accepted to the "home" node when it is up
  - Conflict resolution (similar to master-master) as msg might go out of order on replicas
   - Last write wins: assign a timestamp. achieve eventual consistency but at the cost of durability. However, the timestamp might not be sync'ed between nodes, thus causing a later event stamped with earlier timestamp. Instead of using timestamp, better to use an increasing transaction id.
   - Merging concurrently written values: Need client to provide algo to merge based on version number
   - Version vectors: a vector of versions from all replica to send to client
  - Concurrent: two operations neither knows about the other (no dependency)
- Disadvantage(s): replication
  - There is a potential for loss of data if the master fails before any newly written data can be replicated to other nodes.
  - Writes are replayed to the read replicas. If there are a lot of writes, the read replicas can get bogged down with replaying writes and can't do as many reads.
  - The more read slaves, the more you have to replicate, which leads to greater replication lag.
  - On some systems, writing to the master can spawn multiple threads to write in parallel, whereas read replicas only support writing sequentially with a single thread.
  - Replication adds more hardware and additional complexity.

Load Balancer / Proxy


Load Balancer

- Benefit
- Preventing requests from going to unhealthy servers
- Preventing overloading resources
- Helping to eliminate a single point of failure
- can be implemented with hardware (expensive) or with software such as HAProxy.
- SSL termination - Decrypt incoming requests and encrypt server responses so backend servers do not have to perform these potentially expensive operations
- Session persistence - Issue cookies and route a specific client's requests to same instance if the web apps do not keep track of sessions
- Routing Algo
- Random
- Least loaded
- Session/cookies
- Round robin or weighted round robin
- Based on transport layer info - like source/target IP, ports etc
- Based on application layer info - info application put in header
- Normally Load Balancer falls under:
- DNS Round Robin (rarely used) - hard to control since DNS cache needs time to expire
- L3/L4 Load Balancer
- L7 Load Balancer
. ----- Disadvantage
- Increased complexity
- Single point of failure if not set up properly
- performance bottleneck if not set up properly

Proxy

- Benefit
- Increased security - Hide information about backend servers, blacklist IPs, limit number of connections per client
- Increased scalability and flexibility - Clients only see the reverse proxy's IP, allowing you to scale servers or change their configuration
- SSL termination - Decrypt incoming requests and encrypt server responses so backend servers do not have to perform these potentially expensive operations
- Compression - Compress server responses
- Caching - Return the response for cached requests
- Static content - Serve static content directly

Load balancer vs reverse proxy

- Deploying a load balancer is useful when you have multiple servers. Often, load balancers route traffic to a set of servers serving the same function.
- Reverse proxies can be useful even with just one web server or application server, opening up the benefits described in the previous section.

Applicate Service Tier


Micro Services

The single responsibility principle advocates small and autonomous services that work together, so that each service can do one thing well and not block others.

Service Discovery

- Zookeeper is a popular and centralized choice. Instances with name, address, port, etc. are registered into the path in ZooKeeper for each service.
- If one service does not know where to find another service, it can query Zookeeper for the location and memorize it until that location is unavailable.

Compatibility

- Backward compatibility: Newer code can read data that was written by older code.
- Forward compatibility: Older code can read data that was written by newer code.

Internet


Open Source Interconnection 7 Layer Model
. 1point3acres


Hypertext transfer protocol (HTTP)

HTTP is a method for encoding and transporting data between a client and a server. It is a request/response protocol: clients issue requests and servers issue responses with relevant content and completion status info about the request.  HTTP is an application layer protocol relying on lower-level protocols such as TCP and UDP (normally TCP).

Transmission control protocol (TCP)

- TCP is a connection-oriented protocol over an IP network. Connection is established and terminated using a handshake. All packets sent are guaranteed to reach the destination in the original order and without corruption
- To ensure high throughput, web servers can keep a large number of TCP connections open, resulting in high memory usage. It can be expensive to have a large number of open connections between web server threads and say, a memcached server. Connection pooling can help in addition to switching to UDP where applicable.
- TCP is useful for applications that require high reliability but are less time critical. Some examples include web servers, database info, SMTP, FTP, and SSH.
- Use TCP over UDP when:
- You need all of the data to arrive intact
- You want to automatically make a best estimate use of the network throughput

User datagram protocol (UDP)

- UDP is connectionless. Datagrams (analogous to packets) are guaranteed only at the datagram level. Datagrams might reach their destination out of order or not at all. UDP does not support congestion control. Without the guarantees that TCP support, UDP is generally more efficient.
- UDP can broadcast, sending datagrams to all devices on the subnet. This is useful with DHCP because the client has not yet received an IP address, thus preventing a way for TCP to stream without the IP address.
- UDP is less reliable but works well in real time use cases such as VoIP, video chat, streaming, and realtime multiplayer games.
- Use UDP over TCP when:
- You need the lowest latency
- Late data is worse than loss of data
- You want to implement your own error correction

Batch Processing


Map-Reduce


Usage

- Generate a structure output, so not specifically for analytics
- Can be used to generate indexes for large dataset
- Can also be used to handle raw data then feed into data warehouse for analytic purpose

HDFS
.--
- Share nothing (compared to NAS which shares disk), just need daemon process on each machine, and a central server called NameNode to keep track which file blocks are on which machine.

MapReduce pros

- Putting the computation near the data (run mapper on the machine where the data lives)
- Do sort-merge joins: mapper use same key (uuid for example) for all data, then reducer will receive all data related to the uuid in one shot to process
- Do Group-By
- Existing implementation to send to multiple reducers to handle hot key
- Fault tolerance, can rerun a small portion without impacting the entire job. Can also frequently write intermediate state to disk.

Interview


Powers of two table

```
Power           Exact Value         Approx Value        Bytes
---------------------------------------------------------------
7                             128
8                             256
10                           1024   1 thousand           1 KB
16                         65,536                       64 KB
20                      1,048,576   1 million            1 MB
30                  1,073,741,824   1 billion            1 GB
32                  4,294,967,296                        4 GB
40              1,099,511,627,776   1 trillion           1 TB
```

Latency

```
Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

Notes
-----
nanosecond  1 ns = 10^-9 seconds
microsecond 1 us = 10^-6 seconds = 1,000 ns
millisecond 1 ms = 10^-3 seconds = 1,000 us = 1,000,000 ns

Read sequentially from HDD at 30 MB/s
Read sequentially from 1 Gbps Ethernet at 100 MB/s
Read sequentially from SSD at 1 GB/s
Read sequentially from main memory at 4 GB/s
6-7 world-wide round trips per second
2,000 round trips per second within a data center
```
- Latency is the time to perform some action or to produce some result.
- Throughput is the number of such actions or results per unit of time.
- Generally, you should aim for maximal throughput with acceptable latency.


补充内容 (2022-05-20 09:25 +8:00):
好像有些朋友说下载不了， 我重新上传了，在下面某楼（才知道发帖不能修改了），权限设成了“新农上路”，希望能帮到大家。

我也还在准备面试，求点大米刷面经，谢谢大家，也希望总结的notes对大家有帮助

好像有些朋友说下载不了， 我重新上传下，权限设成了“新农上路”。

看不到附件呢

爱力思特 发表于 2022-5-18 12:08
Export 把表格的title全都合在一起了，我试了几种方法都没法很好的export到pdf

要不干脆上传到google doc分享只读权限吧
这样大家都能随时看到你更新的内容
比如这个：https://docs.google.com/document ... ding=h.7ofxv67ol9lw

gloray曾经也是自由的风 发表于 2022-05-17 14:52:04
看不到附件呢

我这显示attach了啊，难道手机看不了附件？

爱力思特 发表于 2022-5-17 18:01
我这显示attach了啊，难道手机看不了附件？

可以下载，感谢楼主

Dynamodb 应该属于 key value store 把？
DynamoDB is a key-value store with added support for JSON to provide document-like data structures that better match with objects in application code

感谢分享，请问楼主第三页的表格是乱码了吗？

414183054 发表于 2022-05-18 11:16:54
感谢分享，请问楼主第三页的表格是乱码了吗？

Export 把表格的title全都合在一起了，我试了几种方法都没法很好的export到pdf