My System Design Notes

Twitter

  • IDEA
  • User Requirement, Functional Requirement, Extended Requirement
  • Storage Estimates
  • Systems Design 1: Rest API
  • High Level Systems Design 2: Load balencer, API Gateways, DB, File Servers
  • Database Design
  • Data Sharding
    • User ID
  • Algorithm for the API Server

Systems Design ?

  • To understand what all components are requried ?
  • how they work ?
  • how to make use of them well ?

5 Charecteristics

  • Scalability
    • Horizantal(Scale Out)/Vertial(Scale Up)
  • Reliablity
    • $$$ costly
    • pessimistic a bit – probability of time, service/system wont be available!
    • redundancy of data, service,,… for improved Reliability
  • Availability
    • amount of time, system is available for users
      • 365 days – days for manintenance/upgrade/patch fix/tuning/..
  • Efficiency
    • its a bit perspective, related to goal/pupose of the sytem design
    • latency? thoughput?
  • Maintanbility/Serviceablity (maintenances)
    • how easy is it to add
      • features
      • bug fixes
    • how easy is it fix

Components of System Design

Consistent Hashing, CAP Theorem, Load Balancing, Caching, Data Partitioning, Indexes, Proxies, Queues, Replication, and choosing between SQL vs. NoSQL.

Load Balencers

Cache

  • Like LB, improves Scalabilit, Reliabilit, Availability by memorisation of inputss & outputs
  • Used everywheere. hardware(CPU – l3, l2 cache), operating systems(linux ate my ram), web browsers, web applications, DB’s and more
  • In System Design, Cache can be used at App Server but with LB it can increase cache misses or redundant cache
    • Global Caches
    • Distributed Caches
  • CDN – Content Delivery Network for Static Content
  • Challenge 1: Cache Data Validation/Data Invalidation Types
    • Write though Cache – Write to Cache, Write to DB
    • Write around Cache – Write directly to DB only
    • Write back Cache – Written to Cache & acknowledge is sent imm. Later pushed to DB.
  • Challenges 2: Cache Eviction Policy
    • Alogrithms
      • Least Recently Used (LRU)
      • Most Recently Used (MRU)
      • Least Frequently Used (LFU)
      • Most Frequently Used (MFU)
      • FIFO, LIFO
      • Random Replacemnet
  • Examples
    Memcached: Distributed Caching System
    – With high speed network ability, memchaed can handle upto 2L+ requests per second
    – drawbacks
    – limited by ram size usage(more ram avail. per node –> better supp)
    – https://github.com/memcached/memcached/wiki/TutorialCachingStory
    – Cache only that which is
    – high frequenctly used queries
    – high time consuming queries Alternatives – Redis, Couchbase(evolved from memcache)
    https://www.quora.com/What-are-the-differences-between-Redis-and-Memcached

Paritioning

Data Methods: In Databases, to tables are contineously growing we use to do
    - Horizantal paritioning: Different rows in different servers.
        - drawback: if the data is skewed, then equal distribution fails
    - Vertial paritioning: Different tables in different servers
        - drawback: future scope for scalability is less
    - Directory based data segregation
        - Data Pools - where data resides
        - Lookup Services which has Mapping table & know where to look for servers and queries
Data Partioning:
    - Hash based partitioned: use primary key to generated a hash no. then hash no % no.of server to get our server id.
        - drawback: Adding new server => distrubs read/write of current model => use Consistant hashing
    - List based partitioned or Region based partitioned:
        - each server carries a list of keys 
            Example: servers list [france, swiss, demark], [india], [china], [HK, singapore, islanda],..
    - Round Robin partitioned: List of n server. Write is done one after another.
    - Composite  partitioned: Combination of above techniques. GeoLocation + list based partioning
Challenges
    - DB Join, Data Normlaisation, ACID
    - Data Integrety like Unique Columns conditions, say a write fail operations due to this integrety
    - Rebalencing:
        - Data Sknewess
        - Data - Hotspots ~ load balencer issues

Others

- DB Indexes:
    - Can improve speed if table is sufficiently large b't not too large
- Proxy Server:
    - Like LB sits at client location and maintains a cache. For data connects to actual server when need. Home Router for Google Page.
    - works on behalf of servers
- Reverse Proxy Server:
    - works in behalf of client - good for long running/polling requests

