Google’s S2, geometry on the sphere, cells and Hilbert curve

An informative introduction on how Google leverages geometry concepts like Hilbert curves in their famous S2 library that offers spatial indexing capabilities tuned for performance and correctness. Python code examples included.

https://blog.christianperone.com/2015/08/googles-s2-geometry-on-the-sphere-cells-and-hilbert-curve/

Hilbert curves introduction:
https://datagenetics.com/blog/march22013/index.html

#algorithms #math #geometry #python #performance #geo #fencing #spatial #index #s2 #rtree #quadtree #google

💻 The byte is not enough

Fighting spam with Guardian, a real-time analytics and rules engine

Another great story of a practical approach to fight spam at big scale that is being applied at Pinterest. Though this isn't a story of inventing some tremendous and big all-in-one solution, it still provides a nice perspective on how to grow from a small and clumsy solution to a big and robust killer feature.

https://medium.com/pinterest-engineering/fighting-spam-with-guardian-a-real-time-analytics-and-rules-engine-938e7e61fa27

#systemdesign #infrastructure #pinterest #design #scalability #performance #bigdata #hive #kafka #presto #guardian #spam #realtime #analytics #safety #security

💻 The byte is not enough

(Strong) Eventual Consistency and Conflict-free Replicated Data Types (CRDT)

Conflict-free Replicated Data Types (CRDTs) are an increasingly popular family of algorithms for optimistic replication. They allow data to be concurrently updated on several replicas, even while those replicas are offline, and provide a robust way of merging those updates back into a consistent state. CRDTs are used in geo-replicated databases, multi-user collaboration software, distributed processing frameworks, and various other systems.

However, while the basic principles of CRDTs are now quite well known, many challenging problems are lurking below the surface. It turns out that CRDTs are easy to implement badly. Many published algorithms have anomalies that cause them to behave strangely in some situations. Simple implementations often have terrible performance, and making the performance good is challenging.

Martin Kleppmann's talk on CRDT at Hydra Conf:
https://www.youtube.com/watch?v=PMVBuMK_pJY

Sean Cribbs discusses Convergent Replicated Data Types, data structures that tolerate eventual consistency:
https://www.infoq.com/presentations/CRDT/

Marc Shapiro presentation on SEC and CRTD at Microsoft Research:
https://www.youtube.com/watch?v=oyUHd894w18

#systemdesign #algorithms #sec #strong #consistency #crdt #replication #consensus #conflicts #resolution #riak #math #distributed

💻 The byte is not enough

Building scalable near-real time indexing on HBase

An arguably simple and elegant approach to enabling near real-time indexing in HBase that took place at Pinterest.

https://medium.com/pinterest-engineering/building-scalable-near-real-time-indexing-on-hbase-7b5eeb411888

#systemdesign #pinterest #hbasee #hdfs #indexing #search #faulttolerance #scalability #performance #kafka #cache #consistency #infrastructure #design

💻 The byte is not enough

🕰 Blast from the past: Please stop calling databases CP or AP

A post from 2015 where Martin Kleppmann argues about usage of CAP-theorem in context of modern distributed systems. Martin does a great job demonstrating that people tend to attribute terms like consistency and availability with the meaning that differ from the one given in the original Brewer's CAP Theorem paper, and as thus demonstrates that almost no modern distributed system could be characterized with "A" or "C" property.

https://martin.kleppmann.com/2015/05/11/please-stop-calling-databases-cp-or-ap.html

#systemdesign #theory #research #cap #brewer #kleppmann #consistency #availability #partitiontolerance #zab #consensus #linearizability #zookeeper #riak #dynamodb #cassandra #voldemort #cp #aperture

💻 The byte is not enough

Understanding Lamport Timestamps with Python’s multiprocessing library

A brief introduction into Lamport Timestamps and its implementation known as Vector Clocks that helps to distinguish casual ordering between events. Python code examples included.

https://towardsdatascience.com/understanding-lamport-timestamps-with-pythons-multiprocessing-library-12a6427881c6

#algorithms #systemdesign #distributed #ordering #clocks #vector #logical #python #research #paper #lamport #casualordering #synchronization #partial #concurrent #timestamps

💻 The byte is not enough

System Design Interview: The Bare Minimum You Need to Know about Load Balancers

Small introduction to basic things you should know about load balancers before you go for your system design interview.

https://medium.com/swlh/system-design-interview-the-bare-minimum-you-need-to-know-about-load-balancers-fc0cbe1ac276

#systemdesign #sdi #loadbalancers #performance #design #infrastructure #spof #ssl #redundancy

💻 The byte is not enough

6 Things You Need to Know About Kafka Before Using it in a System Design Interview

