75 posts tagged with "system design"

AKF scale cube visualizes the scaling process into three dimensions…

1. ==Horizontal Duplication== and Cloning (X-Axis). Having a farm of identical and preferably stateless instances behind a load balancer or reverse proxy. Therefore, every request can be served by any of those hosts and there will be no single point of failure.
2. ==Functional Decomposition== and Segmentation - Microservices (Y-Axis). e.g. auth service, user profile service, photo service, etc
3. ==Horizontal Data Partitioning== - Shards (Z-Axis). Replicate the whole stack to different “pods”. Each pod can target a specific large group of users. For example, Uber had China and US data centers. Each datacenter might have different “pods” for different regions.

Want an example? Go to see how Facebook scale its social graph data store.

==One Word: Split==

==The AKF Scale Cube== tells us the three dimensions of "splitting":

1. ==Horizontal Scaling== Place many stateless servers behind a load balancer or reverse proxy, so that each request can be handled by any of those servers, eliminating single points of failure.
2. ==Business Splitting== Typical microservices divided by function, such as auth service, user profile service, photo service, etc.
3. ==Data Partitioning== Separate the entire technology stack and data storage specifically for a large group of users, for example, Uber has data centers in China and the United States, with different Pods for different cities or regions within each data center.

Motivation​

Video service over Http Live Streaming for mobile devices, which...

1. ==has limited memory/storage==
2. suffers from the unstable network connection and variable bandwidth, and needs ==midstream quality adjustments.==

Solution​

1. Server-side: In a typical configuration, a hardware encoder takes audio-video input, encodes it as H.264 video and AAC audio, and outputs it in an MPEG-2 Transport Stream

   1. the stream is then broken into a series of short media files (.ts possibly 10s) by a software stream segmenter.
   2. The segmenter also creates and maintains an index(.m3u8) file containing a list of the media files.
   3. Both the media fils and the index files are published on the web server.

2. Client-side: client reads the index, then requests the listed media files in order and displays them without any pauses or gaps between segments.

Architecture​

The essence of KV Cache is to reduce data access latency. For example, it transforms the O(logN) read/write and complex queries on a database that is expensive and slow into O(1) read/writes on a medium that is fast but also costly. There are many strategies for cache design, with common ones being read-through/write-through (or write-back) and cache aside.

The typical read/write ratio for internet services ranges from 100:1 to 1000:1, and we often optimize for reads.

In distributed systems, these patterns represent trade-offs between consistency, availability, and partition tolerance, and the specific choice should be based on your business needs.

General Strategies​

• Read
  • Read-through: A cache layer is added between clients and databases, so clients do not access the database directly but instead access it indirectly through the cache. If the cache is empty, it updates from the database and returns the data; if not, it returns the data directly.
• Write
  • Write-through: Clients first write data to the cache, which then updates the database. The operation is considered complete only when the database is updated.
  • Write-behind/Write-back: Clients first write data to the cache and receive a response immediately. The cache is then asynchronously updated to the database. Generally, write-back is the fastest.
  • Write-around: Clients write directly to the database, bypassing the cache.

Cache Aside Pattern​

Use the Cache Aside pattern when the cache does not support read-through and write-through/write-behind.

Reading data? If the cache hits, read from the cache; if it misses, read from the database and store in the cache. Modifying data? First modify the database, then delete the cache entry.

Why not update the cache after writing to the database? The main concern is that two concurrent database write operations could lead to two concurrent cache updates, resulting in dirty data.

Does using Cache Aside eliminate concurrency issues? There is still a low probability of dirty data occurring, especially when reading from the database and updating the cache while simultaneously updating the database and deleting the cache entry.

Where to Place the Cache?​

• Client side,
• Distinct layer,
• Server side.

What to Do If the Cache Size Is Insufficient? Cache Eviction Strategies​

