Systems Design 1

8:10

What is read-through cache? What is look-aside cache?
- If the cache talks to the DB, it's a read-through cache
- If it doesn't, it's a look-aside cache. Like Redis or Memcache

Misc
- TAO was read-through with a pool of existing connections to the DB
- memcache GET(key) SET(key, value) DEL(key)

Apache process pool? (2005) I thought it was threads? :(

It's 2005. Someone wrote a look-aside in-memory cache with GET SET DEL. It's a black box. Basic Apache webserver and all.
"I would like to put this on the Internet". How do I design a method to put this on the Internet.
They can put their service on Thrift or something similar

? Thrift is HTTP/2.0. What is the difference between HTTP 1/2/3?
Revisit TCP vs UDP (congestion control, exponential backoff, transmission control, retransmits with sequence numbers)
Revisit OSI model
Where do you slot a NIC into a motherboard?
How does the packet get to the proper process? What happens if you overfill the socket queue? NETBUF?
How does an outgoing packet get to the local NIC?
How do I find my local gateway router? Is it 192.168.1.1? And DHCP keeps a LAN's nameservers by MAC.
Local DNS is recursive - has the IP of the global root nameserver. Everything else is iterative.
What are DNS records? A IPv4, AAAA IPv6, CNAME alias
How do you do Secure DNS? DNS SEC?
What is DNS based on, TCP or UDP? Both? It's UDP unless the return is too big: DNSSEC, many records, IPv6, and/or zone transfers.
- https://serverfault.com/questions/404840/when-do-dns-queries-use-tcp-instead-of-udp
What are the different AS protocols? When would you use BGP or OSPF? BGP is eventually consistent, OSPF is always consistent (small nets). BGP is shortest path based on minimum hops. Explain how BGP is eventually consistent.
What are the different AS - AS agreements and traffic?
Open internet to AWS - NAT gateways are LBs. Probably an edge proxy (including NAT gateway) (something with firewall rules and DDOS protection)
How do virtual networks work? How do proxies work? How does DSR work?
How do generic IDLs work? How are Thrift/Protobufs different?
Read up on REST and SOAP (and XML?)
Read up on Thrift inter-machine communication.
Look up RPC and verify whether it's TCP?

Q: Justin Bieber posts daily on your blog. How long does it take for him to post something? (Pointy headed question)
Post is ~32K (1K words tumblr, 1B char, 32B word, small metadata) and MTU is 1500 (9k for large MTU) - 20 packets
Average upload speed is 20 mbps - 20/8 MBps - 32KB / 20/8 MBps - 13 ms - how do you break down "upload speed"? It's a rough average... :(
Subsequent read should fill the cache, unless you have a read-through cache - which always fills the cache (most are LRU).
Subsequent read can be ASYNC with returning to the user.

Assume 20 Mbps is average for servers too because servers can be in AWS while DB is in MongoDB, etc.
Cache should be colocated within the same subnet + facility. FB's TAO is deployed with the webserver fleet, intra-datacenter. 1-5ms round trip.
Cache requests are NEVER cross-regional. So 13*4 = 52 ms total.
Distributed Job Execution Engines are not popular in the open internet. :( Use Ansible or Terraform or new parallel.
Read up on BitTorrent interview question design for distribution. E/W traffic is bottlenecked on individual_server + s2s OR TOR link b/w.

Now a single memcache server is not enough, how do I distribute this to more memcached servers? LRU is "churning" i.e. low hitrate - working memory's content is changing all the time.
When JB posts a lot and millions are online, bottlenecks of single-server design everywhere are:
- Server bandwidth bottleneck immediately. Solve this with multiple webservers and 1+ load balancers.
Pareto principle: 80/20 rule. RULE OF THUMB. For LBs and webservers? What are reactive sockets? What is QUIC?
Examples of popular LBs: AWS LBs, Envoy, etc.
1 LB is usually good for hundreds of webservers but it also depends on the (stateless) load being proxied.
FB uses pick 2. Before the variance was 20% from server to server with balls + buckets, then 1% after pick 2.
Signals for "cache needs to scale" - high CPU, hitrate seasonality (variance over time, teens use it on fridays, etc), working memory, aim for 50% failover
Low hit rate - your users could be very different (servers won't naturally tend toward stability), OR you need more working memory
Reads are 1000x more frequent than writes
High CPU and low hitrate are the signals for too much cache load. I/O is the signal for too much DB load.
Read about DB indexing. It's an R/B tree on DB columns. Good for reads but not writes b/c it means writes must update the tree.
To scale the cache, add a hashring, key % HIGH_NUMBER, when you add/remove a machine, you reassign some non-consecutive shards to new machine.
Frequently you do "maintenance" to "defragment" the hashring - "shard balancing". At FB we had 300K shards for 1B users.
FB's content keyed had FBID, which NTYPE is an intrinsic part of - could be a user, post, or comment.
The hashing algorithm was assumed to be uniform - A FBIDs to <B SHARDS> to C cache servers. Eventually, this changed - some shards were 100x hotter than others in terms of CPU. So each shard was given a weight between 0-1 proportional to the load they drew over the last day.
This helped them determine the mapping to the C cache servers better. Ten 0.1 shards or 1 1.0 shards. Total weight * number of shards = shard space. These shards were shifted daily. Less expensive shards were moved first. This was called shard balancing.
More DBs - Same thing as shards but much less frequent rebalancing. This is just about data placement - moving shards around.

Common pitfall
- Caches are great with hot reads, but hot reads + hot writes is bad --> because the app needs to trigger cache backfill, else you'll have very high inconsistency.
- Hot read, cold cache: Thundering herd problem on the database. Users all come in asking for OLD content, which thunders the DB with SETs. Deduplicating requests is too hard - keeping a bloom filter is too much. You MUTEX on the DB shard + content KEY. This is called "lease get, lease set". Ask the cache for a "lease" - create the key in memcache and write the lease owner in cache. Other users can see that the content is cold but the lease is taken by another guy. Tell other users to try again later. Implemented in FB in 2012. Important for virality.
Read about NGINX.

SYSTEMS
- Memory is used for processes, scheduling, connections, etc. An argument for keeping swap on is "memory pressure". HOW TO KEEP IT ON/OFF?
- Whats the data structure of a page table? Info in a PT entry? Either the content from memory or the location in swap space.. VERIFY THIS
- READ about page faults - apparently the kernel internally page faults - major fault and minor fault? MEMORY MANAGEMENT UNIT
https://scoutapm.com/blog/understanding-page-faults-and-memory-swap-in-outs-when-should-you-worry
- RECALL COW - you don't copy over the stack until you change the stack. READ MORE
- RECALL boot loading
- RECALL signal handling
- RECALL debugging
- RECALL vmstat
- RECALL corrupt files
- recall bpf

Datadog Final Round
- Design: Build a startup from the ground up that notifies users about airline ticket deals within 10 minutes if they haven't been emailed within 24h. The company invested in a Data Science team that has a Data Model which determines if tickets are deals.
- Coding II: Given a stream of metric|value|tags_csv strings AND a set of search tags, output all tags associated with all search tags.

TO DO: write a better explanation for NIC investigation