In a typical system design round, there's a chance you may want to leverage Kafka capabilities in your designated system. But what if an interviewer start asking you questions about Kafka's inner mechanics? Will you be able to answer those questions? Here is a list of 6 most used/interesting aspects of Kafka, knowing which will greatly improve your overall system design skills.

https://levelup.gitconnected.com/6-things-you-need-to-know-about-kafka-before-using-it-in-a-system-design-interview-1fc31451732c

#systemdesign #kafka #distributed #queue #log #infrastructure #design #shared #commit #consumer #producer #faulttolerance #reliability #scalability #performance #broker #zookeeper

💻 The byte is not enough

How Google Spanner Assigns Commit Timestamps — The Secret Sauce of Its Strong Consistency

Spanner is Google’s global scale and synchronously replicated relational database. Its research paper was first published in 2012. Spanner received much acclaim because it was the first system to distribute data at global scale and support strongly consistent distributed transactions. That seems to break the CAP theorem. But in fact, Spanner chooses consistency over availability in face of network partition. It’s just that Google’s data center infrastructure is so reliable that external users typically don’t worry about its outages. Google now offers Spanner as a service through its cloud platform.

https://levelup.gitconnected.com/how-google-spanner-assigns-commit-timestamps-the-secret-sauce-of-its-strong-consistency-8bc143614f26

#systemdesign #google #spanner #transactions #commit #distributed #database #infrastructure #scalability #consistency #quorum #performance #replication #truetime #api #clocks #synchronization #atomicity

💻 The byte is not enough

The System Design Ideas Behind Advanced Search Functions

Search, in its most basic form, can be implemented as a plain inverted index. We build the index as we add/delete/update documents, and use it during search to go from a search term to the documents that contain it. That’s all good. But if you’re more ambitious than building a simplistic lookup by keyword system, read on. This blog post is a gentle introduction to the core ideas behind some of the advanced search functions. By the way, you may recognize that a lot of the ideas here are based on the lucene index.

https://levelup.gitconnected.com/the-system-design-ideas-behind-advanced-search-functions-fa9c7d9010a3

#algorithms #search #design #inverted #index #lucene #scoring #ranking #faceting #mutation

💻 The byte is not enough

A Tricky System Design Interview Question: Explain Server Monitoring

A proactive view on how to approach server monitoring during the system design interview rounds. The article is full of unnecessary details, but it still provides a good point on topics like metrics aggregation, time-series databases and pull/push model trade-offs.

https://betterprogramming.pub/a-tricky-system-design-interview-question-explain-server-monitoring-c5be0ce54a30

#systemdesign #infrastructure #sdi #monitoring #metrics #timeseries #aggregation #prometheus #gorilla #scalability #faulttolerance #alerting

💻 The byte is not enough

Building an Append-only Log From Scratch

Append-only log, sometimes called write ahead log, is a fundamental building block in all modem databases. It’s used to persist mutation commands for recovery purposes. A command to change the database’s state will first be recorded in such a log before applying to the database. Should the database crash and lose updates, its state can be restored by applying the commands since the most recent snapshot backup. The log’s append-only nature is partly due to functional design — because we only ever need to add new commands to the end — and partly due to performance need — sequential file access is orders of magnitude faster than random file access.

https://eileen-code4fun.medium.com/building-an-append-only-log-from-scratch-e8712b49c924

#design #wal #append #log #distributed #shared #commit #log #database #level #leveldb #compaction #segments #lsmtree

💻 The byte is not enough

Log Structured Merge Tree (LSM-tree) Implementations (a Demo and LevelDB)

Log structured merge tree, or LSM-tree, is a famous data structure that has been widely adopted by many modern “big data” products, such as BigTable, HBase, LevelDB, etc. Its core idea is very simple and perhaps somewhat counterintuitive if you’re used to the traditional database architecture.

https://eileen-code4fun.medium.com/log-structured-merge-tree-lsm-tree-implementations-a-demo-and-leveldb-d5e028257330

#design #systemdesign #database #lsmtree #leveldb #sstable #index #wal #faulttolerance #performance #scalability

💻 The byte is not enough

System Design Interview: Distributed Top K Frequent Elements in Stream

The top k frequent elements question is a classic coding interview question. Viewing through the lens of system design interview however, it suddenly has a special appeal. But before we start our usual system design interview discussion, let’s quickly talk about how it’s solved in the coding interview context, which will facilitate the design discussion that follows.

https://levelup.gitconnected.com/system-design-interview-distributed-top-k-frequent-elements-in-stream-2e92d63d777e

#systemdesign #algorithms #design #topK #frequency #distributed #mapreduce #streaming #kafka #scalability #performance #countminsketch

💻 The byte is not enough

System Design Idea: Robust Streaming Data Processing

