这段时刻，在收拾常识星球中面试专栏时看到这么一个字节跳动的二面真题：100Wqps短链体系，怎么规划？

这道题，看上去业务简略，其实，掩盖的常识点十分多：

  • 高并发、高功用散布式 ID
  • Redis Bloom Filter 高并发、低内存损耗的 过滤组件常识
  • 分库、分表海量数据存储
  • 多级缓存的常识
  • HTTP传输常识
  • 二进制、十六进制、六十二进制常识

整体来说，高并发、高功用体系的核心范畴，都掩盖了。所以，陈某剖析下来，得到一个结论：是一个超级好的问题。

1、短URL体系的背景

短网址代替长URL，在互联网网上传达和引证。

例如QQ微博的url.cn，新郎的sinaurl.cn等。

在QQ、微博上发布网址的时分，会主动判别网址，并将其转化，例如：url.cn/2hytQx

为什么要这样做的，无外乎几点：

  1. 缩短地址长度，留足更多空间的给 有意义的内容

    URL是没有意义的，有的原始URL很长，占用有效的屏幕空间。

    微博限制字数为140字一条，那么假如这个连接十分的长，以至于将近要占用咱们内容的一半篇幅，这肯定是不能被允许的，链接变短，关于有长度限制的渠道发文，可编辑的文字就变多了， 所以短网址应运而生了。

  2. 能够很好的对原始URL内容管控。

    有一部分网址能够会涵盖XX，暴力，广告等信息，这样咱们能够经过用户的举报，完全管理这个连接将不呈现在咱们的运用中，应为相同的URL经过加密算法之后，得到的地址是一样的。

  3. 能够很好的对原始URL进行行为剖析

    咱们能够对一系列的网址进行流量，点击等核算，挖掘出大多数用户的重视点，这样有利于咱们对项目的后续作业更好的作出决议计划。

  4. 短网址和短ID适当于直接提高了带宽的运用率、节约成本

  5. 链接太长在有些渠道上无法主动识别为超链接

  6. 短链接愈加简练美观且安全，不露出拜访参数。而且，能躲避关键词、域名屏蔽等手段

2、短URL体系的原理

短URL体系的核心：将长的 URL 转化成短的 URL。

客户端在拜访体系时，短URL的作业流程如下：

  • 先运用短地址A拜访 短链Java 服务
  • 短链Java 服务 进行 地址转化和映射，将 短URL体系映射到对应的长地址URL
  • 短链Java 服务 回来302 重定向 给客户端
  • 然后客户端再重定向到原始服务

如下图所示：

100Wqps短链系统，怎么设计？

那么，原始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存储 的分库分表架构。

陈某提示，这儿能够说说自己的分库分表 操作经历，操作案例。

然后进行 互动式作答。

也便是，首先是进行 输入条件 问询，而且进行承认。

然后依照分治模式，进行两大维度的剖析架构：

  • 数据容量（存储规划） 的 分治架构、
  • 拜访流量 （吞吐量规划）的 分治架构。

100Wqps短链系统，怎么设计？

这块内容涉的计划，不同的项目，基本是相通的。

6、二义性查看的高并发架构

所谓的地址二义性，就行同一个长址屡次恳求得到的短址不一样。

在出产地址的时分，需求进行二义性查看，防止每次都会从头为该长址生成一个短址，一个个长址屡次恳求得到的短址是不一样。

经过二义性查看，完结长短链接真实意义上的一对一。

怎么进行 二义性查看？

最简略，最为粗犷的计划是：直接去数据库中查看。

可是，这就需求付出很大的功用价值。

要知道：

数据库主键不是 原始url，而是 短链url 。

假如依据 原始url 去进行存在性查看，还需求额外树立索引。

问题的关键是，数据库功用特低，没有办法支撑超高并发 二义性查看

所以，这儿肯定不能每次用数据库去查看。

这儿很多同学或许会想到另一种计划，便是 redis 的布隆过滤， 把现已生成过了的 原始url，

大致的计划是，能够把现已生成过的 原始url ，在 redis 布隆过滤器中进行记载。

每次进行二义性查看，走redis 布隆过滤器。

布隆过滤器便是bitset+屡次hash的架构，微观上是空间换时刻，不对一切的 surl （原始url）进行内容存储，只对surl进行存在性存储，这样就节约大家很多的内存空间。

在数据量比较大的情况下，既满意时刻要求，又满意空间的要求。

100Wqps短链系统，怎么设计？

100Wqps短链系统，怎么设计？
布隆过滤器的巨大用处便是，能够迅速判别一个元素是否在一个调集中。

布隆过滤器的常用运用场景如下：

  1. 黑名单 : 反废物邮件，从数十亿个废物邮件列表中判别某邮箱是否废物邮箱（同理，废物短信）
  2. URL去重 : 网页爬虫对 URL 的去重，防止爬取相同的 URL 地址
  3. 单词拼写查看
  4. Key-Value 缓存体系的 Key 校验 (缓存穿透) : 缓存穿透，将一切或许存在的数据缓存放到布隆过滤器中，当黑客拜访不存在的缓存时迅速回来防止缓存及 DB 挂掉。
  5. 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、架构的魅力

架构魅力，在于没有最好的计划，只要更好的计划，大家假如有疑问，或许更好的计划，能够多多沟通。