这段时刻，在收拾常识星球中面试专栏时看到这么一个字节跳动的二面真题：100Wqps短链体系，怎么规划？
这道题，看上去业务简略，其实，掩盖的常识点十分多：
- 高并发、高功用散布式 ID
- Redis Bloom Filter 高并发、低内存损耗的 过滤组件常识
- 分库、分表海量数据存储
- 多级缓存的常识
- HTTP传输常识
- 二进制、十六进制、六十二进制常识
整体来说，高并发、高功用体系的核心范畴，都掩盖了。所以，陈某剖析下来，得到一个结论：是一个超级好的问题。
1、短URL体系的背景
短网址代替长URL，在互联网网上传达和引证。
例如QQ微博的url.cn，新郎的sinaurl.cn等。
在QQ、微博上发布网址的时分，会主动判别网址，并将其转化，例如：url.cn/2hytQx
为什么要这样做的，无外乎几点：
-
缩短地址长度，留足更多空间的给 有意义的内容
URL是没有意义的，有的原始URL很长，占用有效的屏幕空间。
微博限制字数为140字一条，那么假如这个连接十分的长，以至于将近要占用咱们内容的一半篇幅，这肯定是不能被允许的，链接变短，关于有长度限制的渠道发文，可编辑的文字就变多了， 所以短网址应运而生了。
-
能够很好的对原始URL内容管控。
有一部分网址能够会涵盖XX，暴力，广告等信息，这样咱们能够经过用户的举报，完全管理这个连接将不呈现在咱们的运用中，应为相同的URL经过加密算法之后，得到的地址是一样的。
-
能够很好的对原始URL进行行为剖析
咱们能够对一系列的网址进行流量，点击等核算，挖掘出大多数用户的重视点，这样有利于咱们对项目的后续作业更好的作出决议计划。
-
短网址和短ID适当于直接提高了带宽的运用率、节约成本
-
链接太长在有些渠道上无法主动识别为超链接
-
短链接愈加简练美观且安全，不露出拜访参数。而且，能躲避关键词、域名屏蔽等手段
2、短URL体系的原理
短URL体系的核心：将长的 URL 转化成短的 URL。
客户端在拜访体系时，短URL的作业流程如下：
- 先运用短地址A拜访 短链Java 服务
- 短链Java 服务 进行 地址转化和映射，将 短URL体系映射到对应的长地址URL
- 短链Java 服务 回来302 重定向 给客户端
- 然后客户端再重定向到原始服务
如下图所示：
那么，原始URL怎么变短呢？简略来说， 能够将原始的地址，运用编号进行代替
编号怎么进一步变短呢？ 能够运用更大的进制来表明
重视公众号：码猿技能专栏，回复关键词：1111 获取阿里内部Java功用调优手册
六十二进制表明法
顾名思义短网址便是十分短的网址，比方xxx.cn/EYyCO9T，其间核… EYyCO9T 只要7位长度。
其实这儿的7位长度是运用62进制来表明的，便是常用的0-9、a-z、A-Z，也便是10个数字+26个小写+26个大写=62位。
那么7位长度62进制能够表明多大规划呢?
62^7 = 3,521,614,606,208 (合计3.5万亿)，
阐明：
10进制 最大只能生成 10 ^ 6 - 1 =999999个
16进制 最大只能生成 16 ^ 6 - 1 =16777215个
16进制里边现已包括了 A B C D E F 这几个字母
62进制 最大竟能生成 62 ^ 6 - 1 =56800235583个 基本上够了。
A-Z a-z 0-9 刚好等于62位
留意：
int(4个字节) ，存储的规划是-21亿到21亿
long(8个字节)，存储的规划是-900万万亿 到 900万万亿
至于短网址的长度，能够依据自己需求来调整，假如需求更多，能够添加位数，
即便6位长度62^6也能到达568亿的规划，
这样的话只要算法得当，能够掩盖很大的数据规划。
在编码的过程中，能够依照自己的需求来调整62进制各位代表的意义。
一个典型的场景是， 在编码的过程中，假如不想让人明确知道转化前是什么，能够进行弱加密，
比方A站点将字母c表明32、B站点将字母c表明60，就适当于密码本了。
128进制表明法
规范ASCII 码也叫根底ASCII码，运用7 位二进制数（剩下的1位二进制为0）,包括128个字符，
看到这儿你或许会说，运用128进制(假如有的话)岂不是网址更短，
是的，
7 位二进制数（剩下的1位二进制为0）表明一切的大写和小写字母，数字0 到9、标点符号，以及在美式英语中运用的特殊控制字符 [1] 。
留意：
128个进制就或许会呈现很多的不常用字符
比方 # % & * 这些，
这样的话，关于短链接而言，通用性和记忆性就变差了，
所以，62进制是个权衡折中。
3、短 URL 体系的功用剖析
假设短地址长度为8位，62的8次方足够一般体系运用了
体系核心完结，包括三个大的功用
- 发号
- 存储
- 映射
能够分为两个模块：发号与存储模块、映射模块
发号与存储模块
- 发号：运用发号器发号 ， 为每个长地址分配一个号码ID，而且需求防止地址二义，也便是防止同一个长址屡次恳求得到的短址不一样
- 存储：将号码与长地址存放在DB中，将号码转化成62进制，用于表明终究的短地址，并回来给用户
映射模块
用户运用62进制的短地址恳求服务 ，
- 转化：将62进制的数转化成10进制，由于咱们体系内部是long 类型的10进制的数字ID
- 映射：在DB中寻觅对应的长地址
- 经过302重定向，将用户恳求重定向到对应的地址上
4、发号器的高并发架构
回顾一下发号器的功用：
- 为每个长地址分配一个号码ID
- 而且需求防止地址歧义
以下对现在盛行的散布式ID计划做简略介绍
计划1：运用地址的hash 编码作为ID
能够经过 原始Url的 hash编码，得到一个 整数，作为 短链的ID
哈希算法简略来说便是将一个元素映射成另一个元素，
哈希算法能够简略分类两类，
- 加密哈希，如MD5，SHA256等，
- 非加密哈希，如MurMurHash，CRC32，DJB等。
MD5算法
MD5消息摘要算法（MD5 Message-Digest Algorithm），一种被广泛运用的密码散列函数，
能够产生出一个128位（16字节）的散列值（hash value），
MD5算法将数据（如一段文字）运算变为另一固定长度值，是散列算法的根底原理。
由美国密码学家 Ronald Linn Rivest规划，于1992年揭露并在 RFC 1321 中被加以规范。
CRC算法
循环冗余校验（Cyclic Redundancy Check）是一种依据网络数据包或电脑文件等数据，
产生简短固定位数校验码的一种散列函数，由 W. Wesley Peterson 于1961年宣布。
生成的数字在传输或许存储之前核算出来而且附加到数据后面，然后接收方进行查验确定数据是否发生变化。
由于本函数易于用二进制的电脑硬件运用、简略进行数学剖析而且特别长于检测传输通道搅扰引起的错误，因此取得广泛运用。
MurmurHash
MurmurHash 是一种非加密型哈希函数，适用于一般的哈希检索操作。
由 Austin Appleby 在2008年创造，并呈现了多个变种，与其它盛行的哈希函数相比，关于规律性较强的键，MurmurHash的随机散布特征体现更良好。
这个算法现已被很多开源项目运用，比方libstdc++ (4.6版)、Perl、nginx (不早于1.0.1版)、Rubinius、 libmemcached、maatkit、Hadoop、Redis，Memcached，Cassandra，HBase，Lucene等。
MurmurHash 核算能够是 128位、64位、32位，位数越多，碰撞概率越少。
所以，能够把长链做 MurmurHash 核算，能够得到的一个整数哈希值 ，
所得到的短链，类似于下面的办法
固定短链域名+哈希值 = www.weibo.com/888888888
怎么缩短域名？传输的时分，能够把 MurmurHash之后的数字为10进制，能够把数字转成62进制
www.weibo.com/abcdef
那么，运用地址的hash 编码作为ID的问题是啥呢？
会呈现碰撞，所以这种计划不适合。
计划2：数据库自增长ID
归于完全依靠数据源的办法，一切的ID存储在数据库里，是最常用的ID生成办法，在单体运用时期得到了最广泛的运用，树立数据表时运用数据库自带的auto_increment作主键，或是运用序列完结其他场景的一些自增长ID的需求。
可是这种办法存在在高并发情况下功用问题，要处理该问题，能够经过批量发号来处理，
提前为每台机器发放一个ID区间 [low,high]，然后由机器在自己内存中运用 AtomicLong 原子类去确保自增，削减对DB的依靠，
每台机器，比及自己的区间即将满了，再向 DB 恳求下一个区段的号码，
为了完结写入的高并发，能够引进 队列缓冲+批量写入架构，
等区间满了，再一次性将记载保存到DB中，而且异步进行获取和写入操作, 确保服务的持续高并发。
比方能够每次从数据库获取10000个号码，然后在内存中进行发放，当剩余的号码缺乏1000时，从头向MySQL恳求下10000个号码，在上一批号码发放完了之后，批量进行写入数据库。
可是这种计划，更适合于单体的 DB 场景，在散布式DB场景下， 运用 MySQL的自增主键， 会存在不同DB库之间的ID抵触，又要运用各种办法去处理，
总结一下， MySQL的自增主键生成ID的优缺点和运用场景：
-
优点：
十分简略，有序递增，方便分页和排序。
-
缺点：
分库分表后，同一数据表的自增ID简略重复，无法直接运用（能够设置步长，但局限性很明显）；
功用吞吐量整个较低，假如规划一个单独的数据库来完结 散布式运用的数据仅有性，
即便运用预生成计划，也会由于业务锁的问题，高并发场景简略呈现单点瓶颈。
-
适用场景：
单数据库实例的表ID（包括主从同步场景），部分按天计数的流水号等；
分库分表场景、全体系仅有性ID场景不适用。
所以，高并发场景， MySQL的自增主键，很少用。
计划3：散布式、高功用的中心件生成ID
Mysql 不可，能够考虑散布式、高功用的中心件完结。
比方 Redis、MongoDB 的自增主键，或许其他 散布式存储的自增主键，可是这就会引进额外的中心组件。
假如运用Redis，则经过Redis的INCR/INCRBY自增原子操作命令，能确保生成的ID肯定是仅有有序的，本质上完结办法与数据库一致。
可是，超高并发场景，散布式自增主键的出产功用，没有本地出产ID的功用高。
总结一下，散布式、高功用的中心件生成ID的优缺点和运用场景：
-
优点：
整体吞吐量比数据库要高。
-
缺点：
Redis实例或集群宕机后，找回最新的ID值有点困难。
-
适用场景：
比较适合计数场景，如用户拜访量，订单流水号（日期+流水号）等。
计划4：UUID、GUID生成ID
UUID：
依照OSF制定的规范核算，用到了以太网卡地址、纳秒级时刻、芯片ID码和许多或许的数字。由以下几部分的组合：当时日期和时刻(UUID的第一个部分与时刻有关，假如你在生成一个UUID之后，过几秒又生成一个UUID，则第一个部分不同，其余相同)，时钟序列，全局仅有的IEEE机器识别号（假如有网卡，从网卡取得，没有网卡以其他办法取得）
GUID：
微软对UUID这个规范的完结。UUID还有其它各种完结，不止GUID一种，不一一列举了。
这两种归于不依靠数据源办法，真实的全球仅有性ID
总结一下，UUID、GUID生成ID的优缺点和运用场景：
-
优点：
不依靠任何数据源，自行核算，没有网络ID，速度超快，而且全球仅有。
-
缺点：
没有次序性，而且比较长（128bit），作为数据库主键、索引会导致索引效率下降，空间占用较多。
-
适用场景：
只要对存储空间没有苛刻要求的都能够适用，比方各种链路追寻、日志存储等。
办法5：snowflake算法（雪花算法）生成ID
snowflake ID 严格来说，归于 本地出产 ID，这点和 Redis ID、MongoDB ID不同， 后者归于长途出产的ID。
本地出产ID功用高，长途出产的ID功用低。
snowflake ID原理是运用Long类型（64位），依照一定的规则进行分段填充：时刻（毫秒级）+集群ID+机器ID+序列号，每段占用的位数能够依据实际需求分配，其间集群ID和机器ID这两部分，在实际运用场景中要依靠外部参数装备或数据库记载。
总结一下，snowflake ID 的优缺点和运用场景：
-
优点：
高功用、低推迟、去中心化、按时刻整体有序
-
缺点：
要求机器时钟同步（到秒级即可），需求处理 时钟回拨问题
假如某台机器的体系时钟回拨，有或许形成 ID 抵触，或许 ID 乱序。
-
适用场景：
散布式运用环境的数据主键
高并发ID的技能选型
这儿，不用地址的hash 编码作为ID
这儿，不用数据库的自增长ID
这儿，不用redis、mongdb的散布式ID
终究，
这儿，从发号功用、整体有序（B+树索引结构愈加友好）的视点动身，终究挑选的snowflake算法
snowflake算法的吞吐量在 100W ops +
可是 snowflake算法 问题是啥呢？需求处理时钟回拨的问题。
怎么处理时钟回拨的问题，能够参阅 推特官方的 代码、 百度ID的代码、Shardingjdbc ID的源码，综合存储计划规划处理。
5、数据存储的高并发架构
这个数据，十分的结构化，能够运用结构化数据库MYSQL存储。
结构十分简略，咱们会有二列：
1. ID，int, // 散布式雪花id；
2. SURL，varchar, // 原始URL；
接下来，开端高并发、海量数据场景，需求进行 MYSQL存储 的分库分表架构。
陈某提示，这儿能够说说自己的分库分表 操作经历，操作案例。
然后进行 互动式作答。
也便是，首先是进行 输入条件 问询，而且进行承认。
然后依照分治模式，进行两大维度的剖析架构：
- 数据容量（存储规划） 的 分治架构、
- 拜访流量 （吞吐量规划）的 分治架构。
这块内容涉的计划，不同的项目，基本是相通的。
6、二义性查看的高并发架构
所谓的地址二义性，就行同一个长址屡次恳求得到的短址不一样。
在出产地址的时分，需求进行二义性查看，防止每次都会从头为该长址生成一个短址，一个个长址屡次恳求得到的短址是不一样。
经过二义性查看，完结长短链接真实意义上的一对一。
怎么进行 二义性查看？
最简略，最为粗犷的计划是：直接去数据库中查看。
可是，这就需求付出很大的功用价值。
要知道：
数据库主键不是 原始url，而是 短链url 。
假如依据 原始url 去进行存在性查看，还需求额外树立索引。
问题的关键是，数据库功用特低，没有办法支撑超高并发 二义性查看
所以，这儿肯定不能每次用数据库去查看。
这儿很多同学或许会想到另一种计划，便是 redis 的布隆过滤， 把现已生成过了的 原始url，
大致的计划是，能够把现已生成过的 原始url ，在 redis 布隆过滤器中进行记载。
每次进行二义性查看，走redis 布隆过滤器。
布隆过滤器便是bitset+屡次hash的架构，微观上是空间换时刻，不对一切的 surl （原始url）进行内容存储，只对surl进行存在性存储，这样就节约大家很多的内存空间。
在数据量比较大的情况下，既满意时刻要求，又满意空间的要求。
布隆过滤器的常用运用场景如下：
- 黑名单 : 反废物邮件，从数十亿个废物邮件列表中判别某邮箱是否废物邮箱（同理，废物短信）
- URL去重 : 网页爬虫对 URL 的去重，防止爬取相同的 URL 地址
- 单词拼写查看
- Key-Value 缓存体系的 Key 校验 (缓存穿透) : 缓存穿透，将一切或许存在的数据缓存放到布隆过滤器中，当黑客拜访不存在的缓存时迅速回来防止缓存及 DB 挂掉。
- ID 校验，比方订单体系查询某个订单 ID 是否存在，假如不存在就直接回来。
Bloom Filter 专门用来处理咱们上面所说的去重问题的，运用 Bloom Filter 不会像运用缓存那么浪费空间。
当然，他也存在一个小小问题，便是不太准确。
规则是：存在不一定存在，说不存在一定不存在
Bloom Filter 适当所以一个不太准确的 set 调集，咱们能够运用它里边的 contains 办法去判别某一个对象是否存在，可是需求留意，这个判别不是特别准确。
一般来说，经过 contains 判别某个值不存在，那就一定不存在，可是判别某个值存在的话，则他或许不存在。
那么关于 surl，处理的计划是：
- 假如 redis bloom filter 不存在，直接生成
- 否则，假如 redis bloom filter 判别为存在，或许是误判，还需求进行db的查看。
可是， redis bloom filter误判的概率很低，合理优化之后，也就在1%以下。
或许有小伙伴说，假如100Wqps，1%也是10W1ps，DB仍是扛不住，怎么办？
能够运用缓存架构，乃至多级缓存架构
详细来说，能够运用 Redis 缓存进行 抢手url的缓存，完结部分地址的一对一缓存
比方将最近/最抢手的对应联系存储在K-V数据库中，比方在本地缓存 Caffeine中存储最近生成的长对短的对应联系，并选用过期机制完结 LRU 筛选，从而确保频频运用的 URL 的总是对应同一个短址的，可是不确保不频频运用的URL的对应联系，从而大大削减了空间上的耗费。
7、映射模块(/转化模块)高并发架构
这儿，主要是介绍自己对 多级缓存的 掌握和了解。
能够运用了缓存，二级缓存、三级缓存，加速id 到 surl的转化。
简略的缓存计划
将抢手的长链接（需求对长链接进来的次数进行计数）、最近的长链接（能够运用 Redis 保存最近一个小时的数据）等等进行一个缓存，假如恳求的长URL命中了缓存，那么直接获取对应的短URL进行回来，不需求再进行生成操作
弥补服务间的重定向301 和 302 的不同
301永久重定向和 302 暂时重定向。
- 301永久重定向：第一次恳求拿到长链接后，下次浏览器再去恳求短链的话，不会向短网址服务器恳求了，而是直接从浏览器的缓存里拿，削减对服务器的压力。
- 302暂时重定向：每次去恳求短链都会去恳求短网址服务器（除非响应中用 Cache-Control 或 Expired 暗示浏览器进行缓存）
运用 301 虽然能够削减服务器的压力，可是无法在 server 层获取到短网址的拜访次数了，假如链接刚好是某个活动的链接，就无法剖析此活动的作用以及用于大数据剖析了。
而 302 虽然会添加服务器压力，但便于在 server 层核算拜访数，所以假如对这些数据有需求，能够选用 302，由于这点价值是值得的，可是详细选用哪种跳转办法，仍是要结合实际情况进行选型。
8、架构的魅力
架构魅力，在于没有最好的计划，只要更好的计划，大家假如有疑问，或许更好的计划，能够多多沟通。
