水平分区算法，范围分区

什么是水平分区算法？

21世纪以来，大规模分布式系统、云计算和云原生飞速发展，在短短20年间就成为各大企业信息技术基础架构的核心基石。企业迈向分布式的根本原因包括：移动互联网时代，各大企业每天都在和巨大的流量和爆炸性增长的数据打交道；摩尔定律的失效，使得提升单机性能会产生很高的成本，同时网络速度越来越快，意味着并行化程度只增不减；此外，许多应用都要求7×24小时可用，因停电或维护导致的服务不可用，变得越来越让人难以接受；最后，经济全球化也导致了企业必须构建分布在多台计算机甚至多个地理区域的系统。

相较于单体应用或单机系统，分布式应用或分布式系统具有高性能、高可用性、容错性和可扩展性等优点。可见，未来所有的基础架构都会是分布式的。然而分布式系统是一个相当复杂的领域，需要处理各种各样的异常，这些异常不仅难以排查和诊断，而且难以复现，这不是增加测试或采用DevOps就能解决的，有些异常是不可避免的，需要在软件架构中做取舍。因此，想要构建一个健壮的分布式系统，必须先学习相关的基础知识，消化大量信息。尽管学习分布式系统最好的方式是阅读大量的经典论文，但大部分关于分布式系统的资料，要么艰深太晦涩，要么散落在不计其数的学术论文中，对于初学分布式系统的从业者来说，门槛太高，学习曲线太陡峭；再加上相关知识点比较零散、不成体系，让人觉得云山雾罩、望而却步。

而分布式系统中一个很重要的知识点就是——分区。下面详细介绍分区的概念及水平分区算法。

分布式系统带来的主要好处之一是实现了可扩展性，使我们能够存储和处理比单台机器所能容纳的大得多的数据集。实现可扩展性的主要方式之一是对数据进行分区（Partition）。分区是指将一个数据集拆分为多个较小的数据集，同时将存储和处理这些较小数据集的责任分配给分布式系统中的不同节点。数据分区后，我们就可以通过向系统中增加更多节点来增加系统可以存储和处理的数据规模。分区增加了数据的可管理性、可用性和可扩展性。

分区分为垂直分区（Vertical Partitioning）和水平分区（Horizontal Partitioning），这两种分区方式普遍认为起源于关系型数据库，在设计数据库架构时十分常见。

图1展示了垂直分区和水平分区的区别。

垂直分区是对表的列进行拆分，将某些列的整列数据拆分到特定的分区，并放入不同的表中。垂直分区减小了表的宽度，每个分区都包含了其中的列对应的所有行。垂直分区也被称为行拆分（Row Splitting），因为表的每一行都按照其列进行拆分。例如，可以将不经常使用的列或者一个包含了大text类型或BLOB类型的列垂直分区，确保数据完整性的同时提高了访问性能。值得一提的是，列式数据库可以看作已经垂直分区的数据库。

水平分区是对表的行进行拆分，将不同的行放入不同的表中，所有在表中定义的列在每个分区中都能找到，所以表的特性依然得以保留。举个简单的例子：一个包含十年订单记录的表可以水平拆分为十个不同的分区，每个分区包含其中一年的记录（具体的分区方法我们会在后面详细讨论）。

列式数据库（Column-Oriented DBMS或Columnar DBMS）也叫列存数据库，是指以列为单位进行数据存储架构的数据库，主要适用于批量数据处理和即时查询。与之相对应的是行式数据库。一般来说，行式数据库更适用于联机事务处理（OLTP）这类频繁处理事务的场景，列式数据库更适用于联机分析处理（OLAP）这类在海量数据中进行复杂查询的场景。

垂直分区和列相关，而一个表中的列是有限的，这就导致了垂直分区不能超过一定的限度，而水平分区则可以无限拆分。另外，表中数据以行为单位不断增长，而列的变动很少，因此，水平分区更常见。

在分布式系统领域，水平分区常称为分片（Sharding）。需要说明的是，很多图书和文章会纠结分片和分区的具体区别，一种观点认为，分片意味着数据分布在多个节点上，而分区只是将单个存储文件拆分成多个小的文件，并没有跨物理节点存储。由于本书重点讨论的是分布式系统，因此无论是分区还是分片，本书都认为其数据分布在不同物理机器上。

分片在不同系统中有着各种各样的称呼，MongoDB和Elasticsearch中称为shard，HBase中称为region，Bigtable中称为tablet，Cassandra和Riak中称为vnode。

水平分区算法用来计算某个数据应该划分到哪个分区上，不同的分区算法有着不同的特性。本节我们将研究一些经典的分区算法，讨论每种算法的优缺点。

为了方便讨论，我们假设数据都是键值对（Key-Value）的组织形式，通常表示为<Key, Value>。键值对数据结构可以通过关键字（Key）快速找到值（Value），基本上所有编程语言都内置了基于内存的键值对结构，比如C++ STL中的map、Python的dict，以及Java的HashMap，等等。

范围分区

范围分区（Range Partitioning）是指根据指定的关键字将数据集拆分为若干连续的范围，每个范围存储到一个单独的节点上。用来分区的关键字也叫分区键。前面介绍的按年拆分表数据就是一个范围分区的例子，对于2011年到2020年这十年的订单记录，以年为范围，可以划分为10个分区，然后将2011年的订单记录存储到节点N1上，将2012年的订单记录存储到节点N2上，以此类推。

图A中的数据可以按年龄进行范围分区，将数据划分成如图2所示的分区。

如何划分范围可以由管理员设定，或者由存储系统自行划分。通常会选择额外的负载均衡节点或者系统中的一个节点来接收客户端请求，然后根据范围分区算法，确定请求应该重定向（路由）到哪个节点或哪几个节点。

范围分区的主要优点有：

实现起来相对简单。
能够对用来进行范围分区的关键字执行范围查询。
当使用分区键进行范围查询的范围较小且位于同一个节点时，性能良好。
很容易通过修改范围边界增加或减少范围数据，能够简单有效地调整范围（重新分区），以平衡负载。

范围分区的主要缺点有：

无法使用分区键之外的其他关键字进行范围查询。
当查询的范围较大且位于多个节点时，性能较差。
可能产生数据分布不均或请求流量不均的问题，导致某些数据的热点现象，从而某些节点的负载会很高。

例如，当我们将姓氏作为分区键时，某些姓氏的人非常多（比如姓李或者姓王），这会造成数据分布不均。又例如前面的按年拆分订单的例子，虽然数据分布较为均衡，但根据日常生活习惯，最近一年的订单查询流量可能比前几年的查询流量加起来还要多，这就会造成请求流量不均。总的来说，一些节点可能需要存储和处理更多的数据和请求，一般通过继续拆分范围分区来避免热点问题。

使用范围分区的分布式存储系统有Google Bigtable、Apache HBase和PingCAP TiKV。范围分区适合那些需要实现范围查询的系统。

内容摘自《深入理解分布式系统》