1. 系统设计

• 什么是系统设计
• 系统设计需要掌握哪些知识
• 如何设计和实现一个后端系统服务的设计

系统设计是一个初高级中工程师的必经之路，一个好的后端工程师不会系统设计，不是一个优秀的工程师。什么是系统设计（System Design）

• 系统设计是一个定义系统架构、模块、接口和数据满足特定需求的过程
• 比如设计一个短网址服务、评论服务、Feed 流系统、抢红包系统等
• 微服务架构很多系统被安装业务拆分，需单独设计一个系统服务

系统设计的难点

• 需要具备相关领域、算法的经验，有一定的架构设计能力
• 熟悉后端技术组件，如：消息队列、缓存、数据库、框架等
• 具备文档撰写、流程图绘制、架构设计。编码实现等综合能力

1.1 系统设计题目怎么回答

系统设计三大要素：

• 使用场景和限制条件
• 数据存储设计
• 算法模块设计

遵守三个要素回答，包含数据表的设计、api 的设计、算法的设计，最好图文并茂，有数据表、接口定义，流程图等。

如：面试官问你怎样设计一个短网址系统？

1、问面试官：什么场景和条件下使用？

• 这个系统是在什么地方使用的？比如短网址系统提供给站内各种服务生成短网站
• 限制条件：用户估计有多少？至少要能支撑多少用户（服务）？
• 估算并发 qps：峰值 qps 是多少？评价 qps 是多少？

2、设计数据存储系统

• 按需设计数据表，需要哪些字段，使用什么类型？数据增长规模
• 数据库选型：是否需要持久化？使用关系型还是 NoSQL？
• 如何优化？如何设计索引？是否可以使用缓存？

3、设计算法相关模块

算法解决问题的核心，程序=算法+数据结构，系统=服务+存储

• 需要哪些接口？接口如何设计？
• 使用什么算法或模型？
• 不同实现方式之间的优劣对比，如何取舍？

延伸

• 用户多了，qps 高了如何处理？
• 数据存储多了不够存储了如何处理？
• 故障如何处理？单点失败、多点失败、雪崩问题等。

2. 短网址系统设计

首先我们先要明确要设计的系统最基本最核心的东西：

• 什么是短网址系统？包含哪些功能（接口）
• 短网址系统的存储设计？需要存储哪些字段？
• 如何设计算法生成短网址

2.1 什么是短网址系统

短网址系统（网站：TinyUrl Service）：

• 把一个长网站转换成短网址的服务，如：https://bitly.com/
• 转换之后网址的后缀不超过 7 位（字符或数字）

使用场景和限制

• 提供短网址服务为公司其他各业务服务
• 功能：一个长网站转换成短网址并存储，根据短网址还原长网址
• 要求短网址的后缀不超过 7 位（大小写字母和数字）
• 预估峰值插入请求数量级：数百；查询请求数量级：数千

2.2 存储设计

根据上面的场景和限制条件，使用 MySQL 存储即可。还需要明确：

• 需要的字段：id、token（短网址）、url（原网站）、created_at（创建时间）
• 如何根据查询设计索引？

CREATE TABLE short_url(
    id BIGINT UNSIGNED NOT NULL PRIMARY KEY auto_increment,
    token VARCHAR(10),
    url VARCHAR(2048),
    created_at TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
    INDEX tk (token)
);

2.3 算法设计

短网址生成的算法有哪些？优缺点：long2short_url、short2long_url

方法一：

md5 摘要算法（转换为定长的字符串），取前 7 个字符（缺点：可能会冲突）

方法二：

类似于 62 进制的数字，根据自增 ID 生成短网址（即自增序列算法），同时使用 Redis 实现一个计数器

26 个小写字母+26个大写字母+10个数字，总共62种可能，总共有 7 位，每一位有 72 种可能，那么总共就是有 62^7 种可能，就不会重复了。

根据自增 ID，给每一个长网址生成一个 62 位的短网址

def mybin(num):
    """10进制 ——> 2 进制"""
    if num == 0:
        return 0
    res = []
    while num:
        num, rem = divmod(num, 2)   # 商和余数
        res.append(str(rem))
    return ''.join(reversed(res))       # num：10，return：1010

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))

print(encode(1))
print(encode(61))

image

最终版：

import os
import redis

from flask import Flask, jsonify, render_template, request
from flask_mysqldb import MySQL
from flask_redis import FlaskRedis


app = Flask(__name__)
app.config['MYSQL_USER'] = 'root'
# app.config['MYSQL_PASSWORD'] = os.getenv('MYSQL_PASS')
app.config['MYSQL_PASSWORD'] = 'abxxx0139'
app.config['MYSQL_DB'] = 'test'
app.config['MYSQL_CURSORCLASS'] = 'DictCursor'

mysql = MySQL(app)
redis_client = FlaskRedis(app)

CHARS = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'


