Sign in to confirm you’re not a bot
This helps protect our community. Learn more

Consistent Hashing :: Educational System Design Meetup :: 2021-Nov-13

SysDesign Meetup
2.14K subscribers
3.1K views 3 years ago
Today we covered Consistent Hashing. Mostly from the system design perspective, although we did touch on the algorithmic ideas as well. Timekeys: 0:00 Intro 0:48 PSA 1:04 Consistent Hashing (CH) 1:31 Better not start from the ring 2:40 CH: System design aspects 9:00 CH: Algorithmic aspects 9:23 A toy example 11:37 Minimizing reassignment 12:08 Imagine there are five nodes ... 14:53 Primary / backup nodes as an example 18:42 Supporting node weights 20:58 Why "virtual nodes" are IMHO misleading 22:43 Viewing the hash space as continuous 26:42 The Ring as a probabilistic data structure 31:32 The Ring: problem statement 33:34 The Ring: solution 37:46 Pictures, courtesy of `finaldie` the Final Blog 39:56 The Ring implementation notes 43:10 Back to system design: Zero orchestration 46:16 Examining key assignment history 48:13 Distributed filesystem as an example 49:58 Q: Heartbeats and who receives them with no orchestrator? 52:35 Q: How to guarante …...more
...more

Intro

0:00

PSA

0:48

Consistent Hashing (CH)

1:04

Better not start from the ring

1:31

CH: System design aspects

2:40

CH: Algorithmic aspects

9:00

A toy example

9:23

Minimizing reassignment

11:37

Imagine there are five nodes ...

12:08

Primary / backup nodes as an example

14:53

Supporting node weights

18:42

Why "virtual nodes" are IMHO misleading

20:58

Viewing the hash space as continuous

22:43

The Ring as a probabilistic data structure

26:42

The Ring: problem statement

31:32

The Ring: solution

33:34

Pictures, courtesy of `finaldie` the Final Blog

37:46

The Ring implementation notes

39:56

Back to system design: Zero orchestration

43:10

Examining key assignment history

46:16

Distributed filesystem as an example

48:13

Q: Heartbeats and who receives them with no orchestrator?

49:58

Q: How to guarantee five nines of availability?

52:35

Q: Raft or Paxos?

57:07

Mutations and high read to write ratio

1:00:59

Sharding compute (CPU), not RAM/disk

1:04:35

Q: How do CH NoSQL-s ensure consistency?

1:06:20

Q: How to work around hot keys?

1:12:11

Trading more machines for lower latency / higher throughput

1:14:39

Bad apples

1:15:33

Q: Stronger consistency and data validation?

1:19:22

Different meanings of the word consistency

1:23:02

Recap on hot keys (covered in the question before)

1:27:21

Q: More fine-grained assignment based on The Ring

1:28:08
Consistent Hashing :: Educational System Design Meetup :: 2021-Nov-13
112Likes
3,199Views
2021Nov 14
Today we covered Consistent Hashing. Mostly from the system design perspective, although we did touch on the algorithmic ideas as well. Timekeys: 0:00 Intro 0:48 PSA 1:04 Consistent Hashing (CH) 1:31 Better not start from the ring 2:40 CH: System design aspects 9:00 CH: Algorithmic aspects 9:23 A toy example 11:37 Minimizing reassignment 12:08 Imagine there are five nodes ... 14:53 Primary / backup nodes as an example 18:42 Supporting node weights 20:58 Why "virtual nodes" are IMHO misleading 22:43 Viewing the hash space as continuous 26:42 The Ring as a probabilistic data structure 31:32 The Ring: problem statement 33:34 The Ring: solution 37:46 Pictures, courtesy of `finaldie` the Final Blog 39:56 The Ring implementation notes 43:10 Back to system design: Zero orchestration 46:16 Examining key assignment history 48:13 Distributed filesystem as an example 49:58 Q: Heartbeats and who receives them with no orchestrator? 52:35 Q: How to guarantee five nines of availability? 57:07 Q: Raft or Paxos? 1:00:59 Mutations and high read to write ratio 1:04:35 Sharding compute (CPU), not RAM/disk 1:06:20 Q: How do CH NoSQL-s ensure consistency? 1:12:11 Q: How to work around hot keys? 1:14:39 Trading more machines for lower latency / higher throughput 1:15:33 Bad apples 1:19:22 Q: Stronger consistency and data validation? 1:23:02 Different meanings of the word consistency 1:27:21 Recap on hot keys (covered in the question before) 1:28:08 Q: More fine-grained assignment based on The Ring That talk on DynamoDB by Rick Houlihan I keep referring to:    • AWS re:Invent 2018: Amazon DynamoDB Deep D...   Also, around 23:45, I should have referred to the "continuous hash space" as a "Cantorian ideal", not the Platonic one :-) Slides: https://tinyurl.com/sdm-consistenthas...

Follow along using the transcript.

SysDesign Meetup

2.14K subscribers