Database selection

3 criterias ( 3v's - Volume, Veriety, Velocity )
    - Types of Data(structured/unstructured)
    - Queries Patterns(very high speed like cache db, good speed db,..)
    - Data Volumne

    Note: Non functioal requirement decide more than functional requirements! => CAP logics.



Data -- Strucutred
            -- ACID Style ==> Use RDBMS
                - Mysql, OracleDB, MSSql, Postgres

            -- Redis (NoSqlDB) that provide atomic transaction.
                - used as Cache

     -- Unstrucuted
            -- Need custom data structures/data types? Lots of quereis?
                ==> Use Document DB's like MongoDB and CouchDB

            -- Need infinite storage with finite queries like Uber,Swiggy test cases ?
                ==> Columnar DB like Cassendra, HBase


     -- Cache style
        - Store images, videso ==> use blob storage like Azure blob storage or S3. To serve you can use CDN.

        - Key Value db ==> Redis, Memcached, Etcd

        - Text Search ==> Elastic Search, Apache Solr

        - Image Text Search --> Tag images with text & use text searcher like Elastic Search

                Note: Elastic Search, Solr are excellent at search but can lose some doc. Always use a DB as a primary data store.

        - Timeseries/Metrics Data store?
            - Special case ?
                - No randome data writes
                - Data is only appended!
                - Data is only queried b/w time stamps.

            - Poplular data stores are InfluxDB, TimeseriesDB, OpenTSBD, Graphite


        - OLAP
            - Use HDFS

DB Stores Stats

<pre class="wp-block-syntaxhighlighter-code">REDIS => REmote DIctionary Server

- Redis can handle up to 2 ³² keys, and was tested in practice to handle at least 250 million keys per instance
- Redis Server needs only 3 MB to run
- Redis can scale but usually memory/network is bottleneck
- Redis is an in-memory but persistent on disk database

Benchmark stats:
    <a class="m-story" href="https://medium.com/@amila922/redis-sentinel-high-availability-everything-you-need-to-know-from-dev-to-prod-complete-guide-deb198e70ea6" target="_blank" data-width="1008" data-border="1" data-collapsed="">View at Medium.com</a>
    https://redis.io/topics/sentinel
    https://redis.io/topics/benchmarks

S3 - Object Store [stats]

- Least 3,500 PUT/COPY/POST/DELETE or 5,500 GET/HEAD requests per second per prefix in a bucket.
    - To further increase perf. use parallel threads, differen prefixes!
    - With 10 prefixes, parallelize reads, you could scale your read performance to 55,000 read requests per second.

- AWS Data lake applications To Amazon EC2 instance, which can be up to 100 Gb/s on a single instance.
- AWS EC2 to S3 upto 25 Gbps (Giga Bits** not Giga Bytes)

Cassendra [stats]

- Cassendra DB  Maximum recommended capacity for Cassandra 1.2 and later is 3 to 5TB per node for uncompressed data." With our current compression levels of around 17%, this translates to no more than 500-850G of compressed storage per node.</pre>

Latency Comparison Numbers stats

    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
    -----
    1 ns = 10^-9 seconds
    1 us = 10^-6 seconds = 1,000 ns
    1 ms = 10^-3 seconds = 1,000 us = 1,000,000 ns

    Credit
    ------
    By Jeff Dean:               http://research.google.com/people/jeff/
    Originally by Peter Norvig: http://norvig.com/21-days.html#answers

Big Data Processing frameworks
– Stream Processing
– Apache Kafka (also a messaging queue)
– Amazon Kinesis
– Apache Spark with HDFS/S3/Cassendra/,..

Gotchas
– Messaging Queue:
– There is only 1 subscriber liker a worker
– Keyword: Queue
– Pub Sub:
– There are lots of subscribers(Medium Article Post => Lots of users)
– Keywords: Topics

[stats]
Redis Strings are binary safe, this means that a Redis string can contain any kind of data, for instance a JPEG image or a serialized Ruby object. A String value can be at max 512 Megabytes in length.

  1. Paper practive – designs at grokking the interview – each step why this desgin?
    • what different components
    • how they work
    • how to improve efficiency
  2. Internet – search popular systemd design interview question??
    • how to Facebook works ?/
  3. Cracking the Coding Interview. (re-cap)