Przejdź do treści
Biblioteka skilli
Programowanie · Nauka i wyjaśnianie

core-algorithms-system-design

/core-algorithms-system-design

Wyjaśnia i dobiera algorytmy systemów rozproszonych: hashowanie spójne, filtry Blooma, Count-Min Sketch i HyperLogLog.

Repozytorium
agent-skills ↗
Licencja
MIT
Ostatnia zmiana repozytorium
10.11.2026

Ocena i bezpieczeństwo

95/ 100Klasa: dobry
Format20 / 25
Frontmatter z nazwą i opisem, poprawna nazwa, opis do 1024 znaków, nazwa zgodna z folderem.
Odkrywalność25 / 25
Opis mówi, kiedy użyć skilla, ma sensowną długość i jest w 3. osobie.
Treść35 / 35
Co najmniej 150 słów i do 500 linii, nagłówki, listy kroków, przykłady albo kod.
Higiena15 / 15
Bez zaślepek typu TODO, bez ścieżek Windows, z licencją.
Ryzykobrak sygnałów w skanie
Pliki w paczce
1
Skrypty
0
Komentarze HTML
0
Adresy URL w SKILL.md
0
Przestarzałość

Brak sygnałów. Repozytorium zmienione 10.11.2026, bez odwołań do wycofanych modeli i API.

Licencja

MIT, otwarta: można używać i zmieniać, z zachowaniem informacji o autorze.

Co robi i kiedy

Wyjaśnia i dobiera algorytmy systemów rozproszonych: hashowanie spójne, filtry Blooma, Count-Min Sketch i HyperLogLog.

Wyzwalacze z opisu

consistent hashinghash ringvirtual nodesrendezvous hashingjump hashbloom filterfalse positive ratecount-min sketch
Oryginalny opis (EN)

Use this skill when the user says 'consistent hashing', 'hash ring', 'virtual nodes', 'rendezvous hashing', 'jump hash', 'bloom filter', 'false positive rate', 'count-min sketch', 'HyperLogLog', 'top-k', 'merkle tree', 'geohash', 'algorithms for system design interview'. Explains and sizes the probabilistic and partitioning algorithms used in distributed systems — consistent/rendezvous/jump hashing, Bloom and cuckoo filters, Count-Min Sketch, HyperLogLog, Merkle trees, geohash — with formulas, code and when to use each. Do NOT use for: rate limiting algorithms (use system-design-rate-limiting)

Jak działa

  1. Purpose
  2. Agent Protocol
  3. 1. Distributing Keys over Nodes
  4. 2. Bloom Filter (membership, no false negatives)
  5. 3. Count-Min Sketch (frequency)
  6. 4. HyperLogLog (distinct count)
  7. 5. Merkle Trees (reconciliation)
  8. 6. Geospatial Indexing
  9. 7. Decision Table
  10. 8. Anti-Patterns
Sekcje z nagłówków SKILL.md, w oryginale · 115 linii, 962 słów
Podgląd SKILL.md
---
name: core-algorithms-system-design
description: >
  Use this skill when the user says 'consistent hashing', 'hash ring', 'virtual nodes', 'rendezvous hashing', 'jump hash', 'bloom filter', 'false positive rate', 'count-min sketch', 'HyperLogLog', 'top-k', 'merkle tree', 'geohash', 'algorithms for system design interview'. Explains and sizes the probabilistic and partitioning algorithms used in distributed systems — consistent/rendezvous/jump hashing, Bloom and cuckoo filters, Count-Min Sketch, HyperLogLog, Merkle trees, geohash — with formulas, code and when to use each. Do NOT use for: rate limiting algorithms (use system-design-rate-limiting), shard topology and resharding (use system-design-database-sharding), consensus (use distributed-consensus).
version: "2.0.0"
author: "j4flmao"
license: "MIT"
tags: [system-design, algorithms, consistent-hashing, bloom-filter, hyperloglog]
---

# Core Algorithms for System Design

## Purpose
A handful of algorithms keep appearing inside caches, databases and stream processors: ways to spread keys over changing node sets, and compact sketches that answer membership, frequency and cardinality questions approximately. This skill gives each algorithm's guarantees, sizing formulas and a decision table.

