每日分享
Breathe. Take care. Stand still for a minute. What you are looking for might just be looking for you too.
呼吸。 放轻松。 静止一会儿。 您正在寻找的也可能只是在寻找您。
小闫语录：
充实自己，提升自己，照顾好自己，以全盛的姿态去迎接即将到来的、你要寻找的东西。它不会缺席，迟到只是浪费时间在寻找你的路上。不要放弃，更不要为了寻找变的狼狈。
1.8系统设计
上篇文章传送门『我是个链接』
上篇文章对 Python web 框架中的一些经典问题做了总结，比如 WSGI、web 框架、网络安全问题、RESTful 以及 RESTful API
本篇文章将开始系统设计的相关内容，开始咯~
1.8.1 系统设计相关内容
1.什么是系统设计
2.系统设计需要掌握哪些知识
3.如何设计以及如何实现一个后端系统服务的设计
1.8.1.1 什么是系统设计 System Design
系统设计是一个定义系统架构、模块、接口和数据满足特定需求的过程。比如设计一个短网址服务、评论服务、Feed流系统（微博、知乎）、抢红包系统。这些系统设计是最近几年才开始流行起来的，因为现在很多的公司开始采用了微服务架构，在微服务架构之下很多系统被按照业务拆分，需要单独设计一个系统服务。
举个例子，比如短网址服务。一开始是由于 Twitter 只能发 140 个字，很多时候贴一个网址就快占满了，为了解决这个问题，诞生了短网址服务。简单的说就是根据一个长地址生成一个短地址，现在很多网站，比如头条、微博、知乎，大家都能见到这种类似形式的短网址。
在一个公司中会有很多不同的部门，不同的业务，不可能为每一个业务都开发一套。这个时候，公司里可以提供一个供所有业务使用的短网址服务。所有有需要的业务都可以向短网址服务请求接口，获取一个短网址。这就是短网址服务诞生的场景。
1.8.1.2 系统设计的难点
系统设计是中高级工程师必经之路。需要具备相关领域、算法的经验，有一定的架构设计能力。还需要熟悉后端的技术组件，比如消息队列、缓存、数据库和各种 web 框架。我们需要掌握它们的使用场景以及底层原理。比如什么时候去使用缓存？数据同步的问题如何去解决？业务的选型（关系型数据库还是非关系型）？另外一点就是具备文档撰写、流程图绘制、架构设计、编码实现等综合能力。
1.8.1.3 系统设计的要素
系统设计有三大要素：
1.适用场景和限制条件；
2.数据存储设计；
3.算法模块设计。
1.8.1.4 要素之一：场景和限制
1.这个系统是在什么地方使用的？比如短网址系统提供给站内各种服务生成短网址。
2.限制条件：用户估计有多少？至少要能支撑多少用户（服务）？
3.估算并发 qps：峰值 qps 是多少？平均 qps 是多少？
qps ：每秒的查询请求量
1.8.1.5 要素之二：数据存储设计
数据库的选型：
1.按需求设计数据表，需要哪些字段，使用什么类型？数据增长的规模等。
2.数据库选型：是否需要持久化？使用关系型还是 NoSQL？
3.如何优化？如何设计索引？是否可以使用缓存？
1.8.1.6 要素之三：算法模块设计
算法解决问题的核心。程序 = 算法 + 数据结构。系统 = 服务 + 存储
1.需要哪些接口？接口如何设计？
2.使用什么算法或者模型？
3.不同实现方式之间的优劣对比，如何取舍？
1.8.1.7 延伸问题
1.用户多了，qps 高了如何处理？
2.数据库存储多了，不够存了如何处理？
3.故障如何处理？单点失败、多点失败、雪崩等问题
1.8.2 系统设计案例-短网址系统设计与实现
1.8.2.1 如何设计与实现一个短网址系统
我们需要考虑下面的几个问题：
1.什么是短网址系统？包含哪些功能（接口）？
2.短网址系统的存储设计？需要存储哪些字段？
3.如何设计算法生成短网址？
1.8.2.2 什么是短网址系统
TinyURL Service，也就是把一个长网址转成短网址的服务。比如 https://bitly.com/（这个网站可以将长网址变成短网址）。转换之后网址的后缀不超过 7 位（字符或者数字）。
1.8.2.3 场景和限制
使用场景：提供短网址服务为公司各业务服务
功能：一个长网址转成短网址并存储；根据短网址还原长 url。
要求：短网址的后缀不超过 7 位（大小写字母和数字）
预估峰值插入请求数量级：数百
查询请求数量级：数千
1.8.2.4 数据存储设计
根据上面的需求，我们使用 MySQL 就可以满足。接下来再思考一下需要的字段有哪些？id 、生成之后的短网址、长网址和生成时间 4 个字段即可。如下：
| id | token | url | created_at |
| 自增长编号 | 短网址生成的 token，不存储整个短网址，因为希望前面的主机名可以随意的替换。此字段建立索引 | 原网址 | 创建时间 |
1.8.2.5 算法实现设计
我们需要考虑短网址生成算法有哪些，然后对比它们的优缺点。
1.首先我们需要提供两个 API 接口。一个是 long2short_url，一个是 short2long_url。
我们既要将长网址生成短网址，又要还原查询到跳转网址。
2.常用算法： hash 算法截取；自增序列算法
3.对比多种算法，我们采取自增序列算法实现
短网址生成算法：
这个问题很抽象，我们可以先进行转化一下。也就是每一个长网址从下面的字符集中生成一个不超过 7 位长度的短网址的 token：
CHARS ="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
再简单点就是 token 里面的每一个字符都来自上面的字符集。
1.md5 摘要算法是否可以呢？毕竟它可以将任意长度的字节，生成一个定长的字符。此算法多用在我们下载文件的时候，会使用 md5 校验值检查文件是不是被修改了。
利用下面的代码实现：
import hashlib hashlib.md5(url.encode()).hexdigest()
大家实验过之后应该会发现它是一个 32 位定长的字符串。但是我们需要 7 位啊？有人会想我们可以截断，比如取前面7个值或者后面7个字符等方式。虽然可以实现，但是会有一定概率的冲突，一旦有冲突，我们在插入的时候还需要去数据库检查一下，这样在高并发的情况下是非常不友好的。
2.如果我们把每一个自增长的 id 生成一个不重复的短网址的 token 呢？想法是不是很美好。我们先来看一下字符集的特点。一共有 62 个字符（ 26 个小写英文，26 个大写英文外加 10 个数字，也就是字符集的长度总和为 62），我们需要生成的 token 最长为 7 位，每一位上面都有 62 种可能性，也就是 62 的 7 次幂，是多大呢？万亿级，足够使用了，nice ~。
如果你仔细观察给出的 CHARS 字符集，你会发现它是一个类似于 62 位进制的数字。如果还是不好理解，我们一步一步来，大家都知道二进制的可选项是 0，1 对吧？十六进制是 0 - 9 加 a - f 。而我们此处的 62 进制可选项就是字符集中字符了，此处当然不是严格的 62 进制这样的数字，而是字符集中 0 到 61 位上的每一个字符都与之对应。
简单的说就是根据自增 id 来给每一个长网址生成一个 62 进制的短网址。下面又有问题了，那就是怎么将 10 进制的 id 转换成 62 进制的短网址呢？
先看一个简单的例子，怎么将 10 进制转化成 2 进制。口诀就是不断取余，倒叙输出。Python 中 bin 这个函数可以进行转化，但是我们不用，我们傲娇，我们要自己用代码实现一下：
def mybin(num): # 10进制 -> 2进制 if num == 0: return 0 res = [] while num: # 如果10进制要转化成62进制，将下面的2改为62即可 num, rem = divmod(num, 2) res.append(str(rem)) return ''.join(reversed(res))
里面涉及到一个函数 divmod，我们先来看一下它的简介，然后再举个例子：
In [1]: divmod? Signature: divmod(x, y, /) Docstring: Return the tuple (x//y, x%y). Invariant: div*y + mod == x. Type: builtin_function_or_method In [2]: divmod(10, 2) Out[2]: (5, 0)
我们可以看到传了两个数之后，返回一个元祖，第一个是取整数，第二个是取余数。
然后编写一段代码，实现 10 进制数字转化为上述字符集 62 进制字符串：
CHARS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" def encode(num): if num == 0: return CHARS[0] res = [] while num: num, rem = divmod(num, len(CHARS)) res.append(CHARS[rem]) return ''.join(reversed(res))
我们将上面的算法称为 递增序列算法，通过这个算法生成短网址。但是还有一个问题，就是数据库只有在插入的时候才有自增 id 。因此我们需要有一个全局的计数器，用来生成自增的 id。计数器可以使用 Redis 的 incr 实现。
下面回顾一下流程：
一个请求过来之后，我们先去 Redis 中拿到 incr 的值，然后将值转化成 62 进制串，最后将其保存到 MySQL 中就可以了。
下面我们使用 flask 实现一个短网址服务：
import os from flask import Flask, jsonify, render_template, request from flask_mysqldb import MySQL from flask.ext.redis import FlaskRedis app = Flask(__name__) app.config['MYSQL_USER'] = 'root' # 此处填写自己电脑的密码 app.config['MYSQL_PASSWORD'] = os.getenv('MYSQL_PASS') app.config['MYSQL_DB'] = 'test' app.config['MYSQL_CURSORCLASS'] = 'DictCursor' mysql = MySQL(app) redis_store = FlaskRedis(app) CHARS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" def encode(num): if num == 0: return CHARS[0] res = [] while num: num, rem = divmod(num, len(CHARS)) res.append(CHARS[rem]) return ''.join(reversed(res)) @app.route('/shorten', methods=['POST']) def shorten_url(): long_url = request.json['url'] index = int(redis_store.incr('SHORT_CNT')) token = encode(index) sql = "INSERT INTO short_url(token, url) VALUES(%s, %s)" cur = mysql.connection.cursor() cur.execute(sql, (token, long_url)) mysql.connection.commit() shourt_url = 'https://short.com/' + token return jsonify(url=short_url) @app.route('/') def index(): return render_template('index.html') if __name__ == '__main__': app.run(debug=True)
数据库所需表：
CREATE TABLE short_url ( id bigint unsigned NOT NULL AUTO_INCREMENT, token varchar(10), url varchar(2048), created_at timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP, PRIMARY KEY (`id`), KEY `idx_token` (`token`) );
前端页面此处不提供，只提供后端代码。
结束语
截止到现在，这一系列的笔记就完成了！当然，这八篇文章不可能面面俱到，只能将一些重点提到，树的枝干有了之后，就看大家去如何丰富了，希望这些笔记对大家有所帮助。每天其实最开心的就是晚上看到后台增长的粉丝数。虽然我只是一个很小的公众号，内容也不是多么精彩，但是我愿意不断的进步，也希望大家随着我一起进步。完全的免费，只有你们的认可才是我坚持下去的动力，所以喜欢就分享出去，让更多的人看到吧。