• LRU - Least Recently Used: Keeps track of time and retains the most recently used items, evicting those that have not been used recently.
• LFU - Least Frequently Used: Tracks usage frequency, retaining the most frequently used items and evicting the least frequently used ones.
• ARC: Performs better than LRU by maintaining both recently used (RU) and frequently used (FU) items, while also recording the history of recently evicted items.

Which Cache Solution Is the Best?​

Why Should We Value Soft Skills?​

Because your job can be taken by someone with strong soft skills.

Americans have excellent speaking abilities, as their elementary education emphasizes expression, leading to articulate communication. In equal circumstances, even if Chinese individuals have better technical skills, job opportunities can still be snatched away by Americans. This is not about racial discrimination; it’s a matter of self-expression ability.

For instance, Indians have a strong presence in the U.S., especially in the management of high-tech companies, where the influence of Chinese individuals is far less. This is also due to the Indians' exceptional storytelling abilities. Although their English pronunciation may not be standard, they are willing to speak up and often get to the point. Consequently, we often see an Indian manager overshadowing several Chinese employees who may be technically superior. We often mock Indians for their “PPT governance,” but their storytelling ability is something to take note of.

This illustrates that the soft skills of “free artistry” are a shortcoming for contemporary Chinese individuals.

The Essence of an Interview is to Answer the Following Three Questions​

1. Can you do it or not?
2. Do you want to do it or not?
3. Are you a good fit or not?

How to Answer These Three Questions?​

The five discussion points in an interview.

1. Adversity. It’s not about how big the difficulties are, but how you overcame them. You need to prove that you were not only not defeated by adversity but became stronger. Ideally, downplay significant challenges with an optimistic tone. Also, take a moment to express gratitude to those who helped you during tough times, making it clear that you are a grateful person.

2. Influence. All communication issues are essentially leadership issues, and all leadership issues are fundamentally communication issues. If you are good at persuading others, it indicates you possess inherent leadership qualities.

3. Technical Proficiency. What stories can showcase your technical skills?

4. Fit. When the FBI used to interview candidates, they liked to ask what books applicants had read. Candidates would list numerous titles, but what the FBI really wanted to hear was that they had read Tom Clancy's spy novels. For a while, anyone who mentioned reading Clancy's novels had a higher chance of being hired. Eventually, this insider information leaked, and then everyone started saying the same thing, making that tactic ineffective.

5. Achievements. Compared to others, do you have any standout qualities? This is your opportunity to boast about past accomplishments. Achievements don’t necessarily have to be actual work experience.

On a larger scale, even U.S. presidential campaigns follow this pattern. Obama would say, “My father was an immigrant, and he abandoned my mother. I grew up in a single-parent household as a Black man, and it was tough for me… but none of that matters now; I am optimistic and strong.” Trump would say, “I have worked on this project, that project, and this project, and now I want to undertake a major project that benefits America.”

How to Prepare for These Five Discussion Points?​

• Try more, experience failures, and enrich your life experiences;
• Engage with more people to practice your communication and organizational skills;
• Learn some technical skills and master practical tools;
• Be good at research to understand what is happening in your field; seek opportunities to achieve results that make you stand out.

SOLID is an acronym of design principles that help software engineers write solid code within a project.

1. S - Single Responsibility Principle. A module should be responsible to one, and only one, actor. a module is just a cohesive set of functions and data structures.

2. O - Open/Closed Principle. A software artifact should be open for extension but closed for modification.

3. L - Liskov’s Substitution Principle. Simplify code with interface and implementation, generics, sub-classing, and duck-typing for inheritance.

4. I - Interface Segregation Principle. Segregate the monolithic interface into smaller ones to decouple modules.

5. D - Dependency Inversion Principle. The source code dependencies are inverted against the flow of control. most visible organizing principle in our architecture diagrams.

   1. Things should be stable concrete, Or stale abstract, not ==concrete and volatile.==
   2. So use ==abstract factory== to create volatile concrete objects (manage undesirable dependency.) 产生 interface 的 interface
   3. DIP violations cannot be entirely removed. Most systems will contain at least one such concrete component — this component is often called main.

