[Day 27] Partitioning (1) - Partitioning of key-value data

Day 21 ~ Day 26 我们讨论了如何将资料分散到不同节点的 Replication,对那些大型资料集或超大的查询吞吐量来说,只用 Replication 是没有效率的,我们需要把资料切成小块,这个动作称为 partitionssharding

partitions 通常是定义如何把资料切成小块的方法,所有的小块都属於每一笔 row、document 或 record,做 partition 最主要的目的就是 scalability (Day 3Day 20),将 partition 分散到多个节点後,每一个 query 都能独立进行,所以 query 的吞吐量也能随着节点的增加而提高。

Partitioning and Replication

partition 通常会随着 replication 一起做,一个节点会储存许多不同的 partition,如果我们使用 base-leader 这个 replication 模型,组合 partition 後资料流看起来会如下图:

figure_6-1

每一个节点都能为 partition 的 leader 或 follower,其中做的事情就全部跟 Day 21 ~ Day 26 讨论的 Replication 一样,因为 partition 的 schema 是独立於 replication schema 的,所以往後几天再讨论 partition 时会忽略 replication 的事情。

Partitioning of Key-Value Data

我们该如何决定哪些资料到哪些节点上呢?

我们的目标是要把资料平均的分配到各节点上以利查询时能平均查,理论上来看, 10 个节点的查询和写入速度应该要比单 1 个节点快 10 倍 (请暂时忽略 replication的事),如果做 partition 时不公平,某些节点的 partition 资料量或查询量比其他节点大很多,我们称之为 skewed (偏斜) ;以最极限的例子来看,所有的流量最终只会查 1 个节点的 partition,其他 9 台很闲,1 个有着高流量的 partition 我们称之为 hot spot

一个最简单避免 hot spot 的方法就是把资料随机放,虽然节点的资料平均了,但缺点是你不知道资料在哪里,意味者若要查询特定 key 资料,你得去查所有节点的 partition。

在来会介绍 2 种更好、更实际的方法。

Partitioning by Key Range

首先第一种方法就是用 key 的范围做 partition (从 key 的最小值到最大值),就像下图那样,每一本百科全书都用首字字母分开放。

figure_6-2

key 的范围不用平均,因为你的资料本来就不会平均,试想这个百科全书的例子,若将字母以 2 个字母来平均分的话,T ~ Z 这区间的书会很少,这个 partition 的边界需要以资料做调整。

对於每个 partition 中的资料,我们可以保持 key 为排序的状态,例如 LSM-Tree (Day 9),这个好处就是做范围查询非常快;然而,它的缺点就是某些操作会让 partition hot spot,举例来说你现在需要存感应器的资料,key 为 timestamp,partition 为日,感应器只会在检测到某些事情时才存资料,所以你可能会有非常大量资料的 partition。

避免的方式就是用别的资讯当做第一个 key,例如感应器的名字,所以在做 partition 时会先用名字分,然後在用 timestamp。

Partitioning by Hash of Key

第二种做 partition 方法就是对 key 做 hash,因为是给 partition 用的 hash,所以我们的安全性不用太讲究,例如 Cassandra 和 MongoDB 皆使用 MD5 做为 hash 函式;许多的程序语言皆有内建 hash 函式,要留意的是这些可能不是这麽适合做 partition,例如 Java 的 Object.hashCode() 在某些目的下相同的 key 会有不同的 hash 值。

一个好的 hash 函式可让资料平均分布,如下示意图:

figure_6-3

这个 partition 边界就会很平均了,但有一好就有一坏,这个 partition 方法会损失范围查询的效率,因为 key 的排序消失了。

Cassandra 用 compound primary key 的方式来达到一种平衡,Cassandra 只 hash 第一个 key 来做 partition,然後用其他的 key 以 concatenated index 方式做 SSTables 中的排序,这个在一对多 (Day 4) 的资料关系上好处尤其明显,例如在一个社群网站,每一个 user 有许多贴文,此时若你贴文的 key 选择 [user_id, update_timestamp],你就能非常快速的查找某个 user 且也能快速的做时间范围查询。

Skewed Workloads and Relieving Hot Spots

讲了这麽多我们还得要谈谈极端例子,即使你使用 key 的 hash 做 partition,还是有可能所有的查询跟写入都是同一个 key,所以就会发生 skewed 和 hot spot,以我们网路媒体来举例,重大新闻发生时,user 都只会看那新闻,其他新闻没兴趣,该新闻的 partition 就会发生大量写入和查询。

直到今日,大多数的资料系统并不会自动侦测且补偿 skewed 工作量,所以应用程序端得有责任做这些处理,但要留意的是你让在写入时的 partition 平均了,可能会顺势拉高查询时间,例如上面那个新闻事件,我们可以在那新闻 ID 上加上 0~99 的数字,但你查询时就得要多查 100 个 partition。

老话一句,依旧需要依不同应用软件的场景做权衡,一定会有某种平衡的方法适合你公司 (例如只加 5 个数字)。


<<:  {Day27}CameraX

>>:  [Day0] 参赛初衷

Day 14 - 用 canvas 制作刮刮乐

关於前面的小画家 复刻小画家先做到昨天作为最後一篇,接下来会带各位,利用前其所学的功能,制作各种ca...

[DAY30]完赛心得

经过了这次的铁人赛,收获颇丰,因为我本身的知识量无法凑足30天,有蛮多部分都是另外去学的,让我学到了...

第18天~SharedPreference常被使用於资料储存

SharedPreference常被使用於资料储存,很适合做一些简单的资料存取 先配置按钮-因为是要...

[2021完赛纪念篇] 夜市牛排 - 台中-忠孝夜市 #水煮蛋吃到饱

半夜12点都还开着的邪恶消夜~ 台中市南区的忠孝夜市,邻近中兴大学,是许多兴大人共同的回忆,可以在这...

[Day 16]新试剂服英战士(前端篇)

挑战目标: MockNative Camp 中午打完MVC後,下午感到有点想睡,到了晚上瞬间爆想睡....