# redis 建立一个链接池避免每次建立，释放连接的开销
try:
    pool = redis.ConnectionPool(host='192.168.2x.128', port=6379)
    print("连接成功")
except:
    print("could not connect to redis.")
finally:
    r = redis.Redis(connection_pool=pool)


def encode(num):
    """
    将 10 进制转换为 62 进制, len(CHARS) = 62
    :param num: redis 计数器中的数（十进制），也是 MySQL id
    :return:
    """
    if num == 0:
        return CHARS[0]
    res = []
    while num:
        # 返回商和余数
        num, rem = divmod(num, len(CHARS))
        # 从 CHARS 取出匹配的字符/数字，再将余数添加到列表中，
        res.append(CHARS[rem])
    # 拼接成字符串
    return ''.join(reversed(res))


@app.route('/shorten', methods=['POST'])
def shorten_url():
    long_url = request.form['long_url']
    # 用 redis 作一个计数器，存储类型 str，key 为 SHORT_CNT，每次自增 1
    index = int(r.incr('SHORT_CNT'))        # 1 、2 、3 、4... 总共可以有 1-62^7 个数字 
    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()
    short_url = 'https://short.com/' + token
    return jsonify(url=short_url)


@app.route("/")
def index():
    short_url = 'hdd'
    return render_template('index.html', short_url=short_url)

if __name__ == '__main__':
    app.run(debug=1)

[图片上传失败...(image-f585b0-1593096242987)]

2.4 思考：如何设计一个秒杀系统

• 什么是秒杀系统，你又使用过？
• 如何根据三要素来设计？
• 秒杀系统设计到哪些后端组件？
• 如何使用消息队列削峰

主要从几方面入手：

• 使用内存，而不是写入硬盘：redis
• 异步处理而不是同步处理：消息队列削峰
• 分布式处理：分不到多台服务器
• 多个交换机
• docker 技术
• 前端限流（同一个 IP，一秒钟之类只能访问一次）

流程：

• 校验库存
• 扣库存
• 创建订单
• 支付

3. 面试题

1、将一个字符串逆序，不能使用反转函数

>>> s = 'abc'
>>> s[::]
'abc'
>>> s[::-1]
'cba'

2、求从10到100中能被3或5整除的数的和

sum = 0
for i in range(10, 100):
    if i % 3 ==0 or i % 5 == 0:
        sum += i
        
print(sum)

3、什么是 PE8？

Python 八荣八耻，一种代码规范

4、请用自己的算法, 按升序合并如下两个list, 并去除重复的元素

list1 = [2, 3, 8, 4, 9, 5, 6]
list2 = [5, 6, 10, 17, 11, 2]

list1 = [2, 3, 8, 4, 9, 5, 6]
list2 = [5, 6, 10, 17, 11, 2]
list3 = list1 + list2
print(sorted(list(set(list3))))

5、写一个简单的python socket编程

6、请描述set的用途并举例说明

创建一个无序不重复元素集，可进行关系测试，删除重复数据，还可以计算交集、差集、并集等。

scrapy 去除重复 URL。

7、请简述python2.x 与python3.x的主要区别

• Python2：print、Unicode编码格式、xrange()（生成器）、raw_input()
• Python3：print()、UTF-8、range()、没有长整型 long，只有 int、input()

8、简述python新式类和旧式类的区别

• 当类是经典类时，多继承按照深度优先查找
• 当类是新式类时（Python 3.x 都是新式类），多继承按照广度优先查找

9、Python里面 search() 和match()的区别？

• match()：从第一个开始匹配
• search()：全局，找到访问第一个

10、请简述线程＼进程＼协程的特性

• 进程是资源分配的最小单位，切换需要的资源很大，效率很低
• 线程是操作系统调度的最小单位，一个程序至少有一个进程，一个进程至少有一个线程，开销小，但不利于资源的管理和保护，而进程刚好相反
• 协程，又称微线程，纤程，协程的切换只是单纯的操作CPU的上下文，资源很小，效率高

11、请简述你对 python 闭包的理解

在一个内部函数里，对在外部作用域（但不是全局作用域）的变量进行引用，那么这个内部函数就是闭包（closure）。

def fun1(x):
    def fun2(y):
        return x * y
    return fun2
a = fun1(6)         # a 接收的是 fun2() 的内存地址
print(a)
b = a(5)            # a(5) 相当于调用 fun2（）
print(b)

# 上述可以简写
# res = fun1(6)(5)
# print(res)

<function fun1.<locals>.fun2 at 0x00000000026F48C8>
30

不能在外部函数中调用内部函数变量，除非使用 nonlocal

12、解释一下 Django 和 Tornado 的关系、差别

Django：大而全（重量级框架），基本什么都有，也可以拓展第三方插件，如：xadmin、django-redis，注重高效开发，开发速度快。缺点：臃肿、自身模板系统不怎么好用。