Structured programming vs. OO programming vs. Functional programming

1. Structured programming is discipline imposed upon direct transfer of control.

   1. Testability: software is like science: Science does not work by proving statements true, but rather by proving statements false. Structured programming forces us to recursively decompose a program into a set of small provable functions.

2. OO programming is discipline imposed upon indirect transfer of control.

   1. Capsulation, inheritance, polymorphism(pointers to functions) are not unique to OO.
   2. But OO makes polymorphism safe and convenient to use. And then enable the powerful ==plugin architecture== with dependency inversion
      1. Source code denpendencies and flow of control are typically the same. However, if we make them both depend on interfaces, dependency is inverted.
      2. Interfaces empower independent deployability. e.g. when deploying Solidity smart contracts, importing and using interfaces consume much less gases than doing so for the entire implementation.

3. Functional programming: Immutability. is discipline imposed upon variable assignment.

   1. Why important? All race conditions, deadlock conditions, and concurrent update problems are due to mutable variables.
   2. ==Event sourcing== is a strategy wherein we store the transactions, but not the state. When state is required, we simply apply all the transactions from the beginning of time.

ACID (Consistency over Availability)

• Atomicity ensures transaction succeeds completely or fails completely.
• Consistency: In ACID, the C means that a transaction pre-serves all the database rules, such as unique keys, triggers, cascades. In contrast, the C in CAP refers only to single copy consistency, a strict subset of ACID consistency.
• Isolation ensures that concurrent execution of transactions leaves the database in the same state that would have been obtained if the transactions were executed sequentially.
• Durability ensures that once a transaction has been committed, it will remain committed even in the case of a system failure (e.g. power outage or crash).

BASE (Availability over Consistency)

• Basically available indicates that the system is guaranteed to be available
• Soft state indicates that the state of the system may change over time, even without input. This is mainly due to the eventually consistent model.
• Eventual consistency indicates that the system will become consistent over time, given that the system doesn't receive input during that time.

Although most NoSQL takes BASE priciples, they are learning from or moving toward ACID. e.g. Google Spanner provides strong consistency. MongoDB 4.0 adds support for multi-document ACID transactions.

Why replica and consistency?​

large dataset ⟶ scale out ⟶ data shard / partition ⟶ 1) routing for data access 2) replica for availability ⟶ consistency challenge

Consistency trade-offs for CAP theorem​

• Consistency: all nodes see the same data at the same time
• Availability: a guarantee that every request receives a response about whether it succeeded or failed
• Partition tolerance: system continues to operate despite arbitrary message loss or failure of part of the system

Any networked shared-data system can have only two of three desirable properties.

• rDBMS prefer CP ⟶ ACID
• NoSQL prefer AP ⟶ BASE

"2 of 3" is mis-leading​

12 years later, the author Eric Brewer said "2 of 3" is mis-leading, because

1. partitions are rare, there is little reason to forfeit C or A when the system is not partitioned.
2. choices can be actually applied to multiple places within the same system at very fine granularity.
3. choices are not binary but with certain degrees.

Consequently, when there is no partition (nodes are connected correctly), which is often the case, we should have both AC. When there are partitions, deal them with 3 steps:

1. detect the start of a partition,
2. enter an explicit partition mode that may limit some operations, and
3. initiate partition recovery (compensate for mistakes) when communication is restored.

Generally speaking, load balancers fall into three categories:

• DNS Round Robin (rarely used): clients get a randomly-ordered list of IP addresses.
  • pros: easy to implement and free
  • cons: hard to control and not responsive, since DNS cache needs time to expire
• Network (L3/L4) Load Balancer: traffic is routed by IP address and ports.L3 is network layer (IP). L4 is session layer (TCP).
  • pros: better granularity, simple, responsive
• Application (L7) Load Balancer: traffic is routed by what is inside the HTTP protocol. L7 is application layer (HTTP).