outline

consistent hashing 一致性哈性

复习：

数据量过大，需要将数据拆分，有两种拆分方式：

纵向：不同表存在不同机器，按常用字段和不常用字段将表拆分存在不同机器
横向：将数据横向切分，存在不同的机器上

为什么要做一致性hash？

一种简单的hash算法：将数据存在第%n个机器上
当增加一台机器时（n -> n+1），需要迁移的数据量非常大
因此这个hash算法称为不一致hash

一个简单的一致性hash算法：

将key模一个很大的数，比如360
将360分配给n台机器，每个机器负责一段区间
区间分配信息记录在一张表上，存在web server上
新加一台机器的时候，在表中选择一个位置插入，匀走相邻两台机器的一部分数据
比如n从3变化到4：

缺陷：

数据分布不均匀：分摊数据后，各机器数据分布不均匀
迁移压力大：新机器只能从与之相邻的两台机器上迁移数据，导致这两台老机器负载过大

一个更实用的一致性hashing

将机器（IP或者名字）与数据，都看做环上的一个点！！

将机器映射到环上，如下图所示的ABCD是四个机器
比如有个数据，蓝色的点，散在了蓝色点出。那么就顺时针去找一个机器，把这个数据放在这个机器上，即B
那么如何让点更均匀呢？
四个点可能不会均匀，但是4000个点相对来说一定会更均匀。那就引入Micro shards / Virtual nodes 的概念——一台机器对应了1000个代表。例如将A机器撒在环上（下图红色），将B机器撒在环上（下图蓝色）

来了一个数据时，例如图中的黑色点Data，那么就找到了机器B
也就是意味着，每个机器负责了很多个离散的区间。
当需要加入一台新机器时？加入我们现在机器分布是这样：

新来了一个E的机器，丢到环里之后

[D,E]之间的数据必须从A迁移到E上！！！！[A,E]之间的数据必须从B迁移到E上

总结：

将整个hash区间看成一个环，大小从359变成 $2^{64}-1$
将机器和数据都看成是环上的点
引入Micro shards/Virtual nodes的概念，每台机器对应1000个Micro shards/Virtual nodes
把每台机器看成1000台机器均匀撒在环上
每加入一条数据
- 计算其id对应的hash值，得到0~ $2^{64}-1$ 区间上的一个点，找到环上对应的点
- 从这个点出发顺时针找到第一个机器的virtual node
- 该virtual node对应的机器就是本条数据应该存储的数据库服务器
每加入一台新机器
- 在环上随机撒1000个点
- 这1000个virtual node 各自想顺时针相邻的第一个virtual node 索要数据
- 例子：http://www.jiuzhang.com/qa/2067/
实现用TreeMap 红黑树

问题：

问题1：需要存储数据在环的哪里吗？
不需要。因为这个数据在哪里与其它数据在哪里没有关系。只需要在环上计算数据所在的点的下一个位置的机器是哪个即可。

问题：那这个1000能变成100万吗？
太多也不行。查询效率会变低。就是在比较均匀的情况下选一个比较快的就行。

思考：哪种数据结构能够支持这种“顺时针”寻找下一个机器的功能呢？——链表是不行的，因为链表长度太大，查找很慢。用TreeMap!! 就是一个红黑树，能在LogN的时间内寻找比n大的最小值。

数据备份 Replica

问题：Backup和Replica有什么区别？

Backup

一般是周期性的，比如每天晚上进行一次备份
当数据丢失的时候，通常只能恢复到之前的某个时间点
Backup 的数据是死数据，是离线的。不用作在线的数据服务，不分摊读

Replica

是实时的，在数据写入的时候，就会以复制品的形式存为多份
当数据丢失的时候，可以马上通过其他的复制品恢复
Replica是实时的。用作在线的数据服务，分摊读

思考：既然 Replica 更牛，那么还需要 Backup么？

backup便宜哇~

MySQL类型数据库的Replica

以MySQL为代表的的SQL型数据库，通常自带Master Slave模式的Replica方法。Master负责写，Slave负责读。Slave从Master中同步对数据的操作。

Master - slave原理：Write Ahead Log

SQL数据库的任何操作，都会以Log的形式做一份记录。

比如Master上的数据A在B时刻从C改成了D，那么Master会通知Slave来读Log（不是同步值，而是同步操作！）。Slave被激活后，告诉master我可以更新了，之后Master有任何操作就会通知slave来读log然后slave会同步操作

因此Slave上的数据是有延迟的。

问题：万一Master挂了怎么办？

将一台slave升级为master, 接受读 + 写
可能会造成一定程度的数据丢失和不一致

NoSQL类型数据库的Replica

以Cassandra为代表的的NoSQL数据库，通常将数据“顺时针”存储在Consistent hashing环上的三个vitual nodes中。

MySQL和NoSQL型数据库的Replica比较

SQL

“自带” 的 Replica 方式是 Master Slave
“手动” 的 Replica 方式也可以在 Consistent Hashing 环上顺时针存三份

NoSQL

“自带” 的 Replica 方式就是 Consistent Hashing 环上顺时针存三份
“手动” 的 Replica 方式：就不需要手动了，NoSQL就是在 Sharding 和 Replica 上帮你偷懒用的！

