这段时间整理知识星球面试专栏的时候，看到了这么一个字节跳动的双面真题：100Wqps的短链系统，怎么设计？这道题看似简单的业务，其实涵盖了很多知识点：高并发、高性能分布式IDRedisBloomFilter、高并发、低内存损耗过滤器组件知识分库、分表海量数据存储多级缓存知识HTTP传输知识二进制、十六进制、六十进制知识总的来说涵盖了高并发、高性能系统的核心领域。于是，Chen分析了一下，得出了一个结论：超级好的一道题。一、短网址体系的背景短网址取代长网址，在互联网上被广泛传播和引用。比如QQ微博的url.cn，新郎的sinaurl.cn等。在QQ和微博上发布网址时，会自动判断并转换网址，例如：url.cn/2hytQx为什么要这样做，无外乎几点：缩短地址长度并留出更多空间提供有意义的内容URL没有意义，一些原始URL很长，占用了有效的屏幕空间。微博的字数限制在140个字以内，如果链接太长，占据了我们一半的内容，那是绝对不允许的。链接将被缩短。对于有长度限制的平台，可以编辑的文字变多，于是短网址应运而生。它可以很好地控制原始URL的内容。有些网址可能会覆盖XX、暴力、广告等信息，这样我们可以通过用户的举报完全管理这个链接，不会出现在我们的应用中。应该是同一个URL经过加密算法后，得到的地址是相同的。能够很好的分析出原始URL的行为。我们可以对一系列网址的访问量和点击量进行统计，挖掘出大部分用户的关注点，有助于我们对项目的后续工作做出更好的决策。短网址和短ID相当于间接提高了带宽利用率，节约了成本。过长的链接在某些平台上无法自动识别为超链接。短链接更简洁、美观、安全，不暴露访问参数。并且可以避开关键词、域名拦截等手段。2、短网址系统原理短网址系统的核心：将长网址转化为短网址。客户端访问系统时，短URL的工作流程如下：首先，使用短地址A访问短链Java服务。短链Java服务进行地址转换和映射，将短URL系统映射到对应的长地址URL。短链Java服务返回302重定向到客户端，然后客户端再重定向到原服务如下图：那么，如何缩短原URL呢？简单的说，原来的地址可以用数字代替。如何进一步缩短这个数字？可以使用更大的基数来表示六十二记法。shortURL顾名思义就是很短的网址，比如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^6-1=999999十六进制最多只能生成16^6-1=16777215个十六进制其中已经包含ABCDEF这62个字母16进制最多可以生成62^6-1=56800235583基本够用了。A-Za-z0-9正好等于62位注：int（4字节），存储范围-21亿到21亿long（8字节），存储范围-900万到900万至于长度短网址，您可以根据自己的需要进行调整。如果需要更多，可以增加位数。即使6位的长度是62^6，也能达到568亿的范围。在这种情况下，只要算法得当，就可以覆盖大量的URL。数据范围。在编码的过程中，可以根据自己的需要调整base62的各个代表的含义。一个典型的场景是，在编码过程中，如果不想让人知道转换前到底是什么，可以进行弱加密。比如A站点用字母c代表32，B站点用字母c代表60，相当于一个码本up。HexadecimalnotationStandardASCIIcode也叫basicASCII码，使用7位二进制数（剩下1个二进制位为0），包括128个字符，这里你可能会说，使用128位系统（如果有的话）的URL更短一点，是的，7位二进制数字（剩下的1位二进制为0）代表所有大小写字母，数字0到9，标点符号，以及特殊的Control字符[1]。注意：128个碱基中可能会出现大量#%&*等生僻字符。在这种情况下，对于短链接来说，通用性和记忆性都会变差。因此，62个碱基是一种权衡。3、短网址系统功能分析假设短网址的长度为8位，62的8次方就够了。一般系统采用系统核心实现，包括三大功能。存储模块、映射模块发行和存储模块发行：使用数字生成器为每个长地址分配一个数字ID，需要防止地址歧义，即防止多次请求同一个长地址。不同地址存储：将数字和长地址存储在DB中，将数字转换成16进制表示最终的短地址，返回给用户映射模块。用户使用16进制短地址请求服务，转换：将62进制数转换成十进制数，因为我们系统是long类型的十进制数字ID映射：在DB中找到对应的长地址，重定向用户通过302重定向请求到对应地址4.发号器高并发架构回顾发号器的功能：为每个长地址分配一个号码ID，需要防止地址歧义。下面简单介绍一下目前流行的分布式ID方案。方案一：使用地址Hash编码作为ID，可以通过对原始Url的Hash编码得到一个整数。短链ID哈希算法只是将一个元素映射到另一个元素。哈希算法可以简单分为两类，加密哈希，如MD5、SHA256等，非加密哈希，如MurMurHash、CRC32、DJB等。MD5算法MD5消息摘要算法（MD5Message-DigestAlgorithm），一种广泛使用的密码学哈希函数，可以生成一个128位（16字节）的哈希值（hashvalue），MD5算法将数据（如一段文本）运算成为另一个定长值，即哈希算法的基本原理。由美国密码学家RonaldLinnRivest设计，于1992年发表，在RFC1321中指定。CRC算法循环冗余校验（CyclicRedundancyCheck）是一种哈希函数，它根据网络数据包或计算机文件。它由W.WesleyPeterson于1961年出版。在传输或存储之前计算结果数字并将其附加到数据，接收方检查数据是否已更改。该函数应用广泛，因为它易于与二进制计算机硬件一起使用，易于进行数学分析，尤其擅长检测传输信道干扰引起的错误。MurmurHashMurmurHash是一种非加密哈希函数，适用于一般的哈希检索操作。MurmurHash由AustinAppleby于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后面的数字转换成十进制，数字可以转换成62。www.weibo.com/abcdef那么，用地址的哈希码作为ID有什么问题呢？会有碰撞，所以这个方案不适合。方案二：数据库自增长ID完全依赖数据源。所有ID都存储在数据库中，这是最常用的ID生成方式。使用auto_increment作为主键，或者在其他场景下使用sequence来完成一些自增ID的需求。但是这种方式在高并发情况下存在性能问题。解决这个问题，可以通过批量发号来解决。预先给每台机器下发一个ID范围[low,high]，然后机器在自己的内存中使用AtomicLong。原子类保证自增，减少对DB的依赖。每台机器都等到自己的section快满了，然后向DB请求下一个section的编号。为了实现写入的高并发，可以引入队列缓冲+批处理的写入结构，等待间隔满，然后一次性将记录存入DB，异步进行fetch和write操作，保证连续高服务的并发性。比如每次可以从数据库中取10000个数，然后在内存中下发。当剩余数少于1000时，可以再向MySQL请求10000个数。最后一批号码发出后，分批写入数据库。不过这种方案更适合单DB场景。在分布式DB场景下，使用MySQL的自增主键会造成不同DB库之间的ID冲突，需要通过各种方法来解决。总结一下，MySQL自增主键ID生成的优缺点及使用场景：优点：非常简单，递增有序，方便分页排序。缺点：数据库分表后，同一个数据表的自增ID容易重复，不能直接使用（步长可以设置，但局限性明显）；整体性能吞吐量低，如果设计单独的数据库来实现分布式，即使针对应用的数据唯一性采用预生成方案，在高并发场景下也容易出现单点瓶颈，因为事务锁的问题。适用场景：单个数据库实例的表ID（包括主从同步场景），一些按天统计的序号等；分库分表场景，全系统唯一ID场景不适用。所以在高并发场景下，MySQL的自增主键很少用到。方案三：分布式、高性能的中间件不能生成IDMysql，可以考虑分布式、高性能的中间件。比如Redis的自增主键，MongoDB，或者其他分布式存储的自增主键，但是这会引入额外的中间组件。如果使用Redis，Redis的INCR/INCRBY自增原子操作命令可以保证生成的ID必须唯一且有序，实现方式与数据库基本一致。但是在超高并发场景下，分布式自增主键的生产性能没有本地生产ID高。综上所述，分布式、高性能中间件ID生成的优缺点及使用场景：优点：整体吞吐量高于数据库。缺点：Redis实例或集群宕机后，获取最新的ID值有点困难。适用场景：比较适合统计场景，比如用户访问量，订单流水号（日期+流水号）等方案4：UUID和GUID生成IDUUID：按照OSF制定的标准计算，使用以太网卡地址、纳秒时间、芯片ID代码和许多可能的数字。以下部分的组合：当前日期和时间（UUID的第一部分与时间有关，如果生成UUID后几秒后生成UUID，则第一部分不同，其余相同），时钟Sequence，全球唯一的IEEE机器标识号（如果有网卡，从网卡获取，如果没有网卡，通过其他方式获取）GUID：微软的UUID标准实现。UUID还有其他各种实现方式，不仅仅是GUID，就不一一列举了。这两种方法不依赖于数据源。真正的全球唯一ID总结了UUID和GUID生成ID的优缺点和使用场景：优点：不依赖任何数据源，自己计算，无网络ID，速度超快。并且是世界上唯一的。缺点：没有序列，比较长（128bit）。作为数据库的主键和索引，索引的效率会下降，占用的空间会更多。适用场景：只要对存储空间没有严格要求的都可以应用，比如各种链接跟踪，日志存储等。方法五：雪花算法（SnowflakeAlgorithm）生成ID。雪花ID严格来说属于本地生产ID，不同于RedisID、MongoDBID属于远程生产ID。本地生产的高ID性能，远程生产的低ID性能。雪花ID的原理是使用Long类型（64位），按照一定的规则填入段：时间（毫秒级别）+簇ID+机器ID+序列号。每个段占用的位数可以根据实际需要分配，其中clusterID和machineID两部分在实际应用场景中依赖于外部参数配置或数据库记录。总结一下，snowflakeID的优缺点和使用场景：优点：高性能，低延迟，去中心化，整体按时间排序缺点：需要机器时钟同步（到秒级），时钟回调问题需要待解决如果某台机器的系统时钟拨回，可能会导致ID冲突或ID乱序。适用场景：高并发ID的分布式应用环境下数据主键的技术选择这里不使用地址的哈希码作为ID这里不使用数据库的自增ID，以及没有使用redis和mongdb的分布式ID最后，这里，从发送端的数性能和整体顺序（B+树索引结构更友好）来看，最终选择的雪花算法吞吐量为100Wops+但是雪花算法有什么问题？需要解决时钟回调的问题。如何解决时钟回调问题，可以参考推特官方代码、百度ID代码、ShardingjdbcID源码、综合存储方案设计与解决方案。5.数据存储的高并发架构该数据结构化程度很高，可以使用结构化数据库MYSQL进行存储。结构很简单，我们会有两列：1.ID,int,//distributedsnowflakeid;2.SURL,varchar,//原始网址；接下来开始高并发、海量数据场景，需要采用MYSQL分库分表架构存储。陈建议，这里可以谈谈你在分库分表操作方面的经验，以及操作案例。然后进行交互式响应。即首先查询输入条件并进行确认。然后根据分治模型，从两个维度分析架构：数据容量的分治架构（存储规模）和访问流量的分治架构（吞吐规模）。本篇内容涉及的方案，对于不同的项目，基本相同。6.用于歧义检查的高并发架构所谓地址歧义，就是多次请求同一个长地址得到的短地址是不同的。在生成地址时，需要进行歧义检查，防止每次都为长地址重新生成一个短地址，而多次请求每个长地址得到的短地址是不同的。通过歧义检查，长链接和短链接真正做到一对一。如何检查歧义？最简单粗暴的解决办法是：直接去数据库查。然而，这是以显着的性能成本为代价的。你应该知道：数据库的主键不是原始url，而是短链url。如果根据原始url进行存在性检查，则需要额外建立索引。问题的症结在于数据库的性能极低，没有办法支持超高并发的歧义检查。所以，肯定不可能每次都用数据库去查。看到这里很多同学可能想到了另外一种方案，就是redis的Bloomfilter。已经生成的原始url，一般的解决方法是将已经生成的原始url记录到redisBloomfilter中即可。每次执行歧义检查时，都会使用redis布隆过滤器。Bloomfilter是bitset+multiplehashes的架构。宏观上，空间换来了时间。它不存储所有surl（原始url）的内容，只存储surl的存在，为大家节省了大量的内存空间。在数据量比较大的情况下，既满足时间要求，又满足空间要求。布隆过滤器的一大用处在于它可以快速判断一个元素是否在一个集合中。布隆过滤器常见的使用场景如下：黑名单：反垃圾邮件，从数十亿的垃圾邮件列表中判断一个邮箱是否为垃圾邮箱（同理，垃圾邮件）URL去重：网络爬虫对URL进行去重，避免爬取相同的URL地址词拼??写检查Key-Value缓存系统Key验证（缓存穿透）：缓存穿透，将所有可能的数据缓存放入布隆过滤器，当黑客访问不存在缓存时，快速返回，避免缓存和DB挂断。ID校验，例如订单系统查询订单ID是否存在，不存在则直接返回。BloomFilter就是专门为解决我们上面提到的去重问题而设计的。使用布隆过滤器不会像使用缓存那样浪费空间。当然，他也有一个小毛病，就是不太准。规则是：存在不一定存在。BloomFilter相当于一个不准确的集合集合。我们可以使用其中的contains方法来判断一个对象是否存在，但是需要注意的是这个判断并不特殊。准确的。一般来说，如果通过contains判断一个值不存在，则它一定不存在，但如果判断一个值存在，则它可能不存在。那么对于surl，解决方法是：如果redisbloomfilter不存在，直接生成；否则如果判断redisbloomfilter存在，可能是误判，还需要进行dbcheck。但是redisbloomfilter误判的概率很低，经过合理优化，不到1%。有朋友可能会说，100Wqps的话，1%也是10W1ps，DB还是搞不定，怎么办？您可以使用缓存架构，甚至是多级缓存架构。具体可以使用Redis缓存来缓存热门网址，实现部分地址的一对一缓存。比如在K-V数据库中存储最新/最流行的对应关系，比如本地CacheCaffeine存储最近产生的长短对应关系，利用过期机制实现LRU淘汰，保证经常使用的URL总是对应同一个短网址，但不保证不常用网址的对应。从而大大减少了空间的消耗。7.映射模块（/转换模块）高并发架构这里主要介绍一下自己对多级缓存的掌握和理解。可以使用缓存、二级缓存、三级缓存来加速id到surl的转换。简单的缓存方案缓存流行的长链接（需要统计长链接进来的次数），最近的长链接（可以用redis保存最近一小时的数据）等，如果请求longURL命中缓存，直接获取对应的shortURL返回，无需再生成重定向补充服务301和302不同的是301永久重定向和302临时重定向。301永久重定向：第一次请求得到长链接后，浏览器下次请求短链接时，不再向服务器请求短URL，而是直接从浏览器的缓存中获取，减轻了服务器的负载压力。302TemporaryRedirection：每次请求短链接时，都会请求短URL服务器（除非在响应中使用Cache-Control或Expired来暗示浏览器缓存）。使用301可以减轻服务器的压力，但是无法在服务器层获取到短网址。计算URL的访问次数。如果该链接恰好是某个活动的链接，则无法分析此活动的效果并用于大数据分析。302虽然会增加服务器的压力，但是在server层统计访问量还是比较方便的，所以如果有需要这些数据的话，可以使用302，因为这个成本是值得的，但是具体的跳转方法应结合实际情况。情境选择。8、架构的魅力架构的魅力在于没有最好的方案，只有更好的方案。大家有什么问题或者更好的解决办法可以多交流。
