[DDIA 逐章精读（六）: 分区（Partition)]
该笔记首要是记录自己学习内容，内容在小册上再加一些自己的了解，有需求直接戳原文链接和视频链接。
原文档链接：第六章：分区 (qtmuniao.com)
视频链接：DDIA 读书逐章共享——第六章（上）：分片办法和次级索引_哔哩哔哩_bilibili
本章问题总结：
分片 / 分区 parttion 与 仿制 replication 的差异是什么？
从一个机器的视点看，既有一些主副本分片，也有一些从副本分片。实践中，也会尽量确保主副本在集群中均匀散布，防止过多的会集到一台机器上。想想为什么？
在实践中，分片会区分为几个步骤？ 答：两个步骤，1. 对数据集进行逻辑区分， 2.将逻辑分片调度到物理节点
常见的分区办法有哪几种？
答：有两种，按键规模 key range 分区 ， 按键哈希Hash（Key）分区。
key range按键规模，长处：快速规模查询 缺陷：数据涣散不均匀，
Hash key按键Hash，长处：数据涣散均匀 缺陷：规模查询盘
两种分区办法差异在于，一个运用运用相关值（Key）分区，一个运用运用无关值（Hash(key)）分区，前者支撑高效规模查询，后者能够均摊负载。但可运用多个字段，组合运用两种办法，运用一个字段进行分区，运用另一个字段在分区内进行排序，兼取两者长处。
次级索引有哪些？ 答：本地索引 和 大局索引
索引树立是同步树立 仍是 异步树立？ 答：本地索引一般是同步更新， 大局索引一般是异步更新， 本地索引树立，在数据查询时，多个分区并发进行索引查询，然后兼并。
均衡战略有哪些？ 答：不要运用hash mod N 进行均衡，因为无法应对机器数量的改变，数据搬家量会十分大。 静态分区 和 动态分区
静态分区 和 动态分区 是什么？ 答：静态分区，总的分区数量是固定的。假如不能固定的话，则后续扩容数据需求进行搬家，一般依据Hash Key 动态分区，一般依据规模key range，开端是1，有上下界，
Hash Key 与 共同性哈希有什么不同？ 答：Hash Key运用的是Key相关性， 计算出逻辑分区和物理分区。节点宕机时，只能手动搬家，而共同性哈希能够做到半主动的增量式搬家。 Redis集群共同性哈希算法 (qq.com)，运用哈希环，共同性哈希当新增节点以及节点宕机时，影响的数据都是很小一部分，缺陷：当节点较少时，会呈现数据不均匀的场景，处理：引进虚拟节点
上一章首要讲仿制，本章转向分片。这是两个相对正交但勾连的两个概念：
- 分片（Partition） ：处理数据集尺度与单机容量、负载不匹配的问题，分片之后能够利用多机容量和负载。
- 仿制（Replication）：体系机器一多，单机毛病概率便增大，为了防止数据丢掉以及服务高可用，需求做多副本。
分片，Partition，有许多别称。通用的有 Shard；详细到实际体系，HBase 中叫 Region，Bigtable 中叫 tablet，等等。实质上是对数据集的一种逻辑区分，后边行文，分片和分区或许混用，且有时为名词，有时为动词。
一般来说，数据体系在散布式体系中会有三级区分：数据集（如 Database、Bucket）——分片（Partition）——数据条目（Row、KV）。一般，每个分片只归于一个数据集，每个数据条目只归于一个分片。单个分片，就像一个小点的数据库。可是，跨分区的操作的，就要杂乱的多。
本章首要会介绍数据集切分的办法，并谈论索引和分片的合作；然后将会谈论分片再平衡（rebalancing），集群节点增删会引起数据再平衡；终究，会探讨数据库怎么将恳求路由到相应的分片并履行。
分片和仿制
分片一般和仿制结合运用。每个分片有多个副本，能够涣散到多机上去（更泛化一点：多个容错阈）；一起，每个机器含有多个分片，但一般不会有一个分片的两个副本放到一个机器上。
假如运用多副本运用主从模型，则分片、副本、机器联系如下：
- 从一个分片的视点看，主副本在一个机器上，从副本们在别的机器上。
- 从一个机器的视点看，既有一些主副本分片，也有一些从副本分片。实践中，也会尽量确保主副本在集群中均匀散布，防止过多的会集到一台机器上。想想为什么？ 仿制操控算法与分区操控算法会存在一些相同点，假如依据leader-based 算法的话，写入都在主节点，会导致主节点压力过大
因为分区办法和仿制战略相对正交，本章会暂时疏忽仿制战略（在上章讲过），专心分析分区办法。
键值对集的分片
为什么专门将键值对呢？因为大部分类型能够转换为键值对。
键值对是数据的一种最通用、泛化的表明，其他种类数据库都能够转化为键值对表明：
- 联系型数据库，primary key → row
- 文档型数据库，document id → document
- 图数据库，vertex id → vertex props, edge id → edge props
因而，接下来首要针对键值对调集的分区办法，则其他数据库在构建存储层时，能够首要转化为 KV 对，然后进行分区。
分片（Partition） 的实质是对数据调集的区分。但在实践中，能够细分为两个步骤：
- 对数据集进行逻辑区分
- 将逻辑分片调度到物理节点
因而，在分片时，有一些基本要求：
- 分片进程中，要确保每个分片的数据量多少尽量均匀，不然会有数据偏斜（skew），甚而形成数据热门。
- 分片后，需求保存路由信息，给一个 KV 条目，能知道去哪个机器上去查；稍差一些，能够知道去哪几个机器上去找；最差的，假如需求去一切机器逐一查询，但功能一般不行承受。
这两条是相互依靠和限制的。比方说，假定分片数目确认，为了分片均匀，每来一条数据，咱们能够等概率随机挑选一个分片；但在查询每个数据条目时，就得去一切机器上都查一遍。
保存一切数据条目路由信息，有三种常用的战略：
- 经过某种固定规矩，比方哈希，算出一个方位。
- 运用内存，保存一切数据条目到机器的映射。
- 结合两种，首要经过规矩算出到逻辑分片的映射，然后经过内存保存逻辑分片到物理节点的映射。
本节首要谈论依据数据条目（Data Item）算出逻辑分区（Partition），常见的有两种办法：按键规模分区，按键哈希分区。
按键规模（Key Range）分区
关于 KV 数据来说，Key 一般会有个界说域，且在界说域内可（按某种维度）排序。则，将该连续的界说域进行切分，保存每个切分的上下界，在给出某个 Key 时，就能经过比较，定位其地点分区。
如，百科全书系列，一般是按照名词的字母序来分册的，每个分册可了解为该系列的一个分区，查阅时，可依据字母排序来首要找到地点分册，再运用分册目录查阅。图书馆图书的索引编号也是类似道理。
因为键并不一定在界说域内均匀散布，因而简略按照界说域等分，并不能将数据等分。因而，需求按照数据的散布，动态调整分区的鸿沟，确保分区间数据大致均匀。这个调整的进程，既能够手动完成 ，也能够主动进行。
按键规模分区好处在于能够进行快速的规模查询（Rang Query） 。如，某个运用是保存传感器数据，并将时刻戳作为键进行分区，则可轻松获取一段时刻内（如某年，某月）的数据。
但坏处在于，数据涣散不均匀，且简略形成热门。或许需求动态的调整的分区鸿沟，以保护分片的相对均匀。
仍以传感器数据存储为例，以时刻戳为 Key，按天的粒度进行分区，一切最新写入都被路由到终究一个分区节点，形成严重的写入歪斜，不能充分利用一切机器的写入带宽。一个处理办法是分级或许混合，运用拼接主键，如运用传感器称号+时刻戳作为主键，则能够将一起写入的多个传感器的数据涣散到多机上去。
按键散列（Hash）分区
为了防止数据歪斜和读写热门，许多数据体系运用散列函数对键进行分区。
因而，挑选散列函数的依据是，使得数据散列尽量均匀：即给定一个 Key，经过散列函数后，以等概率在哈希区间（如[0, 2^32-1)）内产生一个值。即便原 Key 类似，他的散列值也能均匀散布。
而加密并不在考虑之列，因而并不需求多么杂乱的加密算法，如，Cassandra 和 MongoDB 运用 MD5，Voldemort 运用 Fowler-Noll-Vo 函数。
选定哈希函数后，将原 Key 界说域映射到新的散列值阈，而散列值是均匀的，因而能够对散列值阈按给定分区数进行等分。
还有一种常提的哈希办法叫做共同性哈希。其特点是，会考虑逻辑分片和物理拓扑，将数据和物理节点按相同的哈希函数进行哈希，来决议怎么将哈希分片路由到不同机器上。它能够防止在内存中保护逻辑分片到物理节点的映射，而是每次计算出来。即用一套算法一起处理了咱们在开始提出的逻辑分片和物理路由的两个问题。 比较经典的数据体系，Amazon Dynamo就用了这种办法。
假如不运用共同性哈希，咱们需求在元数据节点中，保护逻辑分片到物理节点的映射。则在某些物理节点宕机后，需求调整该映射并手动进行数据搬家，而不能像共同性哈希相同，半主动的增量式搬家。
哈希分片在获取均匀散列才能的一起，也丧失了依据键高效的规模查询才能。如书中说，MongoDB 中挑选依据哈希的分区办法，规模查询就要发送到一切分区节点；Riak 、Couchbase 或 Voldmort 干脆不支撑主键的上的规模查询。
一种折中办法，和上小节相同，运用组合的办法，先散列，再次序。如运用主键进行散列得到分区，在每个分区内运用其他列次序存储。如在交际网络上，首要按 user_id 进行散列分区，再运用 update_time 对用户工作进行次序排序，则能够经过 (user_id, update_timestamp) 高效查询某个用户一段工作的工作。
小结一下，两种分区办法差异在于，一个运用运用相关值（Key）分区，一个运用运用无关值（Hash(key)）分区，前者支撑高效规模查询，后者能够均摊负载。但可运用多个字段，组合运用两种办法，运用一个字段进行分区，运用另一个字段在分区内进行排序，兼取两者长处。
负载偏斜和热门消除
在数据层，能够经过哈希将数据均匀散列，以期将对数据的恳求均摊；但假如在运用层，不同数据条目的负载本就有歪斜，存在对某些键的热门。那么仅在数据层哈希，就不能起到消除热门的效果。
如在交际网络中的大 V，其发布的信息，天然会引起同一个键（假定键是用户 id）许多数据的写入，因为或许会有针对该用户信息的许多谈论和互动。
此刻，就只能在运用层进行热门消除，如能够用拼接主键，对这些大 V 用户主键进行“分身”，即在用户主键开端或许结尾添加一个随机数，两个十进制后缀就能够添加 100 中拆分或许。但这无疑需求运用层做额外的作业，恳求时需求进行拆分，回来时需求进行兼并。
或许之后能开宣布检测热门，主动拆分兼并分区，以消除歪斜和热门。
分片和次级索引
次级索引（secondary index） ，即主键以外的列的索引；因为分区都是依据主键的，在针对有分区的数据树立次级索引时，就会遇到一些困难。
关于次级索引，举个比方，关于某个用户表（id, name, age, company），咱们按用户 id（如身份证）对一切用户数据进行分区。但咱们常常会依据姓名对用户进行查询，为了加速查询，于是需求依据 name 字段，树立次级索引。
在联系型和文档型数据库中，次级索引很常见。在 KV 存储中，为了降低完成杂乱度，一般不支撑。但大部分场景，因为咱们不或许只按单一维度对数据进行检索，因而次级索引很有用。尤其关于查找场景，比方 Solr 和 Elasticsearch，次级索引（在查找范畴称为倒排索引）更是其完成基石。
在有分区的数据中，常见的树立次级索引的办法有：
- 本地索引（local index），书中又称 document-based index
- 大局索引（global index），书中又称 term-based index
注：书中给的 document-based、term-based 两个名词（包括 document 和 term）是从查找中来的。因为查找中都是 term→ document id list 的映射，document-based 是指按 document id 进行分区，每个分区存的索引都是本地的 document ids，而不论其他分区，因而是本地索引，查询时需求发到一切分区逐个查询。term-based 是指按 term 进行分区，则每个倒排索引都是存的大局的 document id list，因而查询的时候只需求去 term 地点分区查询即可。
本地索引
书中举了一个保护轿车信息数据比方：每种轿车信息由 (id, color, make, location) 四元组构成。首要会依据其主键 id 进行分区，其次为了方便查询，需求对轿车颜色（ color ）和制造商（make）字段（文档数据库中称为field，字段；联系型数据库中称为column，列，图数据库中称为property，属性）树立次级索引。
次级索引会对每个数据条目树立一个索引条目，这给数据库的完成带来了一些问题：
- 当数据库已有数据时，树立索引，何时针对存量数据构建索引。
- 当数据库中数据条目产生更改时，怎么保护数据和索引的共同性，尤其是多客户端并发修改时。
本地索引（local index） ，就是对每个数据分区独登时树立次级索引，即，次级索引只针对本分区数据，而不关心其他分区数据。本地索引的长处是保护方便，在更新数据时，只需求在该分区地点机器一起更新索引即可。但缺陷是，查询功率相对较低，一切依据索引的查询恳求，都要发送到一切分区，并将成果兼并，该进程也称为scatter/gather。但即运用多分区并发（而非次序）进行索引查询优化，也依然简略在某些机器上产生长尾恳求（因为机器负载过高或许网络问题，导致改恳求回来特别慢，称为长尾恳求），导致整个恳求进程变慢。
但因为完成简略，本地索引被广泛运用，如 MongoDB，Riak ，Cassandra，Elasticsearch ，SolrCloud 和 VoltDB 都运用本地索引。
大局索引
为了防止查询索引时将恳求发到一切分区，能够树立大局索引，即每个次级索引条目都是针对大局数据。但为了防止索引查询热门，咱们会将索引数据自身也分片，涣散到多个机器上。
当然，与数据自身相同，关于索引进行分区，也可依据 Range 或依据 Hash，相同也是各有优劣（面向扫描仍是均匀散列）。
大局索引能防止索引查询时的 scatter/gather 操作，但保护起来较为杂乱，因为每个数据的刺进，或许会影响多个索引分区（依据该数据不同字段或许会有多个二级索引）。因而，为了防止添加写入推迟，在实践中，大局索引多为异步更新。但由此会带来短暂（有时或许会比较长）的数据和索引不共同。假如想要确保强共同性，需求引进跨分区的散布式事务（完成杂乱度高，且会带来较大的功能损耗），但并不是一切数据库都支撑。
分片均衡
数据库在运转进程中，数据和机器都会产生一些改变：
- 查询吞吐添加，需求添加机器以应对添加的负载。
- 数据集变大，需求添加磁盘和 RAM 来存储添加数据。
- 有机器毛病，需求其他机器来接管毛病机器数据。
一切这些问题都会引起数据分片在节点间的搬家，咱们将之称为：均衡（rebalancing） 。关于 rebalancing 咱们希望：
- 均衡后负载（存储、读写）在节点间均匀散布
- 均衡时不能禁止读写，而且尽量减小影响
- 尽量削减不必要的数据移动，尽量降低网络和磁盘 IO
均衡战略
分区战略会影响均衡战略。比方动态分区、静态分区，对应的均衡战略就不太相同；此外，分区的粒度和数量也会影响均衡战略。
不要运用：hash mod N
在说怎么进行均衡之前，先说下不应该怎样做。
之前提到过，分区包括逻辑分区和物理调度两个阶段，此处说的是将两者合二为一：假定集群有 N 个节点，编号0 ~ N-1，一条键为 key 的数据到来后，经过hash(key) mod N得到一个编号 n，然后将该数据发送到编号为 n 的机器上去。
为什么说这种战略不好呢？因为他不能应对机器数量的改变，假如要增删节点，就会有许多的数据需求产生搬家，不然，就不能确保数据在hash(key) mod N标号的机器上。在大规模集群中，机器节点增删比较频频，这种战略更是不行承受。
静态分区
静态分区，即，逻辑分区阶段的分区数量是固定的，而且最好让分区数量大于（比方高一个数量级）机器节点。比较动态分区战略（比方，答应分区割裂和兼并），固定数量分区更简略完成和保护。
书中没有提，可是估计需求在类似元信息节点，保护逻辑分区到物理节点的映射，并依据此映射信息来发现不均衡，进而进行调度。
在静态分区中，让分区数量远大于机器节点的好处在于：
- 应对将来或许的扩容。加入分区数量等于机器数量，则将来添加机器，仅就单个数据集来说，并不能添加其存储容量和吞吐。
- 调度粒度更细，数据更简略均衡。举个比方，假定只要 20 个分区，然后有 9 个机器，假定每个分区数据量大致相同，则最均衡的情况，也会有两个机器数的数据量比其他机器多 50%；
- 应对集群中的异构性。比方集群中某些节点磁盘容量比其他机器大，则能够多分配几个分区到该机器上。
但当然，也不能太大，因为每个分区信息也是有管理本钱的：比方元信息开支、均衡调度开支等。一般来说，能够取一个你将来集群或许扩展到的最多节点数量作为初始分区数量。
关于数据量会超预期添加的数据集，静态分区战略就会让用户进退两难，现已有许多数据，从头分区代价很大，不从头分区又难以应对数据量的进一步添加。
动态分区
关于按键规模（key range）进行分区的战略来说，因为数据在界说域内并不均匀散布，假如固定分区数量，则天然地难以均衡。因而，按规模分区战略下，都会支撑动态分区。按生命周期来说：
- 开端，数据量很少，只要一个分区。
- 跟着数据量不断添加，单个分区超过一定上界，则按尺寸一分为二，变成两个新的分区。
- 假如某个分区，数据删去过多，少于某个下界，则会和相邻分区兼并（兼并后超过上界怎么办？）。
动态分区好处在于，小数据量运用少数分区，削减开支；大数据量添加分区，以均摊负载。
但一起，小数据量时，假如只要一个分区，会限制写入并发。因而，工程中有些数据库支撑预分区（pre-splitting），如 HBase 和 MongoDB，即答应在空数据库中，配置最少数的初始分区，并确认每个分区的起止键。
别的，散列分区战略也能够支撑动态分区，即，在哈希空间中对相邻数据集进行兼并和割裂。
与节点成份额分区
前文所述，
- 静态均衡的分区数量一开端就固定的，可是单分区尺寸会跟着总数量增大而增大。
- 动态均衡会按着数据量多少进行动态切合，单分区尺寸相对坚持不变，一向于某个设定的上下界。
但他们的分区数量都和集群节点数量没有直接联系。而另一种均衡战略，则是坚持总分区数量和节点数量成正比，也即，坚持每个节点分区数量不变。
假定集群有 m 个节点，每个节点有 n 个分区，在此种均衡战略下，当有新节点加入时，会从 m*n 个分区中随机挑选 n 个分区，将其一分为二，一半由新节点分走，另一半留在原机器上。
随机挑选，很简略产生有歪斜的分割。但假如 n 比较大，如 Cassandra 默许是 256，则新节点会比较简略均摊负载。
- 为什么？ 是因为能够从每个节点选相同数量的分区吗？比方说 n = 256， m = 16，则能够从每个节点选 16 分区吗？
随机挑选分区，要求运用依据哈希的分区战略，这也是最接近原始共同性哈希的界说的办法。（相同存疑。
运维：主动均衡仍是手动均衡
在实践中，均衡是主动进行仍是手动进行需求慎重考虑。
- 主动进行。体系主动检测是否均衡，然后主动决议方案搬家战略以及搬家时刻。
- 手动进行。管理员指定搬家战略和搬家时刻。
数据均衡是一项十分昂贵且易犯错的操作，会给网络带来很大压力，甚至影正常负载。主动均衡诚然能够削减运维，但在实践中，怎么有用鉴别是否真的需求均衡（比方网络抖动了一段时刻、节点宕机又重启、毛病但能修正）是一个很杂乱的工作，假如做犯过错决议方案，就会带来许多无用的数据搬家。
因而，数据均衡一般会半主动的进行，如体系经过负载情况给出搬家战略，由管理员审核没问题后，决议某个时刻段运转（避开正常流量顶峰），Couchbase、Riak 和 Voldemort 便采用了类似做法。
恳求路由
在咱们将分区放到节点上去后，当客户端恳求到来时，咱们怎么决议将恳求路由到哪台机器？这势必要求咱们以某种办法记下：
- 数据条目到逻辑分区的映射。
- 逻辑分区到物理机器的映射。
这在咱们之前现已谈论过。
其次，是在哪里记下这些路由（映射）信息，泛化一下，是一个服务发现（service discovery）问题。归纳来说，由内而外，有几种方案：
- 每个节点都有大局路由表。客户端能够连接集群中恣意一个节点，如该节点恰有该分区，则处理后回来；不然，依据路由信息，将其路由合适节点。
- 由一个专门的路由层来记录。客户端一切恳求都打到路由层，路由层依据分区路由信息，将恳求转发给相关节点。路由层只担任恳求路由，并不处理详细逻辑。
- 让客户端感知分区到节点映射。客户端能够直接依据该映射，向某个节点发送恳求。
不管记在何处，都有一个重要问题：怎么让相关组件（节点自身、路由层、客户端）及时感知（分区到节点）的映射改变，将恳求正确的路由到相关节点？也即，怎么让一切节点就路由信息快速达到共同，业界有许多做法。
依靠外部协调组件。如 Zookeeper、Etcd，他们各自运用某种共识协议坚持高可用，能够保护轻量的路由表，并提供发布订阅接口，在有路由信息更新时，让外部一切节点快速达到共同。
运用内部元数据服务器。如三节点的 Meta 服务器，每个节点都存储一份路由数据，运用某种共识协议达到共同。如 TiDB 的 Placement Driver。
运用某种协议点对点同步。如 Dynamo 、Cassandra 和 Riak 运用流言协议（Gossip Protocol），在集群内一切机器节点间就路由信息进行传达，并终究达到共同。
更简略一些，如 Couchbase 不支撑主动的负载均衡，因而只需求运用一个路由层经过心跳从集群节点收集到一切路由信息即可。
当运用路由层（或许 Proxy 层，一般由多个实例构成），或许客户端将恳求随机发动到某个集群节点时，客户端需求确认一个详细 IP 地址，但这些信息改变相对较少，因而直接运用 DNS 或许反向代理进行轮询即可。
并行查询履行
大部分 NoSQL 存储，所支撑的查询都不太负载，如依据主键的查询、依据次级索引的 scatter/gather 查询。如前所述，都是针对单个键值十分简略的查询路由。
但关于联系型数据库产品，尤其是支撑大规模并行处理（MPP, Massively parallel processing） 数仓，一个查询语句在履行层要杂乱的多，或许会：
- Stage：由多个阶段组成。
- Partition：每个阶段包括多个针对每个分区的并行的子查询方案。
数仓的大规模的快速并行履行是另一个需求专门谈论的话题，因为多用于支撑 BI，因而其优化具有重要意义，本书后边第十章会专门谈论。