Tornado：异步非阻塞 Web 框架，速度快，（得益于非阻塞和 epoll 的运用），每秒可以处理数以千计的连接，是一个理想的 Web 框架。高并发、注重性能。

要性能， Tornado 首选；要开发速度，Django 和 Flask 都行，区别是 Flask 把许多功能交给第三方库去完成了，因此 Flask 更为灵活。

13、解释下 HTTP 协议
HTTP是一个属于应用层的面向对象的协议，由于其简捷、快速的方式，适用于分布式超媒体信息系统。
HTTP协议的主要特点可概括如下：

• 支持客户、服务器模式。
• 简单快速：客户向服务器请求服务时，只需传送请求方法和路径。请求方法常用的有GET、HEAD、POST。每种方法规定了客户与服务器联系的类型不同。由于HTTP协议简单，使得HTTP服务器的程序规模小，因而通信速度很快。
• 灵活：HTTP允许传输任意类型的数据对象。正在传输的类型由Content-Type加以标记。
• 无连接：无连接的含义是限制每次连接只处理一个请求。服务器处理完客户的请求，并收到客户的应答后，即断开连接。采用这种方式可以节省传输时间。
• 无状态：HTTP协议是无状态协议。无状态是指协议对于事务处理没有记忆能力。缺少状态意味着如果后续处理需要前面的信息，则它必须重传，这样可能导致每次连接传送的数据量增大。另一方面，在服务器不需要先前信息时它的应答就较快。

13、静态属性、静态方法、类方法

• 静态属性（@property）：可以是实例对象在调用函数属性时，可以像调用数据属性一样
• 静态方法（@staticmethod）：如果有想在类中定义一个函数，要求该函数的参数与类、实例都无关（没有绑定），我们可以使用静态方法 @staticmethod。

class Room:
    @staticmethod
    def close_door(position, color):
        print('请关闭 %s 的 %s 小门' % (position, color))

• 类方法（@classmethod）：如果不进行实例化，直接用类名调用类的函数属性，会报缺少位置参数:

@classmethod
def open_door(cls, color):
    print(cls)      # cls 相当于 类本身，在定义类方法时自动补全
    print('请打开那扇 %s 的 %s门' % (color, cls.size))

14、迭代器和生成器，它们有什么区别？

• 生成器：yield（生成器函数）、生成器表达式（将列表推导式的中括号换成小括号），也可以用 next() 方法获取下一个元素，是创建迭代器的简单而强大的工具。生成器能做到迭代器能做的所有事,而且因为自动创建了iter()和next()方法,生成器显得特别简洁,而且生成器也是高效的，使用生成器表达式取代列表解析可以同时节省内存。除了创建和保存程序状态的自动方法,当发生器终结时,还会自动抛出StopIteration异常
• 迭代器：对象必须提供一个 next() 方法，执行该方法要么迭代下一项，要么就引起一个 StopIteration异常以终止迭代（只能往后不能往前）。
• for 循环迭代一个数组时，Python 解释器会先判断这个数组是不是一个 iterable object 可迭代对象，如果是会将其转换为 iterator object 迭代器，才能实现迭代（要获取数据需要是迭代器才能完成）。
• 可迭代对象：类中实现了 __iter()__ 方法
• 迭代器对象：实现了 __iter()__ 和 __next__() 方法
• 应用场景：比如斐波拉契数列，可能你需要知道的只是第 1000 个元素是什么，而不关心前面 999 个元素是什么，如果用列表，就需要创建保存 999 个元素才能得到第 1000 个，浪费资源。递归深度有限制。迭代器它不会把每次生成的值保存起来，而是根据算法生成下一个值，节省资源。

def fib():
    """
    1,1,2,3,5,8,13,21....
    :return:
    """
    a = 0
    b = 1
    while True:
        a, b = b, a+b
        yield a

for each in fib():
    if each > 50:
        break
    print(each)

15、谈下python的GIL

GIL 是python的全局解释器锁，同一进程中假如有多个线程运行，一个线程在运行python程序的时候会霸占python解释器（加了一把锁即GIL），使该进程内的其他线程无法运行，等该线程运行完后其他线程才能运行。如果线程运行过程中遇到耗时操作，则解释器锁解开，使其他线程运行。所以在多线程中，线程的运行仍是有先后顺序的，并不是同时进行。

多进程中因为每个进程都能被系统分配资源，相当于每个进程有了一个python解释器，所以多进程可以实现多个进程的同时运行，缺点是进程系统资源开销大

16、Python 垃圾回收机制

以引用计数为主，标记-清除和分代清除为辅的机制，其中标记-清除和分代回收主要是为了处理循环引用的难题。

引用计数算法：当有1个变量保存了对象的引用时，此对象的引用计数就会加1

当使用del删除变量指向的对象时，如果对象的引用计数不为1，比如3，那么此时只会让这个引用计数减1，即变为2，当再次调用del时，变为1，如果再调用1次del，此时会真的把对象进行删除