分片存储-细碎设计系列(三)

摘要

系统设计中数据存储模型是核心部分，量级大、QPS 高，通常会通过分库降低 CPU/内存 /磁盘 IO 等系统瓶颈，通过分表降低单表量级过大从而导致的性能问题。那么类似分片存储后从业务角度看会有什么问题？索引法、基因法有是什么呢？

前言

大量的数据存储，常见的水平分片算法：

Range
Hash

水平分片算法比较普及，只是为了承上启下简单码了一些，懂的同学可以快速跳过！

Range

基于 Unique Key 按照范围分片。切分的维度：

基于固定量级分表，比如千万级分表。tb1：0-1000W 、tb2：1000W- 2000W 。
基于时间维度分表，比如年、月。

优点：

路由策略简单，按照资源范围快速定位到分片。
扩展性，水平创建日后需要的表即可。

不足：

数据分布严重不均匀。
热点数据集中，单表过热。
量级分表，Unique Key 必须满足递增属性。

Hash

基于 Unique Key 取模，均匀分片。

优点：

路由策略简单，Hash Unique Key 快速定位分片。
数据存储&请求量均匀分配，只要 Unique Key 是均匀的。

不足:

扩展性差，扩容时成本较高。

以上是预热部分，当数据分片后对业务带来了哪些问题呢？

例子

Passport Service 几乎是每一个公司必备的基础服务。

之前团队中负责设计 passport 服务时有过 user 存储的思考和设计，简单说说。

Passport Service 是一个非常常见的基础服务，主要提供账号通行证相关能力，在使用场景中比如登录、注册、登出、登录态校验、更新等，其核心存储是一张 user 表：

比如：

