分布式SQL数据库需要自动对表中的数据进行分区，并将其分布在各个节点上。这称为数据分片，可以通过不同的策略来实现，每种策略都有其自身的权衡。在本文中，我们将研究分布式SQL数据库的各种数据分片策略，分析折衷方案，解释YugabyteDB支持哪种策略的原理，以及我们选择哪种作为默认分片策略。
什么是YugabyteDB？它是一个开放源代码的高性能分布式SQL数据库，该数据库基于Google Spanner的可扩展性和容错设计而构建。Yugabyte的SQL API（YSQL）与PostgreSQL兼容。
构建分片数据系统的经验教训
数据分片通过水平分区数据来帮助实现可伸缩性和地理分布。根据特定的分片策略，SQL表被分解为多组行。这些行集的每一个都称为分片。这些分片在无共享架构中分布在多个服务器节点（容器，VM，裸机）上。这样可以确保分片不会因单个节点上可用的计算，存储和网络资源而成为瓶颈。通过跨多个节点复制每个分片来实现高可用性。但是，该应用程序与作为一个逻辑单元的SQL表进行交互，并且与分片的物理位置无关。在本节中，我们将概述这些数据库采用的分片策略的优缺点和实践经验。
您可能还会对以下内容感兴趣： 什么是分布式SQL？
Memcached和Redis –算法分片
分布式缓存不得不在多个节点之间分布数据一段时间。一种常用的技术是算法分片，其中每个键始终映射到同一节点。这是通过计算密钥中的数字哈希值并使用节点总数计算该哈希的模来计算哪个节点拥有密钥的方法来实现的。
图片来源的一部分：分片 如何工作
优点
在算法分片中，客户端无需任何帮助即可确定给定分区的数据库。
缺点
当添加或删除新节点时，几乎所有密钥的所有权都会受到影响，从而导致群集中所有节点之间所有数据的大量重新分配。尽管这不是分布式缓存中的正确性问题（因为缓存未命中会重新填充数据），但是由于整个缓存都需要再次预热，因此它可能会对性能产生巨大影响。
分析
添加和删除节点是分布式数据库的基础，这些操作必须高效。
这使这种类型的分片成为较差的选择，并且在YugabyteDB中未实现。
参考文献
- 通过“ 使用Memcached进行分布式缓存 ”在整个Memcache层中分片数据
- “分片的工作原理”中的算法分片
Cassandra的初始实现–线性哈希分片
Yugabyte团队的各个成员都直接参与了在Facebook上建立Cassandra的早期工作（大约在2007年），远远早于它成为一个开源项目。在Cassandra中设计数据分片时，我们考虑了Google的Bigtable（默认情况下进行范围分片）和Amazon的Dynamo（默认情况下进行一致的哈希分片）。为了实现两全其美，我们选择了线性哈希分片， 在Cassandra中也称为 OrderPreservingPartitioner。
线性散列分片是散列和范围分片之间的混合，通过使用线性散列函数 而不是常规的随机散列函数来计算如何对行进行分片，从而保留了行的排序顺序 。线性散列函数（有时称为保留顺序的散列）是一种散列函数，可在更改输入值的分布间距时保持输入值的相对顺序。这种分片可保留行的排序顺序，同时在更大的键空间中重新分配这些行。这个想法是，可以预分派用于行重新分配的较大键空间，从而使表可以分布在多个节点上。
优点
从理论上讲，这种类型的分片允许通过主键值有效地查询一定范围的行，同时可以将表预先拆分为多个分片。
缺点
实际上，这种分片策略存在问题，因为不可能提前选择好的分片边界。线性哈希分片的主要缺点是数据永远不会在分区之间均匀分布，因此会导致热点。
分析
尽管从理论上讲很有用，但它们只是可以有效利用此分片策略的狭窄用例集。对于Cassandra，默认分片策略已从线性哈希分片更改为一致分片，以提高可伸缩性和性能。
不建议这样做，因为这个限制以及因为全局排序所有分区都会产生热点：某些分区靠在一起会比其他分区获得更多的活动，而承载这些分区的节点将相对于其他分区过载。您可以尝试通过主动负载平衡来缓解这种情况，但这在实践中效果不佳；等到您可以调整令牌分配，以使过载节点上的热点分区减少时，您的工作负载通常就会发生足够的变化，以至于热点现在位于其他位置。请记住，保留全局顺序意味着您不能只是选择并选择要重新定位的热分区，而必须重新定位连续范围。
因此，这是一个糟糕的分片策略，并且在YugabyteDB中未实现。
DynamoDB和Cassandra –一致的哈希分片
使用一致的哈希分片，使用分区算法将数据均匀且随机地分布在各个分片上。表的每一行都放置在一个分片中，该分片是通过对该行的分区列值进行计算得出的一致哈希值来确定的。如下图所示。
优点
这种分片策略非常适合可大规模扩展的工作负载，因为它可以在群集中的所有节点之间平均分配数据，同时又易于将节点添加到群集中。回想一下，算法哈希分片在跨节点分布数据方面也非常有效，但分布策略取决于节点数。使用一致的哈希分片，分片的数目比节点数多得多，并且维护了一个显式的映射表，该表跟踪分片对节点的分配。添加新节点时，可以将现有节点中的一部分子集有效地移入新节点中，而无需重新分配大量数据。
缺点
执行范围查询可能效率不高。范围查询的示例是查找大于下限或小于上限的行（与点查找相反）。
分析
作为具有构建和运行多个数据库系统经验的团队，我们发现哈希分片是需要扩展的工作负载的理想选择。例如，毫无例外，我们在Apache HBase上的Facebook上运行的所有可大规模扩展的服务都在应用程序层和预拆分表上实现了哈希分片。没有哈希分片，这些应用程序将遇到严重的瓶颈。
我们决定YugabyteDB应该支持一致的哈希分片。
Google Spanner和HBase –范围分片
Apache HBase是一个以Google BigTable为模型的可大规模扩展的分布式NoSQL数据库。这是Yugabyte团队许多成员熟悉的另一个数据库，因为他们多年前已在Facebook内部大规模构建和运行HBase。它是支持多种Internet规模服务的数据库，例如Facebook Messenger（用户到用户消息传递平台）和Operational Data Store（可为所有Facebook基础结构提供指标和警报）。HBase和Google Spanner都支持范围分片。
范围分片涉及将表的行划分为多个连续的范围，这些范围遵循基于主键列值的表的排序顺序。范围分片的表通常以单个分片开始。在将数据插入表中时，由于无法始终提前知道表中键的分布，因此会将其动态拆分为多个分片。下图显示了范围分片的基本思想。
优点
这种分片类型可以通过主键值有效地查询行范围。这种查询的示例是查找位于下限和上限之间的所有键。
缺点
范围分片实际上在规模上导致了许多问题，其中一些与线性哈希分片相似。
首先，当从单个分片开始时，意味着只有一个节点正在接受所有用户查询。这通常会导致数据库“变暖”问题，其中所有查询都由单个节点处理，即使集群中有多个节点也是如此。在使用群集中的所有节点之前，用户将必须等待足够的拆分，并且这些碎片必须重新分配。这在生产工作负载中可能是一个大问题。在某些情况下，可以通过将表预先拆分为多个分片来提前知道键的分配的情况，这可以缓解这种情况，但是实际上这很难。
其次，在所有分片上全局排序的密钥通常会产生热点：某些分片将比其他分片获得更多的活动，并且托管那些分片的节点相对于其他分片而言会过载。尽管可以通过主动负载平衡在某种程度上减轻这些负担，但实际上这并不总是很有效，因为当在各个节点之间重新分配热碎片时，工作负载可能会发生变化并引入新的热点。
分析
范围分片对于有效支持基于小于，大于或介于某些用户指定值之间的列值查找行范围的查询至关重要。对此类查询进行非范围分片的方案可能会导致性能过高，因为它可能必须执行全表扫描。这使得该策略必不可少。
在不需要排序主键的情况下选择范围分片时，应用程序将遇到可伸缩性瓶颈，如上面的缺点部分所述。通常建议的解决方法是在范围分片的基础上实现哈希分片。但是实际上，用户并不总是记得在范围分片的基础上实现哈希分片。
鉴于范围分片在某些情况下很有用，我们决定YugabyteDB应该支持范围分片。
放在一起
哈希分片可从一开始就平均利用多个节点，并且在防止热点方面非常有效。范围分片非常适合执行范围搜索（例如，两个值之间的键范围），并且只是分布式数据库中许多可能的访问模式之一。下表总结了范围和哈希分片之间的关键权衡。