Streaming data processing, while providing benefits such as freshness and smoother resource consumption compared to their batch counterpart, has historically been associated with disadvantages like being unreliable and having approximate results. Those disadvantages, however, are not inherent characteristics of streaming data processing itself, but rather artifacts of how they have previously been implemented. As shown by Google Cloud Dataflow and the Apache Beam movement in recent years, streaming processing can be just as robust as batch processing. In this blog post, we’ll discuss how to make streaming data processing robust. A lot of the ideas here are based on MillWheel, on which Google Cloud Dataflow is said to be built.

https://levelup.gitconnected.com/system-design-idea-robust-streaming-data-processing-2e9224c33d3f

#systemdesign #infrastructure #design #streaming #beam #dataflow #MillWheel #faulttolerance #reliability #scalability #durability

💻 The byte is not enough

💡 System Design Interview: mini Twitter

How would you design Twitter? It’s essentially the same question as designing Facebook, Linkedin, or many other social media services. The key scenario in question is usually that a user can follow or unfollow other users. Any user can tweet stuff. A user should be able to see tweets, displayed in a certain order, from the users she is following — the so-called timeline. And the core discussion point is designing for scale.

https://eileen-code4fun.medium.com/system-design-interview-mini-twitter-1e0e99bd7377

#systemdesign #sdi #design #infrastructure #twitter #interview #prep #fanout

💻 The byte is not enough

System Design Interview: Replicated and Strongly Consistent Key-Value Store

Designing a replicated and strongly consistent key-value store, which sounds seemingly simple, is actually quite a tricky interview question. You’d need to have a good understanding of some of the distributed systems concepts to be able to answer this question well. If you’re not in a domain specific interview, for this kind of questions, chances are that the interviewer just wants to observe how well you can navigate through a complex design problem. In that case, the discussion itself is usually more important than the final solution.

https://levelup.gitconnected.com/system-design-interview-replicated-and-strongly-consistent-key-value-store-b690d8e15c9a

#systemdesign #infrastructure #database #dht #keyvalue #store #replication #strong #consistency #design #faulttolerance #leader #election #quorum #raft

💻 The byte is not enough

🔐 The Next Gen Database Servers Powering Let's Encrypt

Let’s Encrypt helps to protect a huge portion of the Web by providing TLS certificates to more than 235 million websites. A database is at the heart of how Let’s Encrypt manages certificate issuance. If this database isn’t performing well enough, it can cause API errors and timeouts for our subscribers. Database performance is the single most critical factor in our ability to scale while meeting service level objectives. In late 2020, Let's Encrypt upgraded the database servers and they’ve been very happy with the results.

https://letsencrypt.org/2021/01/21/next-gen-database-servers.html

#infrastructure #letsencrypt #ssl #tls #security #hardware #database #amd #intel #nvme #performance

💻 The byte is not enough

🕰 Blast from the past: The Architecture Twitter Uses To Deal With 150M Active Users, 300K QPS, A 22 MB/S Firehose, And Send Tweets In Under 5 Seconds

Toy solutions solving Twitter’s “problems” are a favorite scalability trope. Everybody has this idea that Twitter is easy. With a little architectural hand waving we have a scalable Twitter, just that simple. Well, it’s not that simple as Raffi Krikorian, VP of Engineering at Twitter, describes in his superb and very detailed presentation on Timelines at Scale. If you want to know how Twitter works - then start here.

http://highscalability.com/blog/2013/7/8/the-architecture-twitter-uses-to-deal-with-150m-active-users.html

#systemdesign #twitter #infrastructure #social #graph #highload #performance #scalability #fanout #timeline #availability #reliability #monitoring

💻 The byte is not enough

A Practical Introduction to Kafka Storage Internals

Kafka is everywhere these days. With the advent of Microservices and distributed computing, Kafka has become a regular occurrence in architecture’s of every product. This article tries explain how Kafka’s internal storage mechanism works.

https://medium.com/@durgaswaroop/a-practical-introduction-to-kafka-storage-internals-d5b544f6925f

#kafka #design #infrastructure #storage #replication #distributed #commit #log #queue #performance #scalability #partitions

💻 The byte is not enough

How to Design a Scalable Rate Limiting Algorithm

Rate limiting protects your APIs from inadvertent or malicious overuse by limiting how often each user can call the API. Without rate limiting, each user may make a request as often as they like, leading to “spikes” of requests that starve other consumers. Once enabled, rate limiting can only perform a fixed number of requests per second. A rate limiting algorithm helps automate the process.

https://konghq.com/blog/how-to-design-a-scalable-rate-limiting-algorithm/

#algorithms #design #systemdesign #rate #limiting #slidingwindow #slidinglog #fixedwindow #leakybucket #performance #faulttolerance #scalability

💻 The byte is not enough