CREATE TABLE `tb_user0` (
  `id` int(10) NOT NULL AUTO_INCREMENT COMMENT '表自增 ID',
  `uid` bigint(20) NOT NULL DEFAULT '0' COMMENT '用户 ID',
  `user_name` varchar(255) NOT NULL DEFAULT '' COMMENT '用户名，不区分大小些；统一成大写，加密后入库',
  `pwd` char(40) NOT NULL DEFAULT '' COMMENT '密码',
  
  `......`
  
  `update_time` int(10) NOT NULL DEFAULT '0' COMMENT '最后更新时间',
  `create_time` int(10) NOT NULL DEFAULT '0' COMMENT '创建时间',
  PRIMARY KEY (`id`),
  KEY `idx_uid` (`uid`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='用户主表';

user_name 为登录用户名，通常会是手机号，需要脱敏。

ok，这张表如何设计呢？

单表实现不合理，结合业务场景，水平分片是必须要有的。

账号量级大，请求量高，需要保证高可用和高一致性。UID 作为 Unique Key，基于 UID 是高频查询，那么就基于 UID 水平分表。

前台服务相对核心的操作：

登录。基于 user_name+pwd 实现登录，量级占大盘<=1%。此处 UID 为结果数据
校验登录态。基于 token 解析出 UID，判断登录态获取用户信息，量级占大盘>= 99%。此处 UID 为起始数据

后台服务(MIS 或运营管理后台) 操作：

超多维度检索
批量分页查询

问题

基于 UID 分片，那么问题来了~

基于 UID 分片，前台服务登录时没有 UID，只有 user_name，不清楚账号数据落在哪张表，遍历扫全库么？性能低的丑陋。

用 UID 分片，如何高效实现查询？

这是本文要讨论的问题。
数据既然分片了，后台服务的多维度检索，跨分片汇总数据分页查询怎么搞？继续遍历全库内存计数么？ Mysql 抗的住么？就算 Mysql 抗的住，后台用户等的起么？就算后台用户脾气好，客户端不会超时么？

如何多分片高效检索汇总？

这是本文要讨论的问题++。

方案

issue1: 用 UID 分片，如何高效实现查询?

方案一：索引法

思路：UID 可以定位分片，user_name 无法直接定位，那么通过 user_name 定位 UID，进而定位分片。

方案：

基于 Mysql 建立索引表，存储 user_name 与 UID 的 Mapping 关系。
登录校验时基于索引表通过 user_name 查询到 UID，然后路由到指定分片获取数据。
索引表属性少，理论上单行小，容量千万级没问题。
整体模型就是：基于 Index 索引表 + Meta 元数据表(分片)

问题：多一次 DB 查询，性能相对降低。

方案二: 持久化缓存映射

思路：接受不了多一次 DB 查询，那就将映射关系持久化到缓存中。

方案:

基于缓存(Redis)存储映射关系
登录校验时通过 user_name 到缓存中查询 UID，然后路由到指定分片。
如果缓存没有查到，扫全库获取映射关系持久化到缓存

问题：

多一次 Redis 查询，其实也没啥。
有缓存击穿风险，Cache 中不存在，当高并发请求打进来，全部去 DB 扫全库，引起 DB 压力瞬间陡增。
有缓存穿透风险，当 UID 在 Cache 和 DB 中都不存在，并且不断请求，这种攻击也会导致数据库压力过大。

普通场景下，索引+缓存就可以解决大部分问题

方案三：基于 username 生成 uid

思路：不想单独存储映射关系，直接通过 username 生成 uid

方案：这种通过字符串生成 ID 的 Hash 函数很多，f(username) = uid

问题:

Hash 碰撞，UID 冲突的风险
username 不能更新

方案四: 基因法

思路: 从 username 中提取基因，加入到 uid 生成规则中。

方案:

这里需要引入分布式全局唯一 ID 生成能力，该基因法依赖分布式 ID，后续会输出《分布式发号器》的文字，先简单普及下分布式 ID 生成的一种常见算法，Snowflake 雪花

SnowFlake 算法生成 id 的结果是一个 64bit 大小的整数，它的结构如下图：

1bit，不用，因为二进制中最高位是符号位，1 表示负数，0 表示正数。生成的 id 一般都是用整数，所以最高位固定为 0
41bit-时间戳，用来记录时间戳，毫秒级
10bit-工作机器 id，用来记录集群+机器 id
12bit-序列号，序列号，用来记录同毫秒内产生的不同 id，支持步长自增。

所谓基因算法就是提取 username 的分片基因，合并到全局唯一的 ID 上，生成一个全新的 UID 。如下图：

直接上 Demo 源码吧：

Demo 源码全局唯一 ID 基于 SnowFlake 算法生成，对每个 Block 的 Bit 数简单调整了一下。

基础配置:

const (
	GENE_NODEIDID_BITS int64 = 10	// 机器节点 10Bit
	GENE_SEQ_BITS      int64 = 13	// 同时间同节点序列号 13Bit
	GENE_BITS          int64 = 12	// 分片基因 12Bit

	GENE_NODEID_MAX int64 = -1 ^ (-1 << GENE_NODEIDID_BITS)	// 机器节点最大值 1024
	GENE_SEQ_MAX    int64 = -1 ^ (-1 << GENE_SEQ_BITS)			// 序列号最大值 8192

	// 这块放弃了时间，为了保留基因。timestemp 单位 s，28 个 bit 大约 7 8 年
	GENE_TIMESTEMP_SHIFT       = GENE_NODEIDID_BITS + GENE_SEQ_BITS + GENE_BITS
	GENE_NODEIDID_SHIFT  int64 = GENE_SEQ_BITS + GENE_BITS
	GENE_SEQ_SHIFT       int64 = GENE_BITS

	// 拒绝浪费，珍惜时间
	GENE_EPOCH int64 = 1624258189

	// 默认步长
	GENE_DEFAULT_STEP_LONG = 1
)

这是个 Demo，GENE_BITS 位数需要根据分片数量决定，比如分 16 片，那么 GENE_BITS 4 个 bit 就可以

基因 ID 实例:

type GeneID struct {
	m         sync.Mutex	// 读写锁
	timestemp int64				// 当前时间戳
	nodeID    int64				// 机器节点
	seq       int64				// 序列号
	geneID    int64				// 基因
	step      int64				// 序列号增长步长
}

样本基因提取：

// 基于基因样本提取基因 ID
func ExtractGene(geneSample []byte) int64 {
	gene := md5.Sum(geneSample)
	hashGeneValue := fmt.Sprintf("%x", gene)[29:32]
	geneID, _ := strconv.ParseInt(hashGeneValue, 16, 64)
	return geneID
}

样本 Hash 生成 32 位 MD5
取末尾三个字符
将字符串作为 16 进制转化成 int64 000-fff
结果为基因 ID

基于雪花算法生成完整 ID：

func (g *GeneID) Generate() int64 {
	g.m.Lock()
	defer g.m.Unlock()

	now := time.Now().UnixNano() / 1e9 // 纳秒转秒
	if now == g.timestemp {
		g.seq = g.seq + g.step
		if g.seq > GENE_SEQ_MAX {
			for now <= g.timestemp {
				now = time.Now().UnixNano() / 1e9
			}
			g.seq = 0
		}
	} else {
		g.seq = 0
	}
	g.timestemp = now
	return g.timeBlock() | g.nodeBlock() | g.seqBlock() | g.geneBlock()
}

完整 Demo 源码可访问： https://github.com/xiaoxuz/idgenerator

不足: username 不能更新

issue2：如何多分片高效检索汇总？

思路 1：前后台数据解耦，资源存储隔离，避免后台低效查询引发前台查询抖动。

思路 2：接受数据冗余存储设计，采用其他存储服务作为后台存储组件，数据双写或异步写入。

思路 3：后台存储组件可以基于数据时效性选择：

时效性要求高：选择Elasticsearch，基于其分布式倒排索引的特性，实时同步前台数据，并为后台服务提供多维度检索和聚合能力。
时效性要求低：选择大数据相关服务，比如小时级或天级数据入 Hive。

之前基于 Elasticsearch 做过前后台数据隔离设计，大概设计如下：

基于阿里开源的 Canal 服务实时订阅消费前台 Mysql 的 binlog，将 binlog 发布到消息队列Kafka中。

下游可以通过 Flink 实时计算服务或者通过 Golang 实现的 Consumer 来消费 Kafka 中的 Binlog，解析并且转存到Elasticsearch。

后台服务基于 Elasticsearch 的 RESTful API 实现实时检索和聚合需求。

总结

Issue1：用 UID 分片，如何高效实现查询？

索引法
缓存映射
username 生成 uid
基因法

Issue2：如何多分片高效检索汇总？

前后台资源隔离，冗余存储设计
基于 Es 或大数据相关服务对后台数据进行存储，并提供实时&离线的数据能力。

思考

记忆力好比缓存，记笔记好比落盘。缓存总会失效，硬盘你可以多副本保留。

tips：学习不要光靠脑袋记，沉淀下来记到本子上才是自己的。

收工

打完收工，感谢阅读！

分片存储-细碎设计系列(三)

摘要

前言

Range

Hash

例子

问题

方案

issue1: 用 UID 分片，如何高效实现查询?

issue2： 如何多分片高效检索汇总？

总结

思考

收工

issue2：如何多分片高效检索汇总？