设计短网址系统 Design Tiny URL

短网址生成网站：

https://bitly.com/
https://goo.gl/

系统设计的常见误区：

以下几个是误区

系统一定巨大无比 —— ×
必须用NoSQL —— ×
必须是分布式 —— ×

不可以扔关键词，必须一步步分析。

正确打开方式——4S分析法

提问：分析功能/需求/QPS/存储容量——Scenario
画图：根据分析结果设计“可行解”—— Service+Storage
进化：研究可能遇到的问题，优化系统 —— Scale

1. Scenario 场景需求分析

我要设计啥

根据长URL生成短URL
根据短URL还原长URL

QPS + Storage

假设这个是用来给微博做短网址的跳转。那么QPS能有多少？

询问微博日活用户 —— 约100M
推算产生一条Tiny URL的QPS
- 假设每个用户平均每天发0.1条微博，
- 平均写QPS = 100M * 0.1 / 86400 ~ 100
- 峰值QPS = 100 * 2 = 200
推算点击一条Tiny URL的QPS
- 假设每个用户平均点1个Tiny URL
- 平均读QPS = 100M * 1 / 86400 ~ 1k
- 峰值QPS = 2k
推算每天产生的新的 URL 所占存储
- 100M * 0.1 ~ 10M 条
- 每一条 URL 长度平均 100 算，一共1G
- 1T 的硬盘可以用 3 年

前3点：2k QPS ，一台SSD支持的MySQL完全可以搞定！

2. Service 服务

逻辑块聚类与接口设计

