System Design

1. Load Balancer (reverse Proxy)
a. Increase throughput (App, Cache, DB)
b. Increasing Availability (as X3 controller) (App, Cache, DB)

Load Balancing Methods.

  1. Round Robin (Apps, cache)
  2. least connections (App, Cache)
  3. hashing (stateful and DB)
DNS-based Geo location load balancing
1. Increase throughput
2. Increase availability
3. Reduce response time:

 DNS have the front end IPs in Geo location. 
Routers using IP anycast finds the shortest path to the IP according to its geo location.

2. Redis(In-memory Hash Table Storing)
1. Redis and memcache have key value pairs for cache
2. Sap Hana and Aerospike have AVL tree base implementation so it is good for range query and sort query result. 
3. Kafka (Streaming Pub/Sub event processing)
Distributed event queue
5. CDN (Content Distribution Network)
Proxy Cache: App + cache. Serve for static contents if the system is a read oriented system.
Pros: faster response time, reduced the Internet traffic. 
6. Cache
Cache mostly helps for throughput because DB delay hold time for finish the client requests.

def write(k, v):
     write-into-DB(k, v)
     Delete(k) # Put-Cache(k, v) occurs stale data
def read(k):
     v = get(k)
     if v == None:
          v = Get-From-DB(k)
          put-cache(k,v)
     return v

Cache Strategy
1. Cache-aside
2. Read-through
3. write-back (faster but data can be lost permanently)

Cache eviction strategy: LRU cache

 

7.Sharing/Partitioning
Break up the data accross multiple machines.

Using hash, Shading can be distributed equally. If we do shading with the first name, we can manaually distribute the data such as shade1(a- d), shade2 (e-l), shade3(m-r), sharde4(s-t), shade 5(u-z). One servers is full and some servers are 30 % capacity Then we need to rehash the full server to two or three servers, which is very expensive.

 

8. Rehashing
ShardID = md5(key)%(s + 1)

The Servers are equally distributed when one server reached 70% of its capacity, all others will reach around 70% of its capacity.
Then We add more servers.
ShardID = md5(key)%(s+1 + added servers)
All data and queries need to be moved from one shard server to another.
O(key)
md5(key)=13759278 %30 =18
md5(key)=13759278 %31 =21
Consistent Hashing
virtualid = md5(key)%18
serverid = virtualToServerMap[virtualid]
Map = {0: server1, 1: server1, 2: server 1, 3: server2, 4: server 2, ...}
}

 

 

Replica for Consistent Hashing
Zookeeper: Distribution configuration Management maintains the replica map
Replica MAP= {
serv0 :serv5, serv0, serv1
serv1 : serv0, serv1, serv2
serv2: serv1, serv2, serv3
serv3: serv2, serv3, serv4
serv4: serv3, serv4, serv5
serv5: serv4, serv5, serv0
}

 

9. Database
Key-value stores commonly used for caching: Redis, Memcache
Caasandra (Facebook), DynamoDB(Amazon),BigTable(Google), MongoDB: key Document(XML/Json) stores
SQLDB:
1. structured, expensive if you change schema
2. Data in rows & columns
No-SQLDB:
1. unstructured, no complicated sql language such as join and select
2. data is forms of key-value, key-document pairs, Graph DB
Columnar DB:
1. Structured 
2. fast retrievial of data in column
 SQLNoSQL
StorageTablesKey-value, document, columnar
SchemaFixed and structured (modify=> change whole database)unstructured
QueryingSQLQuerying focus on collections of data
Scalabilitypossible but challenging and timeEasy addition of servers- cost effective
ReliabilityConsistentAvailability

Decision for SQl or NoSQL

  1. Consistency or Availability
  2. Schema change later (agile=> quick iteration)
  3. Complicated Querying vs big data for collections of data

In the case of high QPS, DBMS ensure ACID so that it became slower then NOSQLDB. So the overall throughput for APP can be reduced as the DBMS can increase the process time.

SQL
normalization: Database normalization is a database schema design technique, by which an existing schema is modified to minimize redundancy and dependency of data.
This can save the storage space but it can increase computational time with querying.
CREATE TABLE Students (sid INTEGER, 
                       name CHAR(20), 
                       login CHAR(20), 
                       age INTEGER,
                       gpa REAL,
PRIMARY KEY(sid))
INSERT INTO Students VALUES(5454, "Chang", "chnaglee@gmail.com", 18, 3.2)
DELETE FROM Students WHERE name = "Chang"
UPDATE Students SET age= age +1, gpa=gpa-1 WHERE sid=345454
SELECT name, age
FROM students
WHERE sid > 56565 or gpa < 3.0 and age > 20

Transaction: a sequence of DB operations.
START TRANSACTION
UPDATE Account SET balance= balance-50 WHERE id = “Changlee”
UPDATE Account SET balance=Balance +50 WHERE id = “Changpil”
COMMIT

ACID Property
Consistency: The transaction goes to one valid state to another valid state.
Isolation: If t1, t2, t3 ..tn are tansactions submitted at the same time, then even though they are interleaved, the effect is as if it ran as one unit.
Automicity: Full or None
Durability: Permanently recorded in the DB

BIG DATA
VOLUME: web logs, social media, mobile apps, sensors (IOT)
VELOCITY: Rate at which new data is generated also exploded
VARIETY: THe new data was semi-structured/unstructured

Trend: Quick response in the sacrifice of space.

4. Replication
a. Database replication
Data replication is the process of storing the same data in multiple locations to improve availability and accessibility.
1. master/slave (Synchronous vs asynchronous)
Write goes to Master, other replicas are followers. Read can be sent from any other replicas.
Strong Consistency:  The complete transactions are to update data to all replicas. Write can take time.  
Eventual consistency: Read can be sent a stale data, but Write can be done when write updates master.
When master fails, one of the slave node can act like master.
2. Quorem based Reads and Write (Synchronous)
When writing, send write request to all replicas. Once majority of them ack the write,  consider the write successful.
if N = 3,
Strong Consistency: W = 3, R = 1
Popular: W = 2, R = 2
One node failed, the data is still consistent with timestamp added in the data. 
b. LB replication
c. Cache replication

Think about Replication for Data Center.

 

10. HTTP Long Polling vs Web Socket
Long Pulling
Response to clients only when new data is available
1. client makes HTTP request & wait for the response
2. Server wait
3. when there is an update, server send the response
4. client sends a new request
5. each request has timeout
Web Socket
Full duplex communication channel with a single TCP connection
Persistent communication
Benefits:
lower overhead
real time data transfer