## Agent Protocol

### Trigger
"consistent hashing", "hash ring", "virtual nodes", "rendezvous hashing", "jump hash", "bloom filter", "count-min sketch", "HyperLogLog", "top-k", "merkle tree", "geohash".

### Input Context
- Problem: key placement, membership test, frequency, distinct count, data reconciliation, proximity search
- Scale (items, nodes), acceptable error, memory budget, update/delete needs

### Output Artifact
Algorithm choice with sizing math and a reference implementation. No file unless requested.

### Response Format
```
Problem: {what is asked}
Algorithm: {choice} because {property}
Sizing: {parameters and formula result}
Error/guarantee: {bound}
Code: {snippet}
```

## 1. Distributing Keys over Nodes
`hash(key) % N` remaps about (N-1)/N of keys when N changes — unusable for caches and storage that scale.

| Scheme | Keys moved when a node is added | Lookup | Notes |
|--------|-------------------------------|--------|-------|
| Consistent hashing (ring) | ~K/N (only the new node's arcs) | O(log(N·v)) binary search | needs virtual nodes for balance; supports weights via vnode counts |
| Rendezvous (HRW) hashing | ~K/N | O(N) per key (score every node) | no ring state; easy weights; good for small N |
| Jump consistent hash (Lamping & Veach) | ~K/N | O(log N), no memory | nodes must be numbered 0..N-1; only add/remove at the end |
| Maglev hashing | small, bounded disruption | O(1) table lookup | used in L4 load balancers |

Ring with virtual nodes:
```python
import bisect, hashlib

def h(s: str) -> int:
    return int.from_bytes(hashlib.blake2b(s.encode(), digest_size=8).digest(), "big")

class HashRing:
    def __init__(self, vnodes: int = 160):
        self.vnodes, self.points, self.owner = vnodes, [], {}

    def add(self, node: str) -> None:
        for i in range(self.vnodes):
            p = h(f"{node}#{i}")
            bisect.insort(self.points, p)
            self.owner[p] = node

    def remove(self, node: str) -> None:
        for i in range(self.vnodes):
            p = h(f"{node}#{i}")
            self.points.remove(p)
            del self.owner[p]

    def get(self, key: str) -> str:
        if not self.points:
            raise LookupError("ring is empty")
        i = bisect.bisect(self.points, h(key)) % len(self.points)   # first point clockwise
        return self.owner[self.points[i]]
```
- Without vnodes, one node's share of the ring varies widely (the largest arc is about ln N / N of the ring); with v vnodes per node the relative imbalance shrinks roughly like 1/√v — 100–200 vnodes per node is typical.
- Replication: walk clockwise to the next R distinct physical nodes (Dynamo/Cassandra style).
- Bounded-load variants cap any node at (1+ε)× average load for hot-key resilience.

## 2. Bloom Filter (membership, no false negatives)
- m bits, k hash functions, n inserted items. False-positive probability p ≈ (1 − e^(−kn/m))^k.
- Optimal k = (m/n)·ln 2; required bits m = −n·ln p / (ln 2)² ≈ 9.6 bits per item for 1%, 14.4 for 0.1%.
- Example: 10 million keys at 1% → m ≈ 95.9 Mbit ≈ 12 MB, k ≈ 7.
- Use: skip disk reads for absent keys (LSM-tree SSTables in RocksDB/Cassandra), CDN/cache admission, crawler "seen URL" sets.
- Cannot delete: use a counting Bloom filter (counters instead of bits) or a **cuckoo filter** (supports deletes, better space at low p).
- Implementation tip: derive k indexes from two hashes (Kirsch–Mitzenmacher: g_i = h1 + i·h2 mod m).

## 3. Count-Min Sketch (frequency)
- d rows × w counters; each item increments one counter per row; estimate = min over rows. Never underestimates; overestimates by at most ε·N with probability 1−δ when w = ⌈e/ε⌉, d = ⌈ln(1/δ)⌉.
- Use for heavy hitters / top-k (pair with a min-heap), rate of events per key in streams.

## 4. HyperLogLog (distinct count)
- m = 2^b registers storing the max leading-zero run of hashed items; standard error ≈ 1.04/√m. With m = 16384 (b = 14), ~0.81% error in ~12 KB (Redis `PFADD`/`PFCOUNT` uses this configuration).
- Mergeable: union of HLLs = register-wise max — great for daily/hourly unique users rolled up.

## 5. Merkle Trees (reconciliation)
Hash leaves (data blocks/key ranges), hash pairs upward to a root. Two replicas compare roots and descend only into differing subtrees — anti-entropy in Dynamo-style stores (Cassandra repair), Git, and certificate transparency logs. Cost: O(log n) hashes to locate each difference.

## 6. Geospatial Indexing
- Geohash: interleave latitude/longitude bits into a base-32 string; shared prefix ≈ nearby (but neighbours across cell edges have different prefixes — always query the 8 neighbouring cells).
- Alternatives: S2 cells (Google), H3 hexagons (Uber) with more uniform cell areas; PostGIS/R-trees inside databases.

## 7. Decision Table
| Question | Use |
|----------|-----|
| Which node owns this key, nodes change | consistent / rendezvous / jump hash |
| Is X possibly in the set? | Bloom filter (cuckoo if deletes) |
| How often has X occurred? | Count-Min Sketch |
| How many distinct X? | HyperLogLog |
| Which replicas disagree? | Merkle tree |
| What is near this point? | geohash / S2 / H3 / R-tree |

## 8. Anti-Patterns
- Modulo hashing for cache clusters that scale out.
- Using a cryptographic hash where speed matters and security does not (prefer xxHash/MurmurHash/BLAKE2/BLAKE3 by need; never MD5/SHA-1 where security matters).
- Bloom filters sized for today's n — p degrades quickly when n exceeds the design capacity; size for growth or use scalable Bloom filters.
- Treating sketch estimates as exact in billing or compliance paths.

## 9. Checklist
- [ ] Error bound and memory computed from the formulas, for projected n
- [ ] Hash function choice justified (speed, distribution, security)
- [ ] Rebalancing cost on node change quantified
- [ ] Sketches mergeable where data is sharded

Wersje

W bazie nie ma innych skilli o nazwie core-algorithms-system-design.

Migawka bazy z 13.11.2026 · wersja paczki 3b232fea00e4 (skrót SHA-256 całej paczki)

Pobrania w ostatnich 30 dniach: 0 · ranking

Zgłoś problem z tym skillem: szkodliwa treść, błędny opis albo prośba autora o usunięcie.

Podobne skille

  • 80role-algorithms:data-structures
    Dobiera i implementuje struktury danych, od tablic haszujących i drzew B po filtry Blooma i HyperLogLog.
  • 100computer-science-algorithms
    Pomaga wybierać i implementować algorytmy i struktury danych: złożoność asymptotyczną, sortowanie, programowanie dynamiczne, grafy, algorytmy zachłanne oraz narzędzia na dużą skalę jak Bloom filter, HyperLogLog i consistent hashing.
  • 100mathguard
    Dobiera matematyczne metody dla danych o rozmiarze od 10^6: Bloom, HyperLogLog, Count-Min, MinHash/LSH, FFT, projekcję JL i sweep line, gdy klasyczne O(n log n) nie wystarcza.
  • 100mathguard
    Dobiera matematyczne metody dla danych o rozmiarze od 10^6: Bloom, HyperLogLog, Count-Min, MinHash/LSH, FFT, projekcję JL i sweep line, gdy klasyczne O(n log n) nie wystarcza.
  • 90system-design-building-blocks
    Dobiera komponenty infrastruktury według ograniczenia, które usuwają: load balancery, cache, kolejki i pub/sub, CDN, API gateway, rate limiting i consistent hashing.
  • 100sysdesign
    Tworzy interaktywną stronę HTML wyjaśniającą temat projektowania systemów i otwiera ją w przeglądarce do nauki.

Uwagi i zgłoszenia

Wiadomość trafi do Bartosza Sokolińskiego. Adres e-mail jest potrzebny tylko do odpowiedzi. Szczegóły w polityce prywatności.