Wetts's blog

Stay Hungry, Stay Foolish.

0%

发表于 分类于

su 是用户切换的命令。```

  • su [user]：切换到其他用户，但是不切换环境变量
  • su - [user]：则是完整的切换到新的用户环境

发表于 分类于

参考：

Ubuntu 16.04 发布时，一个引人注目的新特性便是 apt 命令的引入。其实早在 2014 年，apt 命令就已经发布了第一个稳定版，只是直到 2016 年的 Ubuntu 16.04 系统发布时才开始引人关注。

随着 apt install package 命令的使用频率和普遍性逐步超过 apt-get install package，越来越多的其它 Linux 发行版也开始遵循 Ubuntu 的脚步，开始鼓励用户使用 apt 而不是 apt-get。

那么，apt-get 与 apt 命令之间到底有什么区别呢？如果它们有类似的命令结构，为什么还需要新的 apt 命令呢？是否 apt 真的比 apt-get 更好？普通用户应该使用新的 apt 命令还是坚持旧有习惯继续使用 apt-get 呢？

apt 与 apt-get

在开始对比 apt 与 apt-get 命令的区别之前，我们先来看看这两个命令的背景，以及它们要试图达到的目的。

Debian 作为 Ubuntu、Linux Mint 和 elementary OS 等 Linux 操作系统的母板，其具有强健的「包管理」系统，它的每个组件和应用程序都内置在系统中安装的软件包中。Debian 使用一套名为 Advanced Packaging Tool（APT）的工具来管理这种包系统，不过请不要把它与 apt 命令混淆，它们之间是其实不是同一个东西。

在基于 Debian 的 Linux 发行版中，有各种工具可以与 APT 进行交互，以方便用户安装、删除和管理的软件包。apt-get 便是其中一款广受欢迎的命令行工具，另外一款较为流行的是 Aptitude 这一命令行与 GUI 兼顾的小工具。

如果你已阅读过我们的 apt-get 命令指南，可能已经遇到过许多类似的命令，如 apt-cache、apt-config 等。如你所见，这些命令都比较低级又包含众多功能，普通的 Linux 用户也许永远都不会使用到。换种说法来说，就是最常用的 Linux 包管理命令都被分散在了 apt-get、apt-cache 和 apt-config 这三条命令当中。

apt 命令的引入就是为了解决命令过于分散的问题，它包括了 apt-get 命令出现以来使用最广泛的功能选项，以及 apt-cache 和 apt-config 命令中很少用到的功能。

在使用 apt 命令时，用户不必再由 apt-get 转到 apt-cache 或 apt-config，而且 apt 更加结构化，并为用户提供了管理软件包所需的必要选项。

简单来说就是：apt = apt-get、apt-cache 和 apt-config 中最常用命令选项的集合。

apt 与 apt-get 之间的区别

通过 apt 命令，用户可以在同一地方集中得到所有必要的工具，apt 的主要目的是提供一种以「让终端用户满意」的方式来处理 Linux 软件包的有效方式。

apt 具有更精减但足够的命令选项，而且参数选项的组织方式更为有效。除此之外，它默认启用的几个特性对最终用户也非常有帮助。例如，可以在使用 apt 命令安装或删除程序时看到进度条。

apt 还会在更新存储库数据库时提示用户可升级的软件包个数。

如果你使用 apt 的其它命令选项，也可以实现与使用 apt-get 时相同的操作。

apt 和 apt-get 命令之间的区别

虽然 apt 与 apt-get 有一些类似的命令选项，但它并不能完全向下兼容 apt-get 命令。也就是说，可以用 apt 替换部分 apt-get 系列命令，但不是全部。

apt 命令 取代的命令 命令的功能
apt install apt-get install 安装软件包
apt remove apt-get remove 移除软件包
apt purge apt-get purge 移除软件包及配置文件
apt update apt-get update 刷新存储库索引
apt upgrade apt-get upgrade 升级所有可升级的软件包
apt autoremove apt-get autoremove 自动删除不需要的包
apt full-upgrade apt-get dist-upgrade 在升级软件包时自动处理依赖关系
apt search apt-cache search 搜索应用程序
apt show apt-cache show 显示装细节

当然，apt 还有一些自己的命令：

新的apt命令 命令的功能
apt list 列出包含条件的包（已安装，可升级等）
apt edit-sources 编辑源列表

需要大家注意的是：apt 命令也还在不断发展，因此，你可能会在将来的版本中看到新的选项。

发表于 分类于

概述

简介

HBase 利用 Hadoop MapReduce 来处理 HBase 中的海量数据，实现高性能计算；利用 Zookeeper 作为协同服务，实现稳定服务和失败恢复；使用 HDFS 作为高可靠的底层存储，利用廉价集群提供海量数据存储能力。当然，HBase 也可以直接使用本地文件系统而不用 HDFS 作为底层数据存储方式，不过，为了提高数据可靠性和系统的健壮性，发挥 HBase 处理大数据量等功能，一般都使用 HDFS 作为 HBase 的底层数据存储方式。此外，为了方便在 HBase 上进行数据处理，Sqoop 为 HBase 提供了高效、便捷的 RDBMS 数据导人功能，Pig 和 Hive 为 HBase 提供了高层语言支持。HBase 是 BigTable 的开源实现。

HBase与其他部分的关系

HBase与BigTable

HBase 数据模型

数据模型概述

HBase 是一个稀疏、多维度、排序的映射表，这张表的索引是行键、列族、列限定符和时间戳。每个值是一个未经解释的字符串，没有数据类型。用户在表中存储数据，每一行都有一个可排序的行键和任意多的列。表在水平方向由一个或者多个列族组成，同一个列族中可以包含任意多个列，同一个列族里面的数据存储在一起。列族支持动态扩展，可以很轻松地添加-个列族或列，无需预先定义列的数量以及类型，所有列均以字符串形式存储，用户需要自行进行数据类型转换。由于同-张表里面的每一行数据都可以有截然不同的列，因此对于整个映射表的每行数据而言，有些列的值就是空的，所以说 HBase 是稀疏的。

在 HBase 中执行更新操作时，并不会删除数据旧的版本，而是生成一个新的版本，旧有的版本仍然保留，HBase 可以对允许保留的版本的数量进行设置。客户端可以选择获取距离某个时间最近的版本，或者一次获取所有版本。如果在查询的时候不提供时间戳，那么会返回距离现在最近的那一个版本的数据，因为在存储的时候，数据会按照时间戳排序。

HBase 提供了两种数据版本回收方式：

  • 一是保存数据的最后 n 个版本；
  • 二是保存最近一段时间内的版本(如最近7天)。

数据模型的相关概念

HBase数据模型实例

表

HBase 采用表来组织数据，表由行和列组成，列划分为若千个列族。

行

每个 HBase 表都由若干行组成，每个行由行键（Row Key）来标识。访问表中的行只有 3 种方式：

  1. 通过单个行键访问；
  2. 通过一个行键的区间来访问；
  3. 全表扫描。

行键可以是任意字符串（最大长度是 64 KB，实际应用中长度一般为 10~100 字节），在 HBase 内部，行键保存为字节数组。存储时，数据按照行键的字典序排序存储。在设计行键时，要充分考虑这个特性，将经常一起读取的行存储在一起。

列族

一个 HBase 表被分组成许多“列族”的集合，它是基本的访问控制单元。列族需要在表创建时就定义好，数量不能太多（HBase 的一些缺陷使得列族数量只限于几十个），而且不要频繁修改。

存储在一个列族当中的所有数据，通常都属于同一种数据类型，这通常意味着具有更高的压缩率。表中的每个列都归属于某个列族，数据可以被存放到列族的某个列下面，但是在把数据存放到这个列族的某个列下面之前，必须首先创建这个列族。在创建完成一个列族以后，就可以使用同一个列族当中的列。列名都以列族作为前缀。例如，courses:history 和 courses:math 这两个列都属于 courses 这个列族。

在 HBase 中，访问控制、磁盘和内存的使用统计都是在列族层面进行的。实际应用中，我们可以借助列族上的控制权限帮助实现特定的目的。比如，我们可以允许一些应用能够向表中添加新的数据，而另一些应用则只允许浏览数据。HBase 列族还可以被配置成支持不同类型的访问模式。比如，一个列族也可以被设置成放入内存当中，以消耗内存为代价，从而换取更好的响应性能。

列限定符

列族里的数据通过列限定符（或列）来定位。列限定符不用事先定义，也不需要在不同行之间保持一致。列限定符没有数据类型，总被视为字节数组 byte[]。

单元格

在 HBase 表中，通过行、列族和列限定符确定一个“单元格”(Cell)。单元格中存储的数据没有数据类型，总被视为字节数组 bytel]。每个单元格中可以保存一个数据的多个版本，每个版本对应一个不同的时间戳。

时间戳

每个单元格都保存着同一份数据的多个版本，这些版本采用时间戳进行索引。每次对一个单元格执行操作（新建、修改、删除）时，HBase 都会隐式地自动生成并存储一个时间戳。时间戳一般是 64 位整型，可以由用户自己赋值（自己生成唯一时间戳可以避免应用程序中出现数据版本冲突），也可以由 HBase 在数据写入时自动赋值。一个单元格的不同版本是根据时间戳降序的顺序进行存储的，这样，最新的版本可以被最先读取。

数据坐标

HBase 使用坐标来定位表中的数据，也就是说，每个值都是通过坐标来访问的。对于我们熟悉的关系数据库而言，数据定位可以理解为采用“二维坐标”，即根据行和列就可以确定表中一个具体的值。但是，HBase中需要根据行键、列族、列限定符和时间戳来确定一个单元格，因此可以视为一个“四维坐标”，即 [行键，列族，列限定符，时间戳]。

概念视图

在 HBase 的概念视图中，一个表可以视为一个稀疏、多维的映射关系。

HBase数据的概念视图

上图行键是一个反向 URL（即 com.cnn.www），之所以这样存放，是因为 HBase 是按照行键的字典序来排序存储数据的，采用反向 URL 的方式，可以让来自同一个网站的数据内容都保存在相邻的位置，在按照行键的值进行水平分区时，就可以尽量把来自同一个网站的数据划分到同一个分区（Region）中。

物理视图

从概念视图层面，HBase 中的每个表是由许多行组成的，但是在物理存储层面，它是采用了基于列的存储方式，而不是像传统关系数据库那样采用基于行的存储方式，这也是 HBase 和传统关系数据库的重要区别。

HBase数据的物理视图

面向列的存储

行式数据库使用 NSM（N-ary Storage Model）存储模型，一个元组（或行）会被连续地存储在磁盘页中，也就是说，数据是一行一行被存储的，第一行写人磁盘页后，再继续写人第二行，依此类推。在从磁盘中读取数据时，需要从磁盘中顺序扫描每个元组的完整内容，然后从每个元组中筛选出查询所需要的属性。如果每个元组只有少量属性的值对于查询是有用的，那么 NSM 就会浪费许多磁盘空间和内存带宽。

列式数据库采用 DSM（Decomposition Storage Model）存储模型，它是在 1985 年提出来的，目的是最小化无用的 I/O。DSM 采用了不同于 NSM 的思路，对于采用 DSM 存储模型的关系数据库而言，DSM 会对关系进行垂直分解，并为每个属性分配一个子关系。因此，一个具有 n 个属性的关系会被分解成 n 个子关系，每个子关系单独存储，每个子关系只有当其相应的属性被请求时才会被访问。也就是说，DSM 是以关系数据库中的属性或列为单位进行存储，关系中多个元组的同一属性值（或同一列值）会被存储在一起，而一个元组中不同属性值则通常会被分别存放于不同的磁盘页中。

行式存储结构和列式存储结构

  • 行式数据库主要适合于小批量的数据处理，如联机事务型数据处理，我们平时熟悉的 Oracle 和 MySQL 等关系数据库都属于行式数据库。
  • 列式数据库主要适合于批量数据处理和即席查询（Ad-Hoc Query）。

列式存储的优点是：

  • 可以降低 IO 开销，支持大量并发用户查询，其数据处理速度比传统方法快 100 倍，因为仅需要处理可以回答这些查询的列，而不是分类整理与特定查询无关的数据行；
  • 具有较高的数据压缩比，较传统的行式数据库更加有效，甚至能达到 5 倍的效果。

列式数据库主要用于数据挖掘、决策支持和地理信息系统等查询密集型系统中，因为一次查询就可以得出结果，而不必每次都要遍历所有的数据库。所以，列式数据库大多都是应用在人口统计调查、医疗分析等行业中，这种行业需要处理大量的数据统计分析，假如采用行式数据库，势必导致消耗的时间会无限放大。

DSM 存储模型的缺陷是：

  • 执行连接操作时需要昂贵的元组重构代价，因为一个元组的不同属性被分散到不同磁盘页中存储，当需要一个完整的元组时，就要从多个磁盘页中读取相应字段的值来重新组合得到原来的一个元组。
  • 对于联机事务型数据处理而言，需要频繁对一些元组进行修改（如百货商场售出一件衣服后要立即修改库存数据），如果采用DSM存储模型，就会带来高昂的开销。

HBase 的实现原理

HBase 的功能组件

HBase 的实现包括3个主要的功能组件：

  • 库函数，链接到每个客户端；
  • 一个 Master 主服务器；
  • 许多个 Region 服务器。
  • Region 服务器负责存储和维护分配给自己的 Region，处理来自客户端的读写请求。
  • 主服务器 Master 负责管理和维护 HBase 表的分区信息，比如，一个表被分成了哪些 Region，每个 Region 被存放在哪台 Region 服务器上，同时也负责维护 Region 服务器列表。

因此，如果 Master 主服务器死机，那么整个系统都会无效。Master 会实时监测集群中的 Region 服务器，把特定的 Region 分配到可用的 Region 服务器上，并确保整个集群内部不同 Region 服务器之间的负载均衡，当某个 Region 服务器因出现故障而失效时，Master 会把该故障服务器上存储的 Region 重新分配给其他可用的 Region 服务器。除此以外，Master 还处理模式变化，如表和列族的创建。同客户端并不是直接从 Master 主服务器上读取数据，而是在获得 Region 的存储位置信息后，直接从 Region 服务器上读取数据。尤其需要指出的是，HBase 客户端并不依赖于 Master 而是借助于 Zookeeper 来获得 Region 的位置信息的，所以大多数客户端从来不和主服务器 Master 通信，这种设计方式使 Master 的负载很小。

表和 Region

在一个 HBase 中，存储了许多表。对于每个 HBase 表而言，表中的行是根据行键的值的字典序进行维护的，表中包含的行的数量可能非常庞大，无法存储在一台机器上，需要分布存储到多台机器上。因此，需要根据行键的值对表中的行进行分区，每个行区间构成一个分区，被称为”Region”，包含了位于某个值域区间内的所有数据，它是负载均衡和数据分发的基本单位，这些 Region 会被分发到不同的 Region 服务器上。

一个HBase表被划分成多个Region

初始时，每个表只包含一个Region，随着数据的不断插入，Region 会持续增大，当一个 Region 中包含的行数量达到一个阈值时，就会被自动等分成两个新的 Region。随着表中行的数量继续增加，就会分裂出越来越多的 Region。

一个Region分裂成多个新的Region

每个 Region 的默认大小是 100MB 到 200MB，是 HBase 中负载均衡和数据分发的基本单位。Master 主服务器会把不同的 Region 分配到不同的 Region 服务器上，但是同一个 Region 是不会被拆分到多个 Region 服务器上的。每个 Region 服务器负责管理-个 Region 集合，通常在每个 Region 服务器上会放置 10~1000 个 Region。

不同Region分布在不同Region服务器上

Region 的定位

每个 Region 都有一个 RegionID 来标识它的唯一性，这样，一个 Region 标识符就可以表示成“表名 + 开始主键 + RegionID”。

有了 Region 标识符，就可以唯一标识每个 Region。为了定位每个 Region 所在的位置，就可以构建一张映射表，映射表的每个条目（或每行）包含两项内容，一个是 Region 标识符，另一个是 Region 服务器标识，这个条目就表示 Region 和 Region 服务器之间的对应关系，从而就可以知道某个 Region 被保存在哪个 Region 服务器中。这个映射表包含了关于 Region 的元数据（即 Region 和 Region 服务器之间的对应关系），因此也被称为“元数据表”，又名“.META.表”。

当一个 HBase 表中的 Region 数量非常庞大的时候，.META.表的条目就会非常多，一个服务器保存不下，也需要分区存储到不同的服务器上，因此.META.表也会被分裂成多个 Region，这时，为了定位这些 Region，就需要再构建一个新的映射表，记录所有元数据的具体位置，这个新的映射表就是“根数据表”，又名“-ROOT-表”。-ROOT-表是不能被分割的，永远只存在一个 Region 用于存放-ROOT-表，因此这个用来存放-ROOT-表的唯一一个 Region, 它的名字是在程序中被写死的，Master 主服务器永远知道它的位置。

综上所述，HBase 使用类似 B+树的三层结构来保存 Region 位置信息。

HBase的三层结构

HBase三层结构的名称和作用

为了加快访问速度，.META.表的全部 Region 都会被保存在内存中。假设.META.表的每行（一个映射条目）在内存中大约占用 1KB，并且每个 Region 限制为 128MB，那么，上面的三层结构可以保存的用户数据表的 Region 数目的计算方法是：(-ROOT-表能够寻址的.META.表的 Region 个数) x (每个.META.表的 Region 可以寻址的用户数据表的 Region 个数)。一个-ROOT-表最多只能有一个 Region，也就是最多只能有 128MB，按照每行（一个映射条目）占用 1KB 内存计算，128MB 空间可以容纳 128MB/1KB=2^17 行，也就是说，一个-ROOT表可以寻址 2^17 个.META.表的 Region。同理，每个.META.表的 Region 可以寻址的用户数据表的 Region 个数是 128MB/1KB=2^17。最终，三层结构可以保存的 Region 数目是 (128MB/1KB) * (128MB/1KB) = 234 个 Region。可以看出，这种数量已经足够可以满足实际应用中的用户数据存储需求。

客户端访问用户数据之前，需要首先访问 Zookeeper，获取-ROOT-表的位置信息，然后访问-ROOT-表，获得.META.表的信息，接着访问.META.表，找到所需的 Region 具体位于哪个 Region 服务器，最后才会到该 Region 服务器读取数据。该过程需要多次网络操作，为了加速寻址过程，一般会在客户端做缓存，把查询过的位置信息缓存起来，这样以后访问相同的数据时，就可以直接从客户端缓存中获取 Region 的位置信息，而不需要每次都经历一个“三级寻址”过程。需要注意的是，随着 HBase 中表的不断更新，Region 的位置信息可能会发生变化，但是客户端缓存并不会自己检测 Region 位置信息是否失效，而是在需要访问数据时，从缓存中获取 Region 位置信息却发现不存在的时候，才会判断出缓存失效，这时，就需要再次经历上述的“三级寻址”过程，重新获取最新的 Region 位置信息去访问数据，并用最新的 Region 位置信息替换缓存中失效的信息。

当一个客户端从 Zookeeper 服务器上拿到-ROOT-表的地址以后，就可以通过“三级寻址”找到用户数据表所在的 Region 服务器，并直接访问该 Region 服务器获得数据，没有必要再连接主服务器 Master。因此，主服务器的负载相对就小了很多。

HBase 运行机制

HBase 系统架构

HBase 的系统架构包括客户端、Zookeeper 服务器、Master 主服务器、Region 服务器。需要说明的是，HBase 一般采用 HDFS 作为底层数据存储。

HBase的系统架构

客户端

客户端包含访问 HBase 的接口，同时在缓存中维护着已经访问过的 Region 位置信息，用来加快后续数据访问过程。HBase 客户端使用 HBase 的 RPC 机制与 Master 和 Region 服务器进行通信。其中，对于管理类操作，客户端与 Master 进行 RPC；而对于数据读写类操作，客户端则会与 Region 服务器进行 RPC。

Zookeeper 服务器

Zookeeper 服务器并非一台单一的机器，可能是由多台机器构成的集群来提供稳定可靠的协同服务。Zookeeper 能够很容易地实现集群管理的功能，如果有多台服务器组成一个服务器集群，那么必须有一个“总管”知道当前集群中每台机器的服务状态，一旦某台机器不能提供服务，集群中其他机器必须知道，从而做出调整重新分配服务策略。同样，当增加集群的服务能力时，就会增加一台或多台服务器，同样也必须让“总管”知道。

在 HBase 服务器集群中，包含了一个 Master 和多个 Region 服务器，Master 就是这个 HBase 集群的“总管”，它必须知道 Region 服务器的状态。Zookeeper 就可以轻松做到这一点，每个 Region 服务器都需要到 Zookeeper 中进行注册，Zookeeper 会实时监控每个 Region 服务器的状态并通知给 Master，这样，Master 就可以通过 Zookeeper 随时感知到各个 Region 服务器的工作状态。

Zookeeper 不仅能够帮助维护当前的集群中机器的服务状态，而且能够帮助选出一个“总管”，让这个总管来管理集群。HBase 中可以启动多个 Master，但是 Zookeeper 可以帮助选举出一个 Master 作为集群的总管，并保证在任何时刻总有唯一一个 Master 在运行，这就避免了 Master 的“单点失效”问题。

Zookeeper 中保存了-ROOT-表的地址和 Master 的地址，客户端可以通过访问 Zookeeper 获得-ROOT-表的地址，并最终通过“三级寻址”找到所需的数据。Zookeeper 中还存储了 HBase 的模式，包括有哪些表，每个表有哪些列族。

Master

主服务器 Master 主要负责表和 Region 的管理工作。

  • 管理用户对表的增加、删除、修改、查询等操作。
  • 实现不同 Region 服务器之间的负载均衡。
  • 在 Region 分裂或合并后，负责重新调整 Region 的分布。
  • 对发生故障失效的 Region 服务器上的 Region 进行迁移。

客户端访问 HBase 上数据的过程并不需要 Master 的参与，客户端可以访问 Zookeeper 获取-ROOT-表的地址，并最终到达相应的 Region 服务器进行数据读写，Master 仅仅维护着表和 Region 的元数据信息，因此负载很低。

任何时刻，一个 Region 只能分配给一个 Region 服务器。Master 维护了当前可用的 Region 服务器列表，以及当前哪些 Region 分配给了哪些 Region 服务器，哪些 Region 还未被分配。当存在未被分配的 Region，并且有一个 Region 服务器上有可用空间时，Master 就给这个 Region 服务器发送一个请求，把该 Region 分配给它。Region 服务器接受请求并完成数据加载后，就开始负责管理该 Region 对象，并对外提供服务。

Region 服务器

Region 服务器是 HBase 中最核心的模块，负责维护分配给自己的 Region，并响应用户的读写请求。HBase 一般采用 HDFS 作为底层存储文件系统，因此 Region 服务器需要向 HDFS 文件系统中读写数据。采用 HDFS 作为底层存储，可以为 HBase 提供可靠稳定的数据存储，HBase 自身并不具备数据复制和维护数据副本的功能，而HDFS可以为 HBase 提供这些支持。当然，HBase 也可以不采用 HDFS，而是使用其他任何支持 Hadoop 接口的文件系统作为底层存储，比如本地文件系统或云计算环境中的 AmazonS3(Simple Storage Service)。

Region 服务器的工作原理

Region 服务器是 HBase 中最核心的模块，Region 服务器内部管理了一系列 Region 对象和一个 HLog 文件，其中 HLog 是磁盘上面的记录文件，它记录着所有的更新操作。每个 Region 对象又是由多个 Store 组成的，每个 Store 对应了表中的一个列族的存储。每个 Store 又包含了一个 MemStore 和若千个 StoreFile。

  • MemStore 是在内存中的缓存，保存最近更新的数据;
  • StoreFile 是磁盘中的文件，这些文件都是 B 树结构的，方便快速读取。StoreFile 在底层的实现方式是 HDFS 文件系统的 HFile, HFile 的数据块通常采用压缩方式存储，压缩之后可以大大减少网络 I/0 和磁盘 I/O。

Region服务器向HDFS文件系统中读写数据

用户读写数据的过程

当用户写入数据时，会被分配到相应的 Region 服务器去执行操作。用户数据首先被写人到 MemStore 和 HLog 中，当操作写入 HLog 之后，commit() 调用才会将其返回给客户端。

当用户读取数据时，Region 服务器会首先访问 MemStore 缓存，如果数据不在缓存中，才会到磁盘上面的 StoreFile 中去寻找。

缓存的刷新

MemStore 缓存的容量有限，系统会周期性地调用 Region.flushcache() 把 MemStore 缓存里面的内容写到磁盘的 StoreFile 文件中，清空缓存，并在 HLog 文件中写入一个标记，用来表示缓存中
的内容已经被写人 StoreFile 文件中。每次缓存刷新操作都会在磁盘上生成一个新的 StoreFile 文件，因此每个 Store 会包含多个 StoreFile 文件。

每个 Region 服务器都有一个自己的 HLog 文件，在启动的时候，每个 Region 服务器都会检查自己的 HLog 文件，确认最近一次执行缓存刷新操作之后是否发生新的写人操作。如果没有更新，说明所有数据已经被永久保存到磁盘的 StoreFile 文件中；如果发现更新，就先把这些更新写人 MemStore，然后再刷新缓存，写人到磁盘的 StoreFile 文件中。最后，删除旧的 HLog 文件，并开始为用户提供数据访问服务。

StoreFile 的合并

每次 MemStore 缓存的刷新操作都会在磁盘上生成一个新的 StoreFile 文件，这样，系统中的每个 Store 就会存在多个 StoreFile 文件。当需要访问某个 Store 中的某个值时，就必须查找所有这些 StoreFile 文件，非常耗费时间。因此，为了减少查找时间，系统一般会调用 Store.compact() 把多个 StoreFile 文件合并成一个大文件。由于合并操作比较耗费资源，因此只会在 StoreFile 文件的数量达到一个阈值的时候才会触发合并操作。

Store 的工作原理

Region 服务器是 HBase 的核心模块，而 Store 则是 Region 服务器的核心。每个 Store 对应了表中的一个列族的存储。每个 Store 包含一个 MemStore 缓存和若于个 StoreFile 文件。MemStore 是排序的内存缓冲区，当用户写入数据时，系统首先把数据放人 MemStore 缓存，当 MemStore 缓存满时，就会刷新到磁盘中的一个 StoreFile 文件中。随着 StoreFile 文件数量的不断增加，当达到事先设定的数量时，就会触发文件合并操作，多个 StoreFile 文件会被合并成一个大的 StoreFile 文件。当多个 StoreFile 文件合并后，会逐步形成越来越大的 StoreFile 文件，当单个 StoreFile 文件大小超过一定阈值时，就会触发文件分裂操作。同时，当前的 1 个父 Region 会被分裂成 2 个子 Region, 父 Region 会下线，新分裂出的 2 个子 Region 会被 Master 分配到相应的 Region 服务器上。

StoreFile的合并和分裂过程

HLog 的工作原理

在分布式环境下，必须要考虑到系统出错的情形，比如当 Region 服务器发生故障时，MemStore 缓存中的数据（还没有被写人文件）会全部丢失。因此，HBase 采用 HLog 来保证系统发生故障时能够恢复到正确的状态。

HBase 系统为每个 Region 服务器配置了一个 HLog 文件，它是一种预写式日志（Write Ahead Log），也就是说，用户更新数据必须首先被记人日志后才能写人 MemStore 缓存，并且直到 MemStore 缓存内容对应的日志已经被写入磁盘之后，该缓存内容才会被刷新写入磁盘。

Zookeeper 会实时监测每个 Region 服务器的状态，当某个 Region 服务器发生故障时，Zookeeper 会通知 Master。Master 首先会处理该故障 Region 服务器上面遗留的 HLog 文件，由于一个 Region 服务器上面可能会维护着多个 Region 对象，这些 Region 对象共用一个HLog文件，因此这个遗留的 HLog 文件中包含了来自多个 Region 对象的日志记录。系统会根据每条日志记录所属的 Region 对象对 HLog 数据进行拆分，分别放到相应 Region 对象的目录下，然后再将失效的 Region 重新分配到可用的 Region 服务器中，并把与该 Region 对象相关的 HLog 日志记录也发送给相应的 Region 服务器。Region 服务器领取到分配给自己的 Region 对象以及与之相关的 HLog 日志记录以后，会重新做一遍日志记录中的各种操作，把日志记录中的数据写人 MemStore 缓存，然后刷新到磁盘的 StoreFile 文件中，完成数据恢复。

需要特别指出的是，HBase 系统中，每个 Region 服务器只需要维护一个 HLog 文件，所有 Region 对象共用一个 HLog，而不是每个 Region 使用一个 HLog。在这种 Region 对象共用一个 HLog 的方式中，多个 Region 对象的更新操作所发生的日志修改，只需要不断把日志记录追加到单个日志文件中，而不需要同时打开、写入到多个日志文件中，因此可以减少磁盘寻址次数，提高对表的写操作性能。这种方式的缺点是，如果个 Region 服务器发生故障，为了恢复其上的 Region 对象，需要将 Region 服务器上的 HLog 按照其所属的 Region 对象进行拆分，然后分发到其他 Region 服务器上执行恢复操作。

发表于 分类于

HDFS（Hadoop Distributed File System，Hadoop 分布式文件系统）

相关概念

块

在传统的文件系统中，为了提高磁盘读写效率，一般以数据块为单位，而不是以字节为单位。比如，机械式硬盘（磁盘的一种）包含了磁头和转动部件，在读取数据时有一个寻道的过程，通过转动盘片和移动磁头的位置，来找到数据在机械式硬盘中的存储位置，然后才能进行读写。在 I/O 开销中，机械式硬盘的寻址时间是最耗时的部分，一旦找到第条记录，剩下的顺序读取效率是非常高的。因此，以块为单位读写数据，可以把磁盘寻道时间分摊到大量数据中。

HDFS 也同样采用了块的概念，默认的一个块大小是 64 MB。

当客户端需要访问一个文件时，首先从名称节点获得组成这个文件的数据块的位置列表，然后根据位置列表获取实际存储各个数据块的数据节点的位置，最后数据节点根据数据块信息在本地 Linux 文件系统中找到对应的文件，并把数据返回给客户端。

名称节点

名称节点（NameNode）负责管理分布式文件系统的命名空间（Namespace），保存了两个核心的数据结构，即 FsImage 和 EditLog。

  • FsImage：维护文件系统树以及文件树中所有的文件和文件夹的元数据。
  • EditLog：记录了所有针对文件的创建、删除、重命名等操作。

名称节点的数据结构

名称节点记录了每个文件中各个块所在的数据节点的位置信息，但是并不持久化存储这些信息，而是在系统每次启动时扫描所有数据节点重构得到这些信息。

数据节点

数据节点（DataNode）是分布式文件系统HDFS的工作节点，负责数据的存储和读取，会根据客户端或者名称节点的调度来进行数据的存储和检索，并且向名称节点定期发送自己所存储的块的列表。每个数据节点中的数据会被保存在各自节点的本地Linux文件系统中。

第二名称节点

在名称节点运行期间，HDFS会不断发生更新操作，这些更新操作都是直接被写人到 EditLog 文件，因此 EditLog 文件也会逐渐变大。在名称节点运行期间，不断变大的 EditLog 文件通常对于系统性能不会产生显著影响，但是当名称节点重启时，需要将 FsImage 加载到内存中，然后逐条执行 EditLog 中的记录，使得 FsImage 保持最新。可想而知，如果 EditLog 很大，就会导致整个过程变得非常缓慢，使得名称节点在启动过程中长期处于“安全模式”，无法正常对外提供写操作，影响了用户的使用。

为了有效解决 EditLog 逐渐变大带来的问题，HDFS 在设计中采用了第二名称节点（Secondary NameNode）。第二名称节点是 HDFS 架构的一个重要组成部分，具有两个方面的功能：

  • 首先，可以完成 EditLog 与 Fslmage 的合并操作，减小 EditLog 文件大小，缩短名称节点重启时间；
  • 其次，可以作为名称节点的“检查点”，保存名称节点中的元数据信息。

具体如下：

  1. EditLog 与 Fslmage 的合并操作。每隔一段时间，第二名称节点会和名称节点通信，请求其停止使用 EditLog 文件（这里假设这个时刻为 t），暂时将新到达的写操作添加到一个新的文件 EditLog.new 中。然后，第二名称节点把名称节点中的 FsImage 文件和 EditLog 文件拉回到本地，再加载到内存中；对二者执行合并操作，即在内存中逐条执行 EditLog 中的操作，使得 FsImage 保持最新。合并结束后，第二名称节点会把合并后得到的最新的 FsImage 文件发送到名称节点。名称节点收到后，会用最新的 FsImage 文件去替换旧的 FsImage 文件，同时用 EditLog.new 文件去替换 EditLog 文件（这里假设这个时刻为 t2），从而减小了，EditLog 文件的大小。
  2. 作为名称节点的“检查点”。从上面的合并过程可以看出，第二名称节点会定期和名称节点通信，从名称节点获取 FsImage 文件和 EditLog 文件，执行合并操作得到新的 FsImage 文件。从这个角度来讲，第二名称节点相当于为名称节点设置了一个“检查点”，周期性地备份名称节点中的元数据信息，当名称节点发生故障时，就可以用第二名称节点中记录的元数据信息进行系统恢复。但是，在第二名称节点上合并操作得到的新的 FsImage 文件是合并操作发生时（即 t1 时刻）HDFS 记录的元数据信息，并没有包含 t1 时刻和 t2 时刻期间发生的更新操作，如果名称节点在 t1 时刻和 t2 时刻期间发生故障，系统就会丢失部分元数据信息，在 HDFS 的设计中，也并不支持把系统直接切换到第二名称节点，因此从这个角度来讲，第二名称节点只是起到了名称节点的“检查点”作用，并不能起到“热备份”作用。即使有了第二名称节点的存在，当名称节点发生故障时，系统还是有可能会丢失部分元数据信息的。

第二名称节点工作过程示意图

HDFS 体系结构

概述

HDFS的体系结构

HDFS 命名控件管理

HDFS 的命名空间包含目录、文件和块。命名空间管理是指命名空间支持对 HDFS 中的目录、文件和块做类似文件系统的创建、修改、删除等基本操作。在当前的 HDFS 体系结构中，在整个 HDFS 集群中只有一个命名空间，并且只有唯一一个名称节点，该节点负责对这个命名空间进行管理。

HDFS 使用的是传统的分级文件体系，因此用户可以像使用普通文件系统样，创建、删除目录和文件，在目录间转移文件、重命名文件等。但是，HDFS 还没有实现磁盘配额和文件访问权限等功能，也不支持文件的硬连接和软连接（快捷方式）。

通信协议

HDFS 是一个部署在集群上的分布式文件系统，因此很多数据需要通过网络进行传输。所有的 HDFS 通信协议都是构建在 TCP/IP 协议基础之上的。客户端通过一个可配置的端口向名称节点主动发起 TCP 连，并使用客户端协议与名称节点进行交互。名称节点和数据节点之间则使用数据节点协议进行交互。客户端与数据节点的交互是通过 RPC（Remote Procedure Call）来实现的。在设计上，名称节点不会主动发起 RPC，而是响应来自客户端和数据节点的 RPC 请求。

HDFS 体系结构的局限性

HDFS只设置唯一一个名称节点，这样做虽然大大简化了系统设计，但也带来了一些明显的局限性，具体如下。

  1. 命名空间的限制。名称节点是保存在内存中的，因此名称节点能够容纳对象（文件、块）的个数会受到内存空间大小的限制。
  2. 性能的瓶颈。整个分布式文件系统的吞吐量受限于单个名称节点的吞吐量。
  3. 隔离问题。由于集群中只有一个名称节点，只有一个命名空间，因此无法对不同应用程序进行隔离。
  4. 集群的可用性。一旦这个唯一的名称节点发生故障，会导致整个集群变得不可用。

HDFS 的存储原理

数据的冗余存储

HDFS 采用了多副本方式对数据进行冗余存储，通常一个数据块的多个副本会被分布到不同的数据节点上。

HDFS数据块多副本存储

多副本方式具有以下 3 个优点：

  1. 加快数据传输速度。当多个客户端需要同时访问同个文件时，可以让各个客户端分别从不同的数据块副本中读取数据，这就大大加快了数据传输速度。
  2. 容易检查数据错误。HDFS 的数据节点之间通过网络传输数据，采用多个副本可以很容易判断数据传输是否出错。
  3. 保证数据的可靠性。即使某个数据节点出现故障失效，也不会造成数据丢失。

数据存取策略

数据存放

HDFS 默认的冗余复制因子是 3，每一个文件块会被同时保存到 3 个地方，其中，有两份副本放在同一个机架的不同机器上面，第三个副本放在不同机架的机器上面，这样既可以保证机架发生异常时的数据恢复，也可以提高数据读写性能（同机架内带宽高）。一般而言，HDFS 副本的放置策略如下：

  1. 如果是在集群内发起写操作请求，则把第一个副本放置在发起写操作请求的数据节点上，实现就近写入数据。如果是来自集群外部的写操作请求，则从集群内部挑选一台磁盘不太满、CPU 不太忙的数据节点，作为第一个副本的存放地。
  2. 第二个副本会被放置在与第一个副本不同的机架的数据节点上。
  3. 第三个副本会被放置在与第一个副本相同的机架的其他节点上。
  4. 如果还有更多的副本，则继续从集群中随机选择数据节点进行存放。

数据读取

HDFS 提供了一个 API 可以确定一个数据节点所属的机架 ID，客户端也可以调用 API 获取自已所属的机架 ID。当客户端读取数据时，从名称节点获得数据块不同副本的存放位置列表，列表中包含了副本所在的数据节点，可以调用 API 来确定客户端和这些数据节点所属的机架 ID。当发现某个数据块副本对应的机架 ID 和客户端对应的机架 ID 相同时，就优先选择该副本读取数据，如果没有发现，就随机选择-个副本读取数据。

数据复制

HDFS 的数据复制采用了流水线复制的策略，大大提高了数据复制过程的效率。当客户端要往 HDFS 中写入一个文件时，这个文件会首先被写入本地，并被切分成若千个块，每个块的大小是由 HDFS 的设定值来决定的。每个块都向 HDFS 集群中的名称节点发起写请求，名称节点会根据系统中各个数据节点的使用情况，选择一个数据节点列表返回给客户端，然后客户端就把数据首先写入列表中的第一个数据节点，同时把列表传给第一个数据节点，当第一个数据节点接收到 4 KB 数据的时候，写入本地，并且向列表中的第二个数据节点发起连接请求，把自己已经接收到的 4 KB 数据和列表传给第二个数据节点，当第二个数据节点接收到 4 KB 数据的时候，写人本地，并且向列表中的第三个数据节点发起连接请求，依次类推，列表中的多个数据节点形成一条数据复制的流水线。最后，当文件写完的时候，数据复制也同时完成。

数据错误与恢复

名称节点出错

Hadoop 采用两种机制来确保名称节点的安全：

  • 第一，把名称节点上的元数据信息同步存储到其他文件系统（比如远程挂载的网络文件系统 NFS）中；
  • 第二，运行一个第二名称节点，当名称节点宕机以后，可以把第二名称节点作为一种弥补措施，利用第二名称节点中的元数据信息进行系统恢复。

数据节点出错

每个数据节点会定期向名称节点发送“心跳”信息，向名称节点报告自己的状态。当数据节点发生故障，或者网络发生断网时，名称节点就无法收到来自一些数据节点的“心跳”信息，这时这些数据节点就会被标记为“宕机”，节点上面的所有数据都会被标记为“不可读”，名称节点不会再给它们发送任何 IO 请求。

这时，有可能出现一种情形，即由于些数据节点的不可用，会导致一些数据块的副本数量小于冗余因子。名称节点会定期检查这种情况，一旦发现某个数据块的副本数量小于冗余因子，就会启动数据冗余复制，为它生成新的副本。HDFS 与其他分布式文件系统的最大区别就是可以调整冗余数据的位置。

数据出错

网络传输和磁盘错误等因素都会造成数据错误。客户端在读取到数据后，会采用 md5 和 sha1 对数据块进行校验，以确定读取到正确的数据。在文件被创建时，客户端就会对每一个文件块进行信息摘录，并把这些信息写人同一个路径的隐藏文件里面。当客户端读取文件的时候，会先读取该信息文件，然后利用该信息文件对每个读取的数据块进行校验，如果校验出错，客户端就会请求到另外一个数据节点读取该文件块，并且向名称节点报告这个文件块有错误，名称节点会定期检查并且重新复制这个块。

HDFS 的数据读写过程

读数据的过程

HDFS读数据的过程

写数据的过程

HDFS写数据的过程

发表于 分类于

转自：https://blog.csdn.net/zzti_erlie/article/details/103665903

索引的种类

众所周知，索引类似于字典的目录，可以提高查询的效率。

索引从物理上可以分为：聚集索引，非聚集索引

从逻辑上可以分为：普通索引，唯一索引，主键索引，联合索引，全文索引

索引优化策略

不要在索引列上进行运算或使用函数

在列上进行运算或使用函数会使索引失效，从而进行全表扫描。如下面例子在 publish_time，id 列上分别加上索引，publish_time 为 datetime 类型，id 为 int 类型

1
2
-- 全表扫描
select * from article where year(publish_time) < 2019
1
2
-- 走索引
select * from article where publish_time < '2019-01-01'
1
2
-- 全表扫描
select * from article where id + 1 = 5
1
2
-- 走索引
select * from article where id = 4

小心隐式类型转换

假设 id 为 varchar 类型

1
2
-- 全表扫描
select * from article where id = 100
1
2
-- 走索引
select * from article where id = '100'

为什么呢？

1
2
3
select * from article where id = 100
-- 等价于
select * from article where CAST(id AS signed int) = 100

上一条规则说过，不要在索引列上使用函数，隐式类型转换在索引字段上做了函数操作，因此会全表扫描

那么如果 id 是 int，执行下面这个语句是否会导致全表扫描呢？

1
select * from article where id = '100'

答案是会用到索引，我们来分析一下为什么会用到索引

我们先来做一个实验，看一下数据库中字符串和数字做比较的时候，是怎么转换的？

这里有个简单的方法执行select “10” > 9即可

  • 如果结果是1，则是把字符串转成数字，然后进行比较
  • 如果结果是0，则是把数字转成字符串（因为字符串比较是从高位到低位按照asciss码来逐位比较，“1”比“9”小，所以为0），然后进行比较
    1
    2
    3
    4
    5
    6
    mysql> select "10" > 9;
    +----------+
    | "10" > 9 |
    +----------+
    |        1 |
    +----------+

结果为 1 表明当字符串和数字进行比较的时候，是把字符串转成数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
mysql> select "a" = 0;
+---------+
| "a" = 0 |
+---------+
|       1 |
+---------+
1 row in set, 1 warning (0.00 sec)

mysql> select "123abc" = 123;
+----------------+
| "123abc" = 123 |
+----------------+
|              1 |
+----------------+
1 row in set, 1 warning (0.00 sec)

mysql> select "  123abc456" = 123;
+---------------------+
| "  123abc456" = 123 |
+---------------------+
|                   1 |
+---------------------+
1 row in set, 1 warning (0.00 sec)

从实验结果中可以看到，当字符串不含有数字时，会转成 0，否则转成字符串中第一段连续的数字

我们接着来分析上面的例子，为什么一会会用到索引，一会不会用到

1
2
3
4
5
6
7
8
-- id列上有索引，id为varchar，不会走索引
-- id是字符串时，数据库中的id都要转成数字，转成的值不确定（例如id='12ab'会被转成12，不可能从索引上找到12这个值的）
-- 所以得全表扫描
select * from article where id = 100

-- id列上有索引，id为int，会走索引
-- id是int时，'100'会被转成数字100，所以能走索引
select * from article where id = '100'

前导模糊查询不会使用索引

1
2
-- 全表扫描
select * from article where author like '%李'

%李,%李%都会导致全表扫描，非前导模糊查询可以使用索引

1
2
-- 走索引
select * from article where author like '李%'

联合索引最左前缀原则

mysql 会一直向右匹配直到遇到范围查询（>、<、between、like）就停止匹配，比如 a = 1 and b = 2 and c > 3 and d = 4 如果建立（a,b,c,d）顺序的索引，d 是用不到索引的，如果建立（a,b,d,c）的索引则都可以用到，a,b,d 的顺序可以任意调整

  1. 将区分度最高的字段放在最左边

当不需要考虑排序和分组时，将区分度最高的列放在前面通常是很好的。这时候索引的作用只是用于优化 WHERE 条件的查找

如果在 a b 列上建立联合索引，该如何建立，才能使查询效率最高

1
select count(distinct a) / count(*), count(distinct b) / count(*), count(*) from table

执行如下语句，假设 3 个输出依次为 0.0001,0.373,16049，可以看到 b 列的选择性最高，因此将其作为联合索引的第一列，即建立（b, a）的联合索引

  1. 查询时=可以乱序
    如果建立了联合索引（a, b）。例如下面的2个写法是等价的，因为MySQL会将查询的顺序优化成和联合索引的顺序一致

    1
    select * from table where a = '1' and b = '1'
    1
    select * from table where b = '1' and a = '1'

  2. 优化查询，避免出现 filesort

    1
    select * from table where a = ? and b = ? order by c

    最左前缀原则不仅用在查询中，还能用在排序中。MySQL 中，有两种方式生成有序结果集：

  3. 通过有序索引顺序扫描直接返回有序数据

  4. Filesort排序，对返回的数据进行排序

因为索引的结构是 B+树，索引中的数据是按照一定顺序进行排列的，所以在排序查询中如果能利用索引，就能避免额外的排序操作。EXPLAIN 分析查询时，Extra 显示为 Using index。

所有不是通过索引直接返回排序结果的操作都是 Filesort 排序，也就是说进行了额外的排序操作。EXPLAIN 分析查询时，Extra 显示为 Using filesort，当出现 Using filesort 时对性能损耗较大，所以要尽量避免 Using filesort

对于如下sql

1
select * from table where a = ? and b = ? order by c

可以建立联合索引（a, b, c）

如果索引中有范围查找，那么索引有序性无法利用，如

1
select * from table where a > 10 order by b

索引（a，b）无法排序。

放几个例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
-- 使用了a列
where a = 3

-- 使用了a b列
where a = 3 and b = 5

-- 使用了a b c列
where a = 3 and c = 4 and b = 5
 
-- 没有使用索引
where b = 3

-- 使用了a列 
where a = 3 and c = 4

-- 使用了a b列 
where a = 3 and b > 10 and c = 7
 
-- 使用了a b 列
where a = 3 and b like 'xx%' and c = 7

union，or，in 都能命中索引，建议使用in

1
2
3
select * from article where id = 1
union all
select * from article where id = 2
1
select * from article where id in (1 , 2)

新版MySQL的or可以命中索引

1
select * from article where id = 1 or id = 2

效率从高到低为union，in，or。in 和 union 的效率差别可以忽略不计，建议使用 in

负向条件索引不会使用索引，建议用 in

负向条件有：!=、<>、not in、not exists、not like 等

1
2
-- 全表扫描
select * from article where id != 1 and id != 2

知道 id 的所有取值范围，可以改为类似如下形式

1
2
-- 走索引
select * from article where id in (0, 3, 4)

建立覆盖索引

众所周知，表数据是放在一个聚集索引上的，而建立的索引为非聚集索引，非聚集索引的叶子节点存放索引键值，以及该索引键指向的主键。一般查找的过程是从非聚集索引上找到数据的主键，然后根据该主键到聚集索引上查找记录，这个过程称为回表，不清楚的看推荐阅读。

如有下面这个sql

1
select uid, login_time from user where username = ? and passwd = ?

可以建立（username, passwd, login_time）的联合索引，由于 login_time 的值可以直接从索引中拿到，不用再回表查询，提高了查询效率

经常更改，区分度不高的列上不宜加索引

更新会变更 B+ 树，更新频繁的字段建立索引会大大降低数据库性能。

“性别”这种区分度不大的属性，建立索引是没有什么意义的，不能有效过滤数据，性能与全表扫描类似。

一般区分度在80%以上的时候就可以建立索引，区分度可以使用 count(distinct(列名))/count(*) 来计算

明确知道只会返回一条记录，可以加limit 1

当查询确定只有一条记录时，可以加 liimit 1，让 MySQL 停止游标移动，提高查询效率

1
select uid from user where username = ? and passwd = ?

可改为

1
select uid from user where username = ? and passwd = ? limit 1

对文本建立前缀索引

用邮箱登录是一个常见的问题，如果对email整个字段建立索引，会让索引变得大且慢

1
select username from user where email='xxx';

这时我们可以索引开始的部分字符，这样可以大大节约索引空间，从而提高索引效率，但这样也会降低索引的区分度。索引的区分度是指，不重复的索引值和数据表的记录总数的比值。索引的区分度越高则查询效率越高，因为区分度高的索引可以让MySQL在查找时过滤掉更多的行。

因此我们选择足够长的前缀保证较高的区分度，同时又不能太长（以便节约空间）

可以进行如下实验

1
2
3
4
select count(distinct left(email, 5)) / count(*) as col5,
count(distinct left(email, 6)) / count(*) as col6,
count(distinct left(email, 7)) / count(*) as col7
from user

假设输出依次为0.0305，0.0309，0.0310
查询显示当前缀长度达到7的时候，再增加前缀长度，区分度提升的幅度已经很小了，因此创建email(7)的前缀索引即可

需要注意的一点是，前缀索引不能使用覆盖索引

建立索引的列不为NULL

只要列中包含有 NULL 值都将不会被包含在索引中，复合索引中只要有一列含有 NULL值，那么这一列对于此复合索引就是无效的。

因此，在数据库设计时，除非有一个很特别的原因使用 NULL 值，不然尽量不要让字段的默认值为 NULL。

发表于 分类于

FIFO算法

FIFO（First in First out），先进先出。其实在操作系统的设计理念中很多地方都利用到了先进先出的思想，比如作业调度（先来先服务），为什么这个原则在很多地方都会用到呢？因为这个原则简单、且符合人们的惯性思维，具备公平性，并且实现起来简单，直接使用数据结构中的队列即可实现。

在 FIFO Cache 设计中，核心原则就是：如果一个数据最先进入缓存中，则应该最早淘汰掉。也就是说，当缓存满的时候，应当把最先进入缓存的数据给淘汰掉。在 FIFO Cache 中应该支持以下操作;

  • get(key)：如果 Cache 中存在该 key，则返回对应的 value 值，否则，返回 -1；
  • set(key,value)：如果 Cache 中存在该 key，则重置 value 值；如果不存在该 key，则将该 key 插入到到 Cache 中，若 Cache 已满，则淘汰最早进入 Cache 的数据。

举个例子：假如 Cache 大小为 3，访问数据序列为 set(1,1),set(2,2),set(3,3),set(4,4),get(2),set(5,5)

则 Cache 中的数据变化为：

1
2
3
4
5
6
7
8
9
10
11
(1,1)                           set(1,1)

(1,1) (2,2)                     set(2,2)

(1,1) (2,2) (3,3)               set(3,3)

(2,2) (3,3) (4,4)               set(4,4)

(2,2) (3,3) (4,4)               get(2)

(3,3) (4,4) (5,5)               set(5,5)

那么利用什么数据结构来实现呢？

下面提供一种实现思路：

利用一个双向链表保存数据，当来了新的数据之后便添加到链表末尾，如果 Cache 存满数据，则把链表头部数据删除，然后把新的数据添加到链表末尾。在访问数据的时候，如果在 Cache 中存在该数据的话，则返回对应的 value 值；否则返回 -1。如果想提高访问效率，可以利用 hashmap 来保存每个 key 在链表中对应的位置。

LFU 算法

LFU（Least Frequently Used）最近最少使用算法。它是基于“如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小”的思路。

注意 LFU 和 LRU 算法的不同之处，LRU 的淘汰规则是基于访问时间，而 LFU 是基于访问次数的。举个简单的例子：

假设缓存大小为 3，数据访问序列为 set(2,2),set(1,1),get(2),get(1),get(2),set(3,3),set(4,4)，

则在 set(4,4) 时对于 LFU 算法应该淘汰 (3,3)，而 LRU 应该淘汰 (1,1)。

那么 LFU Cache 应该支持的操作为：

  • get(key)：如果 Cache 中存在该 key，则返回对应的 value 值，否则，返回 -1；
  • set(key,value)：如果 Cache 中存在该 key，则重置 value 值；如果不存在该 key，则将该 key 插入到到 Cache 中，若 Cache 已满，则淘汰最少访问的数据。

为了能够淘汰最少使用的数据，因此 LFU 算法最简单的一种设计思路就是 利用一个数组存储数据项，用 hashmap 存储每个数据项在数组中对应的位置，然后为每个数据项设计一个访问频次，当数据项被命中时，访问频次自增，在淘汰的时候淘汰访问频次最少的数据。这样一来的话，在插入数据和访问数据的时候都能达到 $O(1)$ 的时间复杂度，在淘汰数据的时候，通过选择算法得到应该淘汰的数据项在数组中的索引，并将该索引位置的内容替换为新来的数据内容即可，这样的话，淘汰数据的操作时间复杂度为 $O(n)$。

另外还有一种实现思路就是利用小顶堆+hashmap，小顶堆插入、删除操作都能达到 $O(logn)$ 时间复杂度，因此效率相比第一种实现方法更加高效。

LRU

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

1

  1. 新数据插入到链表头部；
  2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
  3. 当链表满的时候，将链表尾部的数据丢弃。

过程如下：

2

  1. 最开始时，内存空间是空的，因此依次进入 A、B、C 是没有问题的
  2. 当加入 D 时，就出现了问题，内存空间不够了，因此根据 LRU 算法，内存空间中 A 待的时间最为久远，选择 A，将其淘汰
  3. 当再次引用 B 时，内存空间中的 B 又处于活跃状态，而 C 则变成了内存空间中，近段时间最久未使用的
  4. 当再次向内存空间加入 E 时，这时内存空间又不足了，选择在内存空间中待的最久的C将其淘汰出内存，这时的内存空间存放的对象就是 E->B->D

发表于 分类于

转自：https://www.jianshu.com/p/8845ddca3b23

前提概要

什么是MVCC?

MVCC，全称Multi-Version Concurrency Control，即多版本并发控制。MVCC是一种并发控制的方法，一般在数据库管理系统中，实现对数据库的并发访问，在编程语言中实现事务内存。

MVCC 在 MySQL InnoDB中的实现主要是为了提高数据库并发性能，用更好的方式去处理读-写冲突，做到即使有读写冲突时，也能做到不加锁，非阻塞并发读

什么是当前读和快照读？

在学习MVCC多版本并发控制之前，我们必须先了解一下，什么是MySQL InnoDB下的当前读和快照读?

当前读

像select lock in share mode(共享锁), select for update ; update, insert ,delete(排他锁)这些操作都是一种当前读，为什么叫当前读？就是它读取的是记录的最新版本，读取时还要保证其他并发事务不能修改当前记录，会对读取的记录进行加锁。

快照读

像不加锁的select操作就是快照读，即不加锁的非阻塞读；快照读的前提是隔离级别不是串行级别，串行级别下的快照读会退化成当前读；之所以出现快照读的情况，是基于提高并发性能的考虑，快照读的实现是基于多版本并发控制，即MVCC,可以认为MVCC是行锁的一个变种，但它在很多情况下，避免了加锁操作，降低了开销；既然是基于多版本，即快照读可能读到的并不一定是数据的最新版本，而有可能是之前的历史版本

说白了MVCC就是为了实现读-写冲突不加锁，而这个读指的就是快照读, 而非当前读，当前读实际上是一种加锁的操作，是悲观锁的实现

当前读，快照读和MVCC的关系

  • 准确的说，MVCC多版本并发控制指的是 “维持一个数据的多个版本，使得读写操作没有冲突” 这么一个概念。仅仅是一个理想概念
  • 而在MySQL中，实现这么一个MVCC理想概念，我们就需要MySQL提供具体的功能去实现它，而快照读就是MySQL为我们实现MVCC理想模型的其中一个具体非阻塞读功能。而相对而言，当前读就是悲观锁的具体功能实现
  • 要说的再细致一些，快照读本身也是一个抽象概念，再深入研究。MVCC模型在MySQL中的具体实现则是由 3个隐式字段，undo日志 ，Read View 等去完成的，具体可以看下面的MVCC实现原理

MVCC能解决什么问题，好处是？

数据库并发场景有三种，分别为：
  • 读-读：不存在任何问题，也不需要并发控制
  • 读-写：有线程安全问题，可能会造成事务隔离性问题，可能遇到脏读，幻读，不可重复读
  • 写-写：有线程安全问题，可能会存在更新丢失问题，比如第一类更新丢失，第二类更新丢失
MVCC带来的好处是？

多版本并发控制（MVCC）是一种用来解决读-写冲突的无锁并发控制，也就是为事务分配单向增长的时间戳，为每个修改保存一个版本，版本与事务时间戳关联，读操作只读该事务开始前的数据库的快照。 所以MVCC可以为数据库解决以下问题

  • 在并发读写数据库时，可以做到在读操作时不用阻塞写操作，写操作也不用阻塞读操作，提高了数据库并发读写的性能
  • 同时还可以解决脏读，幻读，不可重复读等事务隔离问题，但不能解决更新丢失问题
小结一下咯

总之，MVCC就是因为大牛们，不满意只让数据库采用悲观锁这样性能不佳的形式去解决读-写冲突问题，而提出的解决方案，所以在数据库中，因为有了MVCC，所以我们可以形成两个组合：

  • MVCC + 悲观锁
    • MVCC解决读写冲突，悲观锁解决写写冲突
  • MVCC + 乐观锁
    • MVCC解决读写冲突，乐观锁解决写写冲突

这种组合的方式就可以最大程度的提高数据库并发性能，并解决读写冲突，和写写冲突导致的问题

MVCC的实现原理

MVCC的目的就是多版本并发控制，在数据库中的实现，就是为了解决读写冲突，它的实现原理主要是依赖记录中的 3个隐式字段，undo日志 ，Read View 来实现的。所以我们先来看看这个三个point的概念

隐式字段

每行记录除了我们自定义的字段外，还有数据库隐式定义的DB_TRX_ID,DB_ROLL_PTR,DB_ROW_ID等字段

  • DB_TRX_ID
    • 6byte，最近修改(修改/插入)事务ID：记录创建这条记录/最后一次修改该记录的事务ID
  • DB_ROLL_PTR
    • 7byte，回滚指针，指向这条记录的上一个版本（存储于rollback segment里）
  • DB_ROW_ID
    • 6byte，隐含的自增ID（隐藏主键），如果数据表没有主键，InnoDB会自动以DB_ROW_ID产生一个聚簇索引
  • 实际还有一个删除flag隐藏字段, 既记录被更新或删除并不代表真的删除，而是删除flag变了

1

如上图，DB_ROW_ID是数据库默认为该行记录生成的唯一隐式主键，DB_TRX_ID是当前操作该记录的事务ID,而DB_ROLL_PTR是一个回滚指针，用于配合undo日志，指向上一个旧版本

undo日志

undo log主要分为两种：

  • insert undo log
    • 代表事务在insert新记录时产生的undo log, 只在事务回滚时需要，并且在事务提交后可以被立即丢弃
  • update undo log
    • 事务在进行update或delete时产生的undo log; 不仅在事务回滚时需要，在快照读时也需要；所以不能随便删除，只有在快速读或事务回滚不涉及该日志时，对应的日志才会被purge线程统一清除

purge

  • 从前面的分析可以看出，为了实现InnoDB的MVCC机制，更新或者删除操作都只是设置一下老记录的deleted_bit，并不真正将过时的记录删除。
  • 为了节省磁盘空间，InnoDB有专门的purge线程来清理deleted_bit为true的记录。为了不影响MVCC的正常工作，purge线程自己也维护了一个read view（这个read view相当于系统中最老活跃事务的read view）;如果某个记录的deleted_bit为true，并且DB_TRX_ID相对于purge线程的read view可见，那么这条记录一定是可以被安全清除的。

对MVCC有帮助的实质是update undo log ，undo log实际上就是存在rollback segment中旧记录链，它的执行流程如下：

一、 比如一个有个事务插入persion表插入了一条新记录，记录如下，name为Jerry, age为24岁，隐式主键是1，事务ID和回滚指针，我们假设为NULL
2

二、 现在来了一个事务1对该记录的name做出了修改，改为Tom

  • 在事务1修改该行(记录)数据时，数据库会先对该行加排他锁
  • 然后把该行数据拷贝到undo log中，作为旧记录，既在undo log中有当前行的拷贝副本
  • 拷贝完毕后，修改该行name为Tom，并且修改隐藏字段的事务ID为当前事务1的ID, 我们默认从1开始，之后递增，回滚指针指向拷贝到undo log的副本记录，既表示我的上一个版本就是它
  • 事务提交后，释放锁

3

三、 又来了个事务2修改person表的同一个记录，将age修改为30岁

  • 在事务2修改该行数据时，数据库也先为该行加锁
  • 然后把该行数据拷贝到undo log中，作为旧记录，发现该行记录已经有undo log了，那么最新的旧数据作为链表的表头，插在该行记录的undo log最前面
  • 修改该行age为30岁，并且修改隐藏字段的事务ID为当前事务2的ID, 那就是2，回滚指针指向刚刚拷贝到undo log的副本记录
  • 事务提交，释放锁

4

从上面，我们就可以看出，不同事务或者相同事务的对同一记录的修改，会导致该记录的undo log成为一条记录版本线性表，既链表，undo log的链首就是最新的旧记录，链尾就是最早的旧记录（当然就像之前说的该undo log的节点可能是会purge线程清除掉，向图中的第一条insert undo log，其实在事务提交之后可能就被删除丢失了，不过这里为了演示，所以还放在这里）

Read View(读视图)

什么是Read View?

什么是Read View，说白了Read View就是事务进行快照读操作的时候生产的读视图(Read View)，在该事务执行的快照读的那一刻，会生成数据库系统当前的一个快照，记录并维护系统当前活跃事务的ID(当每个事务开启时，都会被分配一个ID, 这个ID是递增的，所以最新的事务，ID值越大)

所以我们知道 Read View主要是用来做可见性判断的, 即当我们某个事务执行快照读的时候，对该记录创建一个Read View读视图，把它比作条件用来判断当前事务能够看到哪个版本的数据，既可能是当前最新的数据，也有可能是该行记录的undo log里面的某个版本的数据。

Read View遵循一个可见性算法，主要是将要被修改的数据的最新记录中的DB_TRX_ID（即当前事务ID）取出来，与系统当前其他活跃事务的ID去对比（由Read View维护），如果DB_TRX_ID跟Read View的属性做了某些比较，不符合可见性，那就通过DB_ROLL_PTR回滚指针去取出Undo Log中的DB_TRX_ID再比较，即遍历链表的DB_TRX_ID（从链首到链尾，即从最近的一次修改查起），直到找到满足特定条件的DB_TRX_ID, 那么这个DB_TRX_ID所在的旧记录就是当前事务能看见的最新老版本

那么这个判断条件是什么呢？

5

如上，它是一段MySQL判断可见性的一段源码，即changes_visible方法（不完全哈，但能看出大致逻辑），该方法展示了我们拿DB_TRX_ID去跟Read View某些属性进行怎么样的比较

在展示之前，我先简化一下Read View，我们可以把Read View简单的理解成有三个全局属性

  • trx_list（名字我随便取的）
    • 一个数值列表，用来维护Read View生成时刻系统正活跃的事务ID
  • up_limit_id
    • 记录trx_list列表中事务ID最小的ID
  • low_limit_id
    • ReadView生成时刻系统尚未分配的下一个事务ID，也就是目前已出现过的事务ID的最大值+1
  1. 首先比较DB_TRX_ID < up_limit_id, 如果小于，则当前事务能看到DB_TRX_ID 所在的记录，如果大于等于进入下一个判断
  2. 接下来判断 DB_TRX_ID 大于等于 low_limit_id , 如果大于等于则代表DB_TRX_ID 所在的记录在Read View生成后才出现的，那对当前事务肯定不可见，如果小于则进入下一个判断
  3. 判断DB_TRX_ID 是否在活跃事务之中，trx_list.contains(DB_TRX_ID)，如果在，则代表我Read View生成时刻，你这个事务还在活跃，还没有Commit，你修改的数据，我当前事务也是看不见的；如果不在，则说明，你这个事务在Read View生成之前就已经Commit了，你修改的结果，我当前事务是能看见的

整体流程

我们在了解了隐式字段，undo log， 以及Read View的概念之后，就可以来看看MVCC实现的整体流程是怎么样了

整体的流程是怎么样的呢？我们可以模拟一下

  • 当事务2对某行数据执行了快照读，数据库为该行数据生成一个Read View读视图，假设当前事务ID为2，此时还有事务1和事务3在活跃中，事务4在事务2快照读前一刻提交更新了，所以Read View记录了系统当前活跃事务1，3的ID，维护在一个列表上，假设我们称为trx_list

6

  • Read View不仅仅会通过一个列表trx_list来维护事务2执行快照读那刻系统正活跃的事务ID，还会有两个属性up_limit_id（记录trx_list列表中事务ID最小的ID），low_limit_id(记录trx_list列表中事务ID最大的ID，也有人说快照读那刻系统尚未分配的下一个事务ID也就是目前已出现过的事务ID的最大值+1，我更倾向于后者；所以在这里例子中up_limit_id就是1，low_limit_id就是4 + 1 = 5，trx_list集合的值是1,3，Read View如下图

7

  • 我们的例子中，只有事务4修改过该行记录，并在事务2执行快照读前，就提交了事务，所以当前该行当前数据的undo log如下图所示；我们的事务2在快照读该行记录的时候，就会拿该行记录的DB_TRX_ID去跟up_limit_id,low_limit_id和活跃事务ID列表(trx_list)进行比较，判断当前事务2能看到该记录的版本是哪个。

8

  • 所以先拿该记录DB_TRX_ID字段记录的事务ID 4去跟Read View的的up_limit_id比较，看4是否小于up_limit_id(1)，所以不符合条件，继续判断 4 是否大于等于 low_limit_id(5)，也不符合条件，最后判断4是否处于trx_list中的活跃事务, 最后发现事务ID为4的事务不在当前活跃事务列表中, 符合可见性条件，所以事务4修改后提交的最新结果对事务2快照读时是可见的，所以事务2能读到的最新数据记录是事务4所提交的版本，而事务4提交的版本也是全局角度上最新的版本

9

也正是Read View生成时机的不同，从而造成RC,RR级别下快照读的结果的不同

MVCC相关问题

RR是如何在RC级的基础上解决不可重复读的？

当前读和快照读在RR级别下的区别：

表1:
10

表2:
11

而在表2这里的顺序中，事务B在事务A提交后的快照读和当前读都是实时的新数据400，这是为什么呢？

  • 这里与上表的唯一区别仅仅是表1的事务B在事务A修改金额前快照读过一次金额数据，而表2的事务B在事务A修改金额前没有进行过快照读。

所以我们知道事务中快照读的结果是非常依赖该事务首次出现快照读的地方，即某个事务中首次出现快照读的地方非常关键，它有决定该事务后续快照读结果的能力

我们这里测试的是更新，同时删除和更新也是一样的，如果事务B的快照读是在事务A操作之后进行的，事务B的快照读也是能读取到最新的数据的

RC,RR级别下的InnoDB快照读有什么不同？

正是Read View生成时机的不同，从而造成RC,RR级别下快照读的结果的不同

  • 在RR级别下的某个事务的对某条记录的第一次快照读会创建一个快照及Read View, 将当前系统活跃的其他事务记录起来，此后在调用快照读的时候，还是使用的是同一个Read View，所以只要当前事务在其他事务提交更新之前使用过快照读，那么之后的快照读使用的都是同一个Read View，所以对之后的修改不可见；
  • 即RR级别下，快照读生成Read View时，Read View会记录此时所有其他活动事务的快照，这些事务的修改对于当前事务都是不可见的。而早于Read View创建的事务所做的修改均是可见
  • 而在RC级别下的，事务中，每次快照读都会新生成一个快照和Read View, 这就是我们在RC级别下的事务中可以看到别的事务提交的更新的原因

总之在RC隔离级别下，是每个快照读都会生成并获取最新的Read View；而在RR隔离级别下，则是同一个事务中的第一个快照读才会创建Read View, 之后的快照读获取的都是同一个Read View。

发表于 分类于

转自：https://zhuanlan.zhihu.com/p/27700617

平衡二叉树

概念

平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构；

特点：

平衡二叉树是采用二分法思维把数据按规则组装成一个树形结构的数据，用这个树形结构的数据减少无关数据的检索，大大的提升了数据检索的速度；平衡二叉树的数据结构组装过程有以下规则：

  1. 非叶子节点只能允许最多两个子节点存在。
  2. 每一个非叶子节点数据分布规则为左边的子节点小当前节点的值，右边的子节点大于当前节点的值(这里值是基于自己的算法规则而定的，比如hash值)；

1

平衡树的层级结构：因为平衡二叉树查询性能和树的层级（h高度）成反比，h值越小查询越快、为了保证树的结构左右两端数据大致平衡降低二叉树的查询难度一般会采用一种算法机制实现节点数据结构的平衡，实现了这种算法的有比如Treap、红黑树，使用平衡二叉树能保证数据的左右两边的节点层级相差不会大于1.，通过这样避免树形结构由于删除增加变成线性链表影响查询效率，保证数据平衡的情况下查找数据的速度近于二分法查找；

2

总结平衡二叉树特点：

  1. 非叶子节点最多拥有两个子节点；
  2. 非叶子节值大于左边子节点、小于右边子节点；
  3. 树的左右两边的层级数相差不会大于1;
  4. 没有值相等重复的节点;

B树(B-tree)

注意:之前有看到有很多文章把B树和B-tree理解成了两种不同类别的树，其实这两个是同一种树;

概念：

B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个），数据库索引技术里大量使用者B树和B+树的数据结构，让我们来看看他有什么特点;

规则：

  1. 排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；
  2. 子节点数：非叶节点的子节点数>1，且<=M ，且M>=2，空树除外（注：M阶代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉）；
  3. 关键字数：枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个（注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2);
  4. 所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子;

最后我们用一个图和一个实际的例子来理解B树（这里为了理解方便我就直接用实际字母的大小来排列C>B>A）
3

B树的查询流程：

如上图我要从上图中找到E字母，查找流程如下

  1. 获取根节点的关键字进行比较，当前根节点关键字为M，E<M（26个字母顺序），所以往找到指向左边的子节点（二分法规则，左小右大，左边放小于当前节点值的子节点、右边放大于当前节点值的子节点）；
  2. 拿到关键字D和G，D<E<G 所以直接找到D和G中间的节点；
  3. 拿到E和F，因为E=E 所以直接返回关键字和指针信息（如果树结构里面没有包含所要查找的节点则返回null）；

B树的插入节点流程

定义一个5阶树（平衡5路查找树;），现在我们要把3、8、31、11、23、29、50、28 这些数字构建出一个5阶树出来;

遵循规则：

  1. 节点拆分规则：当前是要组成一个5路查找树，那么此时m=5,关键字数必须<=5-1（这里关键字数>4就要进行节点拆分）；
  2. 排序规则：满足节点本身比左边节点大，比右边节点小的排序规则;

先插入 3、8、31、11
4

再插入23、29
5

再插入50、28
6

B树节点的删除

规则：

  1. 节点合并规则：当前是要组成一个5路查找树，那么此时m=5,关键字数必须大于等于ceil（5/2）（这里关键字数<2就要进行节点合并）；
  2. 满足节点本身比左边节点大，比右边节点小的排序规则;
  3. 关键字数小于二时先从子节点取，子节点没有符合条件时就向向父节点取，取中间值往父节点放；
    7

特点：

B树相对于平衡二叉树的不同是，每个节点包含的关键字增多了，特别是在B树应用到数据库中的时候，数据库充分利用了磁盘块的原理（磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读取出来）把节点大小限制和充分使用在磁盘快大小范围；把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度;

B+树

概念

B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。为什么说B+树查找的效率要比B树更高、更稳定；我们先看看两者的区别

规则

  1. B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；
  2. B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；
  3. B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。
  4. 非叶子节点的子节点数=关键字数（来源百度百科）（根据各种资料 这里有两种算法的实现方式，另一种为非叶节点的关键字数=子节点数-1（来源维基百科)，虽然他们数据排列结构不一样，但其原理还是一样的Mysql 的B+树是用第一种方式实现）;

8
（百度百科算法结构示意图）

9
（维基百科算法结构示意图）

特点

  1. B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
  2. B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
  3. B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
  4. B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

B*树

规则

B*树是B+树的变种，相对于B+树他们的不同之处如下：

  1. 首先是关键字个数限制问题，B+树初始化的关键字初始化个数是cei(m/2)，b树的初始化个数为（cei(2/3m)）
  2. B+树节点满时就会分裂，而B*树节点满时会检查兄弟节点是否满（因为每个节点都有指向兄弟的指针），如果兄弟节点未满则向兄弟节点转移关键字，如果兄弟节点已满，则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来；

特点

在B+树的基础上因其初始化的容量变大，使得节点空间使用率更高，而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少；

10

总结

  1. 相同思想和策略

    从平衡数据结构-树-二叉树、B树、B+树、B*树总体来看它们的贯彻的思想是相同的，都是采用二分法和数据平衡策略来提升查找数据的速度；

  2. 不同的方式的磁盘空间利用

    不同点是他们一个一个在演变的过程中通过IO从磁盘读取数据的原理进行一步步的演变，每一次演变都是为了让节点的空间更合理的运用起来，从而使树的层级减少达到快速查找数据的目的；

发表于 分类于

转自：https://zhuanlan.zhihu.com/p/85837641

一

分布式ID的特点

全局唯一性

不能出现有重复的ID标识，这是基本要求。

递增性

确保生成ID对于用户或业务是递增的。

高可用性

确保任何时候都能生成正确的ID。

高性能性

在高并发的环境下依然表现良好。

分布式ID的常见解决方案

UUID

Java自带的生成一串唯一随机36位字符串（32个字符串+4个“-”）的算法。它可以保证唯一性，且据说够用N亿年，但是其业务可读性差，无法有序递增。

SnowFlake

今天的主角雪花算法，它是Twitter开源的由64位整数组成分布式ID，性能较高，并且在单机上递增。 具体参考：https://github.com/twitter-archive/snowflake

UidGenerator

UidGenerator是百度开源的分布式ID生成器，其基于雪花算法实现。 具体参考：https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md

Leaf

Leaf是美团开源的分布式ID生成器，能保证全局唯一，趋势递增，但需要依赖关系数据库、Zookeeper等中间件。 具体参考：https://tech.meituan.com/MT_Leaf.html

雪花算法的概要

SnowFlake是Twitter公司采用的一种算法，目的是在分布式系统中产生全局唯一且趋势递增的ID。

1

组成部分（64bit）

  1. 第一位 占用1bit，其值始终是0，没有实际作用。
  2. 时间戳 占用41bit，精确到毫秒，总共可以容纳约69年的时间。
  3. 工作机器id 占用10bit，其中高位5bit是数据中心ID，低位5bit是工作节点ID，做多可以容纳1024个节点。
  4. 序列号 占用12bit，每个节点每毫秒0开始不断累加，最多可以累加到4095，一共可以产生4096个ID。

SnowFlake算法在同一毫秒内最多可以生成多少个全局唯一ID呢：： 同一毫秒的ID数量 = 1024 X 4096 = 4194304

雪花算法的实现

雪花算法的实现主要依赖于数据中心ID和数据节点ID这两个参数，具体实现如下。

JAVA实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
public class SnowflakeIdWorker {
    /**
     * 开始时间截 (2015-01-01)
     */
    private final long twepoch = 1420041600000L;
    /**
     * 机器id所占的位数
     */
    private final long workerIdBits = 5L;
    /**
     * 数据标识id所占的位数
     */
    private final long datacenterIdBits = 5L;
    /**
     * 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数)
     */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
    /**
     * 支持的最大数据标识id，结果是31
     */
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
    /**
     * 序列在id中占的位数
     */
    private final long sequenceBits = 12L;
    /**
     * 机器ID向左移12位
     */
    private final long workerIdShift = sequenceBits;
    /**
     * 数据标识id向左移17位(12+5)
     */
    private final long datacenterIdShift = sequenceBits + workerIdBits;
    /**
     * 时间截向左移22位(5+5+12)
     */
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
    /**
     * 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095)
     */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);
    /**
     * 工作机器ID(0~31)
     */
    private long workerId;
    /**
     * 数据中心ID(0~31)
     */
    private long datacenterId;
    /**
     * 毫秒内序列(0~4095)
     */
    private long sequence = 0L;
    /**
     * 上次生成ID的时间截
     */
    private long lastTimestamp = -1L;
    /**
     * 构造函数
     * @param workerId     工作ID (0~31)
     * @param datacenterId 数据中心ID (0~31)
     */
    public SnowflakeIdWorker(long workerId, long datacenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }
    /**
     * 获得下一个ID (该方法是线程安全的)
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        long timestamp = timeGen();
        // 如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(
                    String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }
        // 如果是同一时间生成的，则进行毫秒内序列
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            // 毫秒内序列溢出
            if (sequence == 0) {
                //阻塞到下一个毫秒,获得新的时间戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        // 时间戳改变，毫秒内序列重置
        else {
            sequence = 0L;
        }
        // 上次生成ID的时间截
        lastTimestamp = timestamp;
        // 移位并通过或运算拼到一起组成64位的ID
        return ((timestamp - twepoch) << timestampLeftShift) //
                | (datacenterId << datacenterIdShift) //
                | (workerId << workerIdShift) //
                | sequence;
    }
    /**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     * @param lastTimestamp 上次生成ID的时间截
     * @return 当前时间戳
     */
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }
    /**
     * 返回以毫秒为单位的当前时间
     * @return 当前时间(毫秒)
     */
    protected long timeGen() {
        return System.currentTimeMillis();
    }

    public static void main(String[] args) throws InterruptedException {
        SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);
        for (int i = 0; i < 10; i++) {
            long id = idWorker.nextId();
            Thread.sleep(1);
            System.out.println(id);
        }
    }
}

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
# coding: utf-8
import time


class InvalidSystemClock(Exception):
    """
    时钟回拨异常
    """
    pass

# 64位ID的划分
WORKER_ID_BITS = 5
DATACENTER_ID_BITS = 5
SEQUENCE_BITS = 12

# 最大取值计算
MAX_WORKER_ID = -1 ^ (-1 << WORKER_ID_BITS)  # 2**5-1 0b11111
MAX_DATACENTER_ID = -1 ^ (-1 << DATACENTER_ID_BITS)

# 移位偏移计算
WOKER_ID_SHIFT = SEQUENCE_BITS
DATACENTER_ID_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS
TIMESTAMP_LEFT_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS + DATACENTER_ID_BITS

# 序号循环掩码
SEQUENCE_MASK = -1 ^ (-1 << SEQUENCE_BITS)

# 开始时间截 (2015-01-01)
TWEPOCH = 1420041600000


class IdWorker(object):
    """
    用于生成IDs
    """
    def __init__(self, datacenter_id, worker_id, sequence=0):
        """
        初始化
        :param datacenter_id: 数据中心（机器区域）ID
        :param worker_id: 机器ID
        :param sequence: 其实序号
        """
        # sanity check
        if worker_id > MAX_WORKER_ID or worker_id < 0:
            raise ValueError('worker_id值越界')

        if datacenter_id > MAX_DATACENTER_ID or datacenter_id < 0:
            raise ValueError('datacenter_id值越界')

        self.worker_id = worker_id
        self.datacenter_id = datacenter_id
        self.sequence = sequence

        self.last_timestamp = -1  # 上次计算的时间戳

    def _gen_timestamp(self):
        """
        生成整数时间戳
        :return:int timestamp
        """
        return int(time.time() * 1000)

    def get_id(self):
        """
        获取新ID
        :return:
        """
        timestamp = self._gen_timestamp()

        # 时钟回拨
        if timestamp < self.last_timestamp:
            raise InvalidSystemClock

        if timestamp == self.last_timestamp:
            self.sequence = (self.sequence + 1) & SEQUENCE_MASK
            if self.sequence == 0:
                timestamp = self._til_next_millis(self.last_timestamp)
        else:
            self.sequence = 0

        self.last_timestamp = timestamp

        new_id = ((timestamp - TWEPOCH) << TIMESTAMP_LEFT_SHIFT) | (self.datacenter_id << DATACENTER_ID_SHIFT) | \
                 (self.worker_id << WOKER_ID_SHIFT) | self.sequence
        return new_id

    def _til_next_millis(self, last_timestamp):
        """
        等到下一毫秒
        """
        timestamp = self._gen_timestamp()
        while timestamp <= last_timestamp:
            timestamp = self._gen_timestamp()
        return timestamp


if __name__ == '__main__':
    worker = IdWorker(0, 0)
    print(worker.get_id())

转自：https://blog.csdn.net/ycb1689/article/details/89331634

二

snowflake简介

互联网快速发展的今天，分布式应用系统已经见怪不怪，在分布式系统中，我们需要各种各样的ID，既然是ID那么必然是要保证全局唯一，除此之外，不同当业务还需要不同的特性，比如像并发巨大的业务要求ID生成效率高，吞吐大；比如某些银行类业务，需要按每日日期制定交易流水号；又比如我们希望用户的ID是随机的，无序的，纯数字的，且位数长度是小于10位的。等等，不同的业务场景需要的ID特性各不一样，于是，衍生了各种ID生成器，但大多数利用数据库控制ID的生成，性能受数据库并发能力限制，那么有没有一款不需要依赖任何中间件（如数据库，分布式缓存服务等）的ID生成器呢？本着取之于开源，用之于开源的原则，今天，特此介绍Twitter开源的一款分布式自增ID算法snowflake，并附上算法原理推导和演算过程！

snowflake算法是一款本地生成的（ID生成过程不依赖任何中间件，无网络通信），保证ID全局唯一，并且ID总体有序递增，性能每秒生成300w＋。

2

  • 1bit:一般是符号位，不做处理
  • 41bit:用来记录时间戳，这里可以记录69年，如果设置好起始时间比如今年是2018年，那么可以用到2089年，到时候怎么办？要是这个系统能用69年，我相信这个系统早都重构了好多次了。
  • 10bit:10bit用来记录机器ID，总共可以记录1024台机器，一般用前5位代表数据中心ID，后面5位是某个数据中心的机器ID
  • 12bit:循环位，用来对同一个毫秒之内产生不同的ID，12位可以最多记录4095个，也就是在同一个机器同一毫秒最多记录4095个，多余的需要进行等待下毫秒。

总体来说，在工作节点达到1024顶配的场景下，SnowFlake算法在同一毫秒内最多可以生成多少个全局唯一ID呢？这是一个简单的乘法：

同一毫秒的ID数量 = 1024 X 4096 = 4194304

400多万个ID，这个数字在绝大多数并发场景下都是够用的。

snowflake 算法中，第三个部分是工作机器ID，可以结合上一节的命名方法，并通过Zookeeper管理workId，免去手动频繁修改集群节点，免去配置机器ID的麻烦。

上面只是一个将64bit划分的标准，当然也不一定这么做，可以根据不同业务的具体场景来划分，比如下面给出一个业务场景：

  • 服务目前QPS10万，预计几年之内会发展到百万。
  • 当前机器三地部署，上海，北京，深圳都有。
  • 当前机器10台左右，预计未来会增加至百台。

这个时候我们根据上面的场景可以再次合理的划分62bit,QPS几年之内会发展到百万，那么每毫秒就是千级的请求，目前10台机器那么每台机器承担百级的请求，为了保证扩展，后面的循环位可以限制到1024，也就是2^10，那么循环位10位就足够了。

机器三地部署我们可以用3bit总共8来表示机房位置，当前的机器10台，为了保证扩展到百台那么可以用7bit 128来表示，时间位依然是41bit,那么还剩下64-10-3-7-41-1 = 2bit,还剩下2bit可以用来进行扩展。

3

适用场景：当我们需要无序不能被猜测的ID，并且需要一定高性能，且需要long型，那么就可以使用我们雪花算法。比如常见的订单ID，用雪花算法别人就发猜测你每天的订单量是多少。

上面定义了雪花算法的实现，在nextId中是我们生成雪花算法的关键。

防止时钟回拨

因为机器的原因会发生时间回拨，我们的雪花算法是强依赖我们的时间的，如果时间发生回拨，有可能会生成重复的ID，在我们上面的nextId中我们用当前时间和上一次的时间进行判断，如果当前时间小于上一次的时间那么肯定是发生了回拨，普通的算法会直接抛出异常,这里我们可以对其进行优化,一般分为两个情况:

  • 如果时间回拨时间较短，比如配置5ms以内，那么可以直接等待一定的时间，让机器的时间追上来。
  • 如果时间的回拨时间较长，我们不能接受这么长的阻塞等待，那么又有两个策略:
    1. 直接拒绝，抛出异常，打日志，通知RD时钟回滚。
    2. 利用扩展位，上面我们讨论过不同业务场景位数可能用不到那么多，那么我们可以把扩展位数利用起来了，比如当这个时间回拨比较长的时候，我们可以不需要等待，直接在扩展位加1。2位的扩展位允许我们有3次大的时钟回拨，一般来说就够了，如果其超过三次我们还是选择抛出异常，打日志。

通过上面的几种策略可以比较的防护我们的时钟回拨，防止出现回拨之后大量的异常出现。下面是修改之后的代码，这里修改了时钟回拨的逻辑:

最终代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
import org.apache.commons.lang3.RandomUtils;
import org.apache.commons.lang3.StringUtils;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
 
import java.lang.management.ManagementFactory;
import java.net.InetAddress;
import java.net.NetworkInterface;
import java.net.UnknownHostException;
import java.text.SimpleDateFormat;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.LockSupport;
 
 
/**
 * 分布式全局ID雪花算法解决方案
 *
 * 防止时钟回拨
 * 因为机器的原因会发生时间回拨，我们的雪花算法是强依赖我们的时间的，如果时间发生回拨，
 * 有可能会生成重复的ID，在我们上面的nextId中我们用当前时间和上一次的时间进行判断，
 * 如果当前时间小于上一次的时间那么肯定是发生了回拨，
 * 普通的算法会直接抛出异常,这里我们可以对其进行优化,一般分为两个情况:
 * 如果时间回拨时间较短，比如配置5ms以内，那么可以直接等待一定的时间，让机器的时间追上来。
 * 如果时间的回拨时间较长，我们不能接受这么长的阻塞等待，那么又有两个策略:
 * 直接拒绝，抛出异常，打日志，通知RD时钟回滚。
 * 利用扩展位，上面我们讨论过不同业务场景位数可能用不到那么多，那么我们可以把扩展位数利用起来了，
 * 比如当这个时间回拨比较长的时候，我们可以不需要等待，直接在扩展位加1。
 * 2位的扩展位允许我们有3次大的时钟回拨，一般来说就够了，如果其超过三次我们还是选择抛出异常，打日志。
 * 通过上面的几种策略可以比较的防护我们的时钟回拨，防止出现回拨之后大量的异常出现。下面是修改之后的代码，这里修改了时钟回拨的逻辑:
 */
public class SnowflakeIdFactory {
 
    private static final Logger log = LoggerFactory.getLogger(SnowflakeIdFactory.class);
 
    /**
     * EPOCH是服务器第一次上线时间点, 设置后不允许修改
     * 2018/9/29日，从此时开始计算，可以用到2089年
     */
    private static long EPOCH = 1538211907857L;
 
    /**
     * 每台workerId服务器有3个备份workerId, 备份workerId数量越多, 可靠性越高, 但是可部署的sequence ID服务越少
     */
    private static final long BACKUP_COUNT = 3;
 
    /**
     * worker id 的bit数，最多支持8192个节点
     */
    private static final long workerIdBits = 5L;
    /**
     * 数据中心标识位数
     */
    private static final long dataCenterIdBits = 5L;
    /**
     * 序列号，支持单节点最高每毫秒的最大ID数4096
     * 毫秒内自增位
     */
    private static final long sequenceBits = 12L;
 
    /**
     * 机器ID偏左移12位
     */
    private static final long workerIdShift = sequenceBits;
 
    /**
     * 数据中心ID左移17位(12+5)
     */
    private static final long dataCenterIdShift = sequenceBits + workerIdBits;
 
    /**
     * 时间毫秒左移22位(5+5+12)
     */
    private static final long timestampLeftShift = sequenceBits + workerIdBits + dataCenterIdBits;
    /**
     * sequence掩码，确保sequnce不会超出上限
     * 最大的序列号，4096
     * -1 的补码（二进制全1）右移12位, 然后取反
     * 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095)
     */
    private static final long sequenceMask = -1L ^ (-1L << sequenceBits);
 
    //private final static long sequenceMask = ~(-1L << sequenceBits);
    /**
     * 实际的最大workerId的值 结果是31，8091
     * workerId原则上上限为1024, 但是需要为每台sequence服务预留BACKUP_AMOUNT个workerId,
     * (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数)
     */
    //private static final long maxWorkerId = (1L << workerIdBits) / (BACKUP_COUNT + 1);
 
    //原来代码 -1 的补码（二进制全1）右移13位, 然后取反
    private static final long maxWorkerId = -1L ^ (-1L << workerIdBits);
    //private final static long maxWorkerId = ~(-1L << workerIdBits);
 
    /**
     * 支持的最大数据标识id，结果是31
     */
    private static final long maxDataCenterId = -1L ^ (-1L << dataCenterIdBits);
    /**
     * long workerIdBits = 5L;
     * -1L 的二进制: 1111111111111111111111111111111111111111111111111111111111111111
     * -1L<<workerIdBits = -32 ,二进制: 1111111111111111111111111111111111111111111111111111111111100000
     *  workerMask= -1L ^ -32 = 31, 二进制: 11111
     */
    private static long workerMask= -1L ^ (-1L << workerIdBits);
    //进程编码
    private long processId = 1L;
    private static long processMask=-1L ^ (-1L << dataCenterIdBits);
 
 
    /**
     * 工作机器ID(0~31)
     * snowflake算法给workerId预留了10位，即workId的取值范围为[0, 1023]，
     * 事实上实际生产环境不大可能需要部署1024个分布式ID服务，
     * 所以：将workerId取值范围缩小为[0, 511]，[512, 1023]
     * 这个范围的workerId当做备用workerId。workId为0的备用workerId是512，
     * workId为1的备用workerId是513，以此类推
     */
    private static long workerId;
 
    /**
     * 数据中心ID(0~31)
     */
    private long dataCenterId;
 
    /**
     * 当前毫秒生成的序列
     */
    private long sequence = 0L;
 
    /**
     * 上次生成ID的时间戳
     */
    private long lastTimestamp = -1L;
 
    private long extension = 0L;
    private long maxExtension =  0L;
 
    /**
     * 保留workerId和lastTimestamp, 以及备用workerId和其对应的lastTimestamp
     */
    private static Map<Long, Long> workerIdLastTimeMap = new ConcurrentHashMap<>();
 
    /**
     * 最大容忍时间, 单位毫秒, 即如果时钟只是回拨了该变量指定的时间, 那么等待相应的时间即可;
     * 考虑到sequence服务的高性能, 这个值不易过大
     */
    private static final long MAX_BACKWARD_MS = 3;
    private static SnowflakeIdFactory idWorker;
 
    static {
        idWorker = new SnowflakeIdFactory();
    }
 
 
 
    static {
        Calendar calendar = Calendar.getInstance();
        calendar.set(2018, Calendar.NOVEMBER, 1);
        calendar.set(Calendar.HOUR_OF_DAY, 0);
        calendar.set(Calendar.MINUTE, 0);
        calendar.set(Calendar.SECOND, 0);
        calendar.set(Calendar.MILLISECOND, 0);
        // EPOCH是服务器第一次上线时间点, 设置后不允许修改
        EPOCH = calendar.getTimeInMillis();
 
        // 初始化workerId和其所有备份workerId与lastTimestamp
        // 假设workerId为0且BACKUP_AMOUNT为4, 那么map的值为: {0:0L, 256:0L, 512:0L, 768:0L}
        // 假设workerId为2且BACKUP_AMOUNT为4, 那么map的值为: {2:0L, 258:0L, 514:0L, 770:0L}
       /* for (int i = 0; i<= BACKUP_COUNT; i++){
            workerIdLastTimeMap.put(workerId + (i * maxWorkerId), 0L);
        }*/
    }
 
    //成员类，IdGenUtils的实例对象的保存域
    private static class SnowflakeIdGenHolder {
        private static final SnowflakeIdFactory instance = new SnowflakeIdFactory();
    }
    //外部调用获取IdGenUtils的实例对象，确保不可变
    public static SnowflakeIdFactory getInstance(){
        return SnowflakeIdGenHolder.instance;
    }
 
    /**
     * 静态工具类
     *
     * @return
     */
    public static Long generateId(){
        long id = idWorker.nextId();
        return id;
    }
 
    //初始化构造，无参构造有参函数，默认节点都是0
    public SnowflakeIdFactory(){
        //this(0L, 0L);
        this.dataCenterId = getDataCenterId(maxDataCenterId);
        //获取机器编码
        this.workerId = getWorkerId(dataCenterId, maxWorkerId);
    }
 
    /**
     * 构造函数
     * @param workerId 工作ID (0~31)
     * @param dataCenterId 数据中心ID (0~31)
     */
    public SnowflakeIdFactory(long workerId, long dataCenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        if (dataCenterId > maxDataCenterId || dataCenterId < 0) {
            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDataCenterId));
        }
        this.workerId = workerId;
        this.dataCenterId = dataCenterId;
    }
 
   /**
     * 获取带自定义前缀的全局唯一编码
     */
    public String getStrCodingByPrefix(String prefix){
        Long ele = this.nextId();
        return prefix + ele.toString();
    }
 
    /**
     * 获得下一个ID (该方法是线程安全的)
     * 在单节点上获得下一个ID，使用Synchronized控制并发，而非CAS的方式，
     * 是因为CAS不适合并发量非常高的场景。
     *
     * 考虑时钟回拨
     * 缺陷: 如果连续两次时钟回拨, 可能还是会有问题, 但是这种概率极低极低
     * @return
     */
    public synchronized long nextId() {
        long currentTimestamp = timeGen();
        // 当发生时钟回拨时
        if (currentTimestamp < lastTimestamp){
            // 如果时钟回拨在可接受范围内, 等待即可
            long offset = lastTimestamp - currentTimestamp;
            if ( offset <= MAX_BACKWARD_MS){
                try {
                    //睡（lastTimestamp - currentTimestamp）ms让其追上
                    LockSupport.parkNanos(TimeUnit.MILLISECONDS.toNanos(offset));
                    //时间偏差大小小于5ms，则等待两倍时间
                    //wait(offset << 1);
                    //Thread.sleep(waitTimestamp);
 
                    currentTimestamp = timeGen();
                    //如果时间还小于当前时间，那么利用扩展字段加1
                    //或者是采用抛异常并上报
                    if (currentTimestamp < lastTimestamp) {
                        //扩展字段
                        //extension += 1;
                        //if (extension > maxExtension) {
                            //服务器时钟被调整了,ID生成器停止服务.
                            throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - currentTimestamp));
                        //}
                    }
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }else {
                //扩展字段
                /*extension += 1;
                if (extension > maxExtension) {
                    //服务器时钟被调整了,ID生成器停止服务.
                    throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - currentTimestamp));
                }*/
                tryGenerateKeyOnBackup(currentTimestamp);
            }
        }
        //对时钟回拨简单处理
       /* if (currentTimestamp < lastTimestamp) {
            //服务器时钟被调整了,ID生成器停止服务.
            throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - currentTimestamp));
        }*/
 
        // 如果和最后一次请求处于同一毫秒, 那么sequence+1
        if (lastTimestamp == currentTimestamp) {
            // 如果当前生成id的时间还是上次的时间，那么对sequence序列号进行+1
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                //自旋等待到下一毫秒
                currentTimestamp = waitUntilNextTime(lastTimestamp);
            }
            //判断是否溢出,也就是每毫秒内超过4095，当为4096时，与sequenceMask相与，sequence就等于0
            /*if (sequence == sequenceMask) {
                // 当前毫秒生成的序列数已经大于最大值，那么阻塞到下一个毫秒再获取新的时间戳
                currentTimestamp = this.waitUntilNextTime(lastTimestamp);
            }*/
 
        } else {
            // 如果是一个更近的时间戳, 那么sequence归零
            sequence = 0L;
        }
        // 更新上次生成id的时间戳
        lastTimestamp = currentTimestamp;
 
        // 更新map中保存的workerId对应的lastTimestamp
        //workerIdLastTimeMap.put(this.workerId, lastTimestamp);
 
        if (log.isDebugEnabled()) {
            log.debug("{}-{}-{}", new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS").format(new Date(lastTimestamp)), workerId, sequence);
        }
 
        // 进行移位操作生成int64的唯一ID
        //时间戳右移动23位
        long timestamp = (currentTimestamp - EPOCH) << timestampLeftShift;
 
        //workerId 右移动10位
        long workerId = this.workerId << workerIdShift;
 
        //dataCenterId 右移动(sequenceBits + workerIdBits = 17位)
        long dataCenterId = this.dataCenterId << dataCenterIdShift;
        return timestamp | dataCenterId | workerId | sequence;
    }
 
    /**
     * 尝试在workerId的备份workerId上生成
     * 核心优化代码在方法tryGenerateKeyOnBackup()中，BACKUP_COUNT即备份workerId数越多，
     * sequence服务避免时钟回拨影响的能力越强，但是可部署的sequence服务越少，
     * 设置BACKUP_COUNT为3，最多可以部署1024/(3+1)即256个sequence服务，完全够用，
     * 抗时钟回拨影响的能力也得到非常大的保障。
     * @param currentMillis 当前时间
     */
    private long tryGenerateKeyOnBackup(long currentMillis){
        // 遍历所有workerId(包括备用workerId, 查看哪些workerId可用)
        for (Map.Entry<Long, Long> entry:workerIdLastTimeMap.entrySet()){
            this.workerId = entry.getKey();
            // 取得备用workerId的lastTime
            Long tempLastTime = entry.getValue();
            lastTimestamp = tempLastTime==null?0L:tempLastTime;
 
            // 如果找到了合适的workerId
            if (lastTimestamp<=currentMillis){
                return lastTimestamp;
            }
        }
 
        // 如果所有workerId以及备用workerId都处于时钟回拨, 那么抛出异常
        throw new IllegalStateException("Clock is moving backwards, current time is "
                +currentMillis+" milliseconds, workerId map = " + workerIdLastTimeMap);
    }
 
    /**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     * @param lastTimestamp 上次生成ID的时间截
     * @return 当前时间戳
     */
    protected long waitUntilNextTime(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }
 
    protected long timeGen() {
        return System.currentTimeMillis();
    }
 
    /**
     *  获取WorkerId
     * @param dataCenterId
     * @param maxWorkerId
     * @return
     */
    protected static long getWorkerId(long dataCenterId, long maxWorkerId) {
        StringBuffer mpid = new StringBuffer();
        mpid.append(dataCenterId);
        String name = ManagementFactory.getRuntimeMXBean().getName();
        if (!name.isEmpty()) {
           // GET jvmPid
           mpid.append(name.split("@")[0]);
        }
       // MAC + PID 的 hashcode 获取16个低位
        return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1);
    }
 
    /**
     * 获取机器编码 用来做数据ID
     * 数据标识id部分 通常不建议采用下面的MAC地址方式，
     * 因为用户通过破解很容易拿到MAC进行破坏
     */
    protected static long getDataCenterId(long tempMaxDataCenterId) {
        if (tempMaxDataCenterId < 0L  || tempMaxDataCenterId > maxDataCenterId) {
            tempMaxDataCenterId = maxDataCenterId;
        }
        long id = 0L;
        try {
            InetAddress ip = InetAddress.getLocalHost();
            NetworkInterface network = NetworkInterface.getByInetAddress(ip);
            if (network == null) {
                id = 1L;
            } else {
                byte[] mac = network.getHardwareAddress();
                id = ((0x000000FF & (long) mac[mac.length - 1])
                        | (0x0000FF00 & (((long) mac[mac.length - 2]) << 8))) >> 6;
                id = id % (tempMaxDataCenterId + 1);
            }
        } catch (Exception e) {
            System.out.println(" getDatacenterId: " + e.getMessage());
        }
        return id;
    }
 
 
    public static void testProductIdByMoreThread(int dataCenterId, int workerId, int n) throws InterruptedException {
        List<Thread> tlist = new ArrayList<>();
        Set<Long> setAll = new HashSet<>();
        CountDownLatch cdLatch = new CountDownLatch(10);
        long start = System.currentTimeMillis();
        int threadNo = dataCenterId;
        Map<String,SnowflakeIdFactory> idFactories = new HashMap<>();
        for(int i=0;i<10;i++){
            //用线程名称做map key.
            idFactories.put("snowflake"+i,new SnowflakeIdFactory(workerId, threadNo++));
        }
        for(int i=0;i<10;i++){
            Thread temp =new Thread(new Runnable() {
                @Override
                public void run() {
                    Set<Long> setId = new HashSet<>();
                    SnowflakeIdFactory idWorker = idFactories.get(Thread.currentThread().getName());
                    for(int j=0;j<n;j++){
                        setId.add(idWorker.nextId());
                    }
                    synchronized (setAll){
                        setAll.addAll(setId);
                        log.info("{}生产了{}个id,并成功加入到setAll中.",Thread.currentThread().getName(),n);
                    }
                    cdLatch.countDown();
                }
            },"snowflake"+i);
            tlist.add(temp);
        }
        for(int j=0;j<10;j++){
            tlist.get(j).start();
        }
        cdLatch.await();
 
        long end1 = System.currentTimeMillis() - start;
 
        log.info("共耗时:{}毫秒,预期应该生产{}个id, 实际合并总计生成ID个数:{}",end1,10*n,setAll.size());
 
    }
 
    public static void testProductId(int dataCenterId, int workerId, int n){
        SnowflakeIdFactory idWorker = new SnowflakeIdFactory(workerId, dataCenterId);
        SnowflakeIdFactory idWorker2 = new SnowflakeIdFactory(workerId+1, dataCenterId);
        Set<Long> setOne = new HashSet<>();
        Set<Long> setTow = new HashSet<>();
        long start = System.currentTimeMillis();
        for (int i = 0; i < n; i++) {
            setOne.add(idWorker.nextId());//加入set
        }
        long end1 = System.currentTimeMillis() - start;
        log.info("第一批ID预计生成{}个,实际生成{}个<<<<*>>>>共耗时:{}",n,setOne.size(),end1);
 
        for (int i = 0; i < n; i++) {
            setTow.add(idWorker2.nextId());//加入set
        }
        long end2 = System.currentTimeMillis() - start;
        log.info("第二批ID预计生成{}个,实际生成{}个<<<<*>>>>共耗时:{}",n,setTow.size(),end2);
 
        setOne.addAll(setTow);
        log.info("合并总计生成ID个数:{}",setOne.size());
 
    }
 
    public static void testPerSecondProductIdNums(){
        SnowflakeIdFactory idWorker = new SnowflakeIdFactory(1, 2);
        long start = System.currentTimeMillis();
        int count = 0;
        for (int i = 0; System.currentTimeMillis()-start<1000; i++,count=i) {
            /**  测试方法一: 此用法纯粹的生产ID,每秒生产ID个数为300w+ */
            idWorker.nextId();
            /**  测试方法二: 在log中打印,同时获取ID,此用法生产ID的能力受限于log.error()的吞吐能力.
             * 每秒徘徊在10万左右. */
            //log.error("{}",idWorker.nextId());
        }
        long end = System.currentTimeMillis()-start;
        System.out.println(end);
        System.out.println(count);
    }
 
    public static void main(String[] args) {
        /** case1: 测试每秒生产id个数?
         *   结论: 每秒生产id个数300w+ */
        testPerSecondProductIdNums();
 
        /** case2: 单线程-测试多个生产者同时生产N个id,验证id是否有重复?
         *   结论: 验证通过,没有重复. */
        //testProductId(1,2,10000);//验证通过!
        //testProductId(1,2,20000);//验证通过!
 
        /** case3: 多线程-测试多个生产者同时生产N个id, 全部id在全局范围内是否会重复?
         *   结论: 验证通过,没有重复. */
       /* try {
            testProductIdByMoreThread(1,2,100000);//单机测试此场景,性能损失至少折半!
        } catch (InterruptedException e) {
            e.printStackTrace();
        }*/
 
    }
}

发表于 分类于

在 Python 中，整数 0 代表假，整数 1 代表真。不过，除此之外，Python 也把任何空数据结构视为假，把任何非空数据结构视为真。更一般地，真和假的概念是 Python 中每个对象的固有属性：每个对象非真即假。

  • 数字如果等于零则为假，反之则为真。
  • 其他对象如果为空则为假，反之则为真。
  • 空字符串、空列表、空字典都为假。
  • None 为假。