TinyUrl只有一个UrlService
- 本身就是一个小Application
- 无需关心其他的
函数设计
- UrlService.encode(long_url)
- `UrlService.decode(short_url)

访问端口设计

GET /<short_url>
	return a Http redirect response
POST /data/shorten/
	Data = {url: http://xxxx }
	Return short url

3. Storage 数据存储

两个步骤：

选择存储结构
细化数据表

选择存储结构 SQL vs NoSQL

是否需要支持 Transaction（事务）？
- NoSQL不支持Transaction
- 是否需要丰富的 SQL Query？
NoSQL的SQL Query不是太丰富
- 也有一些NoSQL的数据库提供简单的SQL Query支持
是否想偷懒？
- 大多数 Web Framework 与 SQL 数据库兼容得很好
- 用SQL比用NoSQL少写很多代码
是否需要Sequential ID？
- SQL 为你提供了 auto-increment 的 Sequential ID。也就是1,2,3,4,5 …
- NoSQL的ID并不是 Sequential 的
对QPS的要求有多高？
- NoSQL 的性能更高
对Scalability的要求有多高？
- SQL 需要码农自己写代码来 Scale
- 还记得Db那节课中怎么做 Sharding，Replica 的么？
NoSQL 这些都帮你做了

选择

是否需要支持 Transaction？——不需要。NoSQL +1
是否需要丰富的 SQL Query？——不需要。NoSQL +1
是否想偷懒？——Tiny URL 需要写的代码并不复杂。NoSQL+1
对QPS的要求有多高？—— 经计算，2k QPS并不高，而且2k读可以用Cache，写很少。SQL +1
对Scalability的要求有多高？—— 存储和QPS要求都不高，单机都可以搞定。SQL+1
是否需要Sequential ID？—— 取决于你的算法是什么 : 如何将Long URL 转化为 Short URL

4. 算法：如何将Long URL 转化为 Short URL

4.1 算法1 使用哈希函数 Hash Function（不可行）

比如取 Long Url 的 MD5 的最后 6 位——这个方法肯定是有问题的

优点：快
缺点：难以设计一个没有冲突的哈希算法

4.2 算法2：随机生成 + 数据库去重

随机一个 6 位的 ShortURL，如果没有被用过，就绑定到该 LongURL

伪代码如下：

优点：实现简单
缺点：生成短网址的长度随着短网址越来越多变得越来越慢
可行性：其实能凑合用。在生活中有很多随机编码的，例如机票码、酒店码，是不可重复的，就是用这种方法弄的。

4.3 算法3：进制转换 Base62

Base62
- 将6位的short url看成一个62进制的数（0-9,a-z,A-Z）
- 每个short url对应到一个整数
- 该整数对应数据库表的主键——Sequential ID
6位可以表示不同的URL有多少？
- 5位 = 625625 = 9亿
- 6位 = 626626 = 570亿
- 7位 = 627627 = 35000亿
优缺点
- 优点：效率高
- 缺点：依赖于全局的自增ID

4.4 算法2与3的比较

基于随机生成的方法
需要根据 Long 查询 Short，也需要根据 Short 查询 Long。基本上work solution如下图所示：

如果选择用 SQL 型数据库，表结构如下：

并且需要对shortKey和longURL分别建索引
• 什么是索引？
• 索引的原理？
也可以选用 NoSQL 数据库，但是需要建立两张表（大多数NoSQL数据库不支持二级索引）。以 Cassandra 为例子
第一张表：根据 Long 查询 Short
row_key=longURL, column_key=ShortURL, value=null or timestamp
第二张表：根据 Short 查询 Long
row_key=shortURL, column_key=LongURL, value=null or timestamp
基于进制转换的方法
因为需要用到自增ID（Sequential ID），因此只能选择使用 SQL 型数据库。表单结构如下，shortURL 可以不存储在表单里，因为可以根据 id 来进行换算

5. Scale 优化

5.1 如何提高响应速度？

读操作的优化

既然读操作比较多，那么可以用cache的方式去提速。

cache里存什么？
- long to short(生成新short url时需要)
- short to long(查询short url时需要)
查询的流程图：

5.2 如何提速？

利用地理位置信息加速
优化服务器速度
- 不同地区，使用不同Web服务器
- 通过DNS解析不同地区的用户到不同的服务器
优化数据访问速度
- 使用Centralized MySQL + Distributed Memcached
- 数据库共享一个，不同地区设置多个缓存
- 一个MySQL配多个Memcached, Memcached跨地区分布

5.3 数据量扩展

如果数据量很大，一台MySQL搞不定了

什么时候需要扩展多台服务器？
- Cache资源不够
- 写操作越来越多
- 请求太多，无法通过Cache满足
增加多台数据库可以优化什么？
- 解决存不下的问题——Storage角度（TinyURL一般遇不到这种问题）
- 解决忙不过来的问题——QPS角度
- TinyURL主要是什么问题？？——忙不过来的问题

如何解决忙不过来的问题？拆分
- 纵向切分？不同列放不同数据库？不可行！
- 横向拆分？
  - 用什么做sharding key?
  - 如果用longURL做为sharding key，如何查询ID(short URL) ?
    - 已知shortURL查询longURL时，只能广播给N台数据库查询
    - 不能降低每台机器QPS
  - 如果用ID(short URL)做为sharding key，如何查询 longURL?
    - 假设按照ID%N来分配存储
    - short2long
      - 将shortURL转化为ID
      - 根据ID计算找到数据库
      - 在该数据库中查询longURL即可
    - long2short
      - 先查询：广播给N台数据库，查询是否存在，似乎有点耗时，但是也是可行的，因为数据库服务器不会太多
      - 再插入如果不存在的话，获得下一个自增ID值，插入对应数据库
      - 其实也不可以不查询直接插入，因为long2short没有必要意义对应，一个long可以对应多个short，也就是说可以把长网址转成多个短网址，但是一旦用户获得一个短网址，相同的短网址只能对应一个长网址。
    - 这种方法还有一个问题，如何在多台数据库服务器上获取全局递增的ID？（因为每台机器上都有一个数据表，需要获取所有数据的递增ID就是个问题），解决办法：
      1. 专门用一台服务器负责自增ID服务，不存储数据，也不负责查询
      2. 用Zookeeper
      但用全局递增ID不是解决TinyURL的好办法
  下面是一种更好的sharding办法，不需要全局递增ID：
- 如果最开始shortkey为6位，那就增加一位前置位：
  - AB1234 –> 0AB1234（该前置位由hash(long_url)%62得到（可以用consistent hash算法），因此是唯一的。这个前置位可以作为机器的ID等）
  - 另一种做法，把第一位单独留出来做sharding key，总共还是6位
- 该前置位为sharding key
- 这样我们就可以同时通过shortURL和longURL得到sharding key
  - 无需广播
  - 无论short2long还是long2short都可直接定位数据所在服务器
- 当新加入一个longURL时，先通过hash(long_url)%62得到机器ID，然后在该机器上，通过该台机器的自增ID通过进制转换得到6位shortkey
- 用户已知shortURL时，先按第一位获取到机器ID，然后在此机器上查询longURL
  
  那么当前的架构就变成了：

5.4 Multi region 的进一步优化

上面的架构图还有优化的空间：

网站服务器与数据库服务器之间的通信
中心化服务器集群与跨地域的web server之间的通信较慢，比如如果中心数据库放在美国，那么中国的服务器需要访问美国的数据库，通信较慢

解决方法1：重写数据库到中国，中国用户访问中国数据库

问题：重写数据库，一致性问题如何解决？很难解决

正确打开方式：

想一想用户习惯：

中国的用户一般访问的网站是中国的，美国的用户一般访问的网站是美国的
中国用户访问时，会被DNS分配中国的服务器

因此我们可以用地域信息进行sharding，也就是说按照网站的地域信息将其数据分开存储在不同地方的数据库中

如何获得网站的地域信息？做一张用户经常访问的网站数据表

这样中国用户要访问的网站大多在位于中国的数据库中，响应速度就会比较快，当然也有少量中国用户需要访问美国网站的情况，就直接去访问美国数据库就好，反正不会慢对少，毕竟中国访问中国是主流需求，优化系统就是要优化主要需求。

最终架构图

5.5 自定义短链接

用户自定义短网址 -> 长网址映射

http://tiny.url/google/ => http://www.google.com
http://tiny.url/systemdesign/ => http://www.jiuzhang.com/course/2/

一个错误的想法是：

在URLtable中增加一个column，存放自定义的URL，因为这一列大部分会是空的，浪费空间。