湖州网站设计浙北数据,电子工程网注册,东莞网站建设销售前景怎么样,济南建设集团网站Java全能学习面试指南#xff1a;https://javaxiaobear.cn 我们先来看看#xff0c;当高并发遇到海量数据处理时的架构。在社交媒体上#xff0c;人们经常需要分享一些 URL#xff0c;但是有些 URL 可能会很长#xff0c;比如#xff1a;
https://time.geekbang.org/hyb… Java全能学习面试指南https://javaxiaobear.cn 我们先来看看当高并发遇到海量数据处理时的架构。在社交媒体上人们经常需要分享一些 URL但是有些 URL 可能会很长比如
https://time.geekbang.org/hybrid/pvip?utm_sourcegeektime-pcdiscover-bannerutm_termgeektime-pc-discover-banner
这样长的 URL 显然体验并不友好。我们期望分享的是一些更短、更易于阅读的短 URL比如像 http://javaxiaobear.cn/study-tutorial/这样的。当用户点击这个短 URL 的时候可以重定向访问到原始的链接地址。为此我们将设计开发一个短 URL 生成器产品名称是“Fuxi伏羲”。
我们预计 Fuxi 需要管理的短 URL 规模在百亿级别并发吞吐量达到数万级别。这个量级的数据对应的存储方案是什么样的用传统的关系数据库存储还是有其他更简单的办法此外如何提升系统的并发处理能力呢这些是我们今天要重点考虑的问题。
1、需求分析
短 URL 生成器也称作短链接生成器就是将一个比较长的 URL 生成一个比较短的URL当浏览器通过短 URL 生成器访问这个短 URL 的时候重定向访问到原始的长 URL目标服务器访问时序图如下: 对于需要展示短 URL 的应用程序由该应用调用短 URL 生成器生成短 URL并将该短URL 展示给用户用户在浏览器中点击该短 URL 的时候请求发送到短 URL 生成器短URL 生成器以 HTTP 服务器的方式对外提供服务短 URL 域名指向短 URL 生成器短URL 生成器返回 HTTP 重定向响应将用户请求重定向到最初的原始长 URL浏览器访问长 URL 服务器完成请求服务。
1、短 URL 生成器的用例图 用户 client 程序可以使用短 URL 生成器 Fuxi 为每个长 URL 生成唯一的短 URL并存储起来。用户可以访问这个短 URLFuxi 将请求重定向到原始长 URL。生成的短 URL 可以是 Fuxi 自动生成的也可以是用户自定义的。用户可以指定一个长URL 对应的短 URL 内容只要这个短 URL 还没有被使用。管理员可以通过 web 后台检索、查看 Fuxi 的使用情况。短 URL 有有效期2 年后台定时任务会清理超过有效期的 URL以节省存储资源同时回收短 URL 地址链接资源。
2、性能指标估算
Fuxi 的存储容量和并发量估算如下
预计每月新生成短 URL 5 亿条短 URL 有效期 2 年那么总 URL 数量 120 亿
5亿 × 12月 × 2年 120亿1、存储空间
每条短 URL 数据库记录大约 1KB那么需要总存储空间 12TB不含数据冗余备份
120亿 × 1KB 12TB
2、吞吐量
每条短 URL 平均读取次数 100 次那么平均访问吞吐量每秒访问次数2 万
5亿 × 100 ÷ 30 × 24 × 60 × 60 ≈ 20000
一般系统高峰期访问量是平均访问量的 2 倍因此系统架构需要支持的吞吐能力应为 4万。
3、网络带宽
短 URL 的重定向响应包含长 URL 地址内容长 URL 地址大约 500BHTTP 响应头其他内容大约 500B所以每个响应 1KB高峰期需要的响应网络带宽 40MB
4万每秒次请求 × 1KB 40MB
Fuxi 的短 URL 长度估算如下: 短 URL 采用 Base64 编码如果短 URL 长度是 7 个字符的话大约可以编码 4 万亿个短URL 6 4 7 4 万亿 64^74万亿 6474万亿 如果短 URL 长度是 6 个字符的话大约可以编码 680 亿个短 URL。 6 4 6 680 亿 64^6680亿 646680亿
按我们前面评估总 URL 数 120 亿6 个字符的编码就可以满足需求。因此 Fuxi 的短URL 编码长度 6 个字符形如 http://javaxiaobear.cn/ScW4dt 。
3、非功能需求
系统需要保持高可用不因为服务器、数据库宕机而引起服务失效。系统需要保持高性能服务端 80% 请求响应时间应小于 5ms99% 请求响应时间小于20ms平均响应时间小于 10ms。短 URL 应该是不可猜测的即不能猜测某个短 URL 是否存在也不能猜测短 URL 可能对应的长 URL 地址内容。
2、概要设计
短 URL 生成器的设计核心就是短 URL 的生成即长 URL 通过某种函数计算得到一个 6个字符的短 URL。短 URL 有几种不同的生成算法。
1、单项散列函数生成短 URL
通常的设计方案是将长 URL 利用 MD5 或者 SHA256 等单项散列算法进行 Hash 计算得到 128bit 或者 256bit 的 Hash 值。然后对该 Hash 值进行 Base64 编码得到 22个或者 43 个 Base64 字符再截取前面的 6 个字符就得到短 URL 了如图 但是这样得到的短 URL可能会发生 Hash 冲突即不同的长 URL计算得到的短 URL是相同的MD5 或者 SHA256 计算得到的 Hash 值几乎不会冲突但是 Base64 编码后再截断的 6 个字符有可能会冲突。所以在生成的时候需要先校验该短 URL 是否已经映射为其他的长 URL如果是那么需要重新计算换单向散列算法或者换 Base64 编码截断位置。重新计算得到的短 URL 依然可能冲突需要再重新计算。但是这样的冲突处理需要多次到存储中查找 URL无法保证 Fuxi 的性能要求。
2、自增长短 URL
一种免冲突的算法是用自增长自然数来实现即维持一个自增长的二进制自然数然后将该自然数进行 Base64 编码即可得到一系列的短 URL。这样生成的的短 URL 必然唯一而且还可以生成小于 6 个字符的短 URL比如自然数 0 的 Base64 编码是字符“A”就可以用 http://javaxiaobear.cn/A 作为短 URL。
但是这种算法将导致短 URL 是可猜测的如果某个应用在某个时间段内生成了一批短URL那么这批短 URL 就会集中在一个自然数区间内。只要知道了其中一个短 URL就可以通过自增以及自减的方式请求访问其他 URL。Fuxi 的需求是不允许短 URL 可预测。
3、预生成短 URL
因此Fuxi 采用预生成短 URL 的方案。即预先生成一批没有冲突的短 URL 字符串当外部请求输入长 URL 需要生成短 URL 的时候直接从预先生成好的短 URL 字符串池中获取一个即可。
预生成短 URL 的算法可以采用随机数来实现6 个字符每个字符都用随机数产生用0~63 的随机数产生一个 Base64 编码字符
为了避免随机数产生的短 URL 冲突需要在预生成的时候检查该 URL 是否已经存在用布隆过滤器检查。因为预生成短 URL 是
离线的所以这时不会有性能方面的问题。事实上Fuxi 在上线之前就已经生成全部需要的 144 亿条短 URL 并存储在文件系统中预估需要短 URL120 亿Fuxi 预生成的时候进行了 20% 的冗余即 144 亿。
代码实现如下
import java.util.Random;
public class RandomBase64 {public static void main(String[] args) {StringBuilder shortUrl new StringBuilder();Random random new Random();for (int i 0; i 6; i) {int randomNumber random.nextInt(64);shortUrl.append(Base64Encoder(randomNumber));}System.out.println(生成的短URL: shortUrl.toString());}public static char Base64Encoder(int number) {char[] base64Chars ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789/.toCharArray();return base64Chars[number];}
}4、Fuxi 的整体部署模型
Fuxi 的业务逻辑比较简单相对比较有挑战的就是高并发的读请求如何处理、预生成的短URL 如何存储以及访问。高并发访问主要通过负载均衡与分布式缓存解决而海量数据存储则通过 HDFS 以及 HBase 来完成。具体架构图如下。 系统调用可以分成两种情况一种是用户请求生成短 URL 的过程另一种是用户访问短URL通过 Fuxi 跳转到长 URL 的过程。
对于用户请求生成短 RUL 的过程在短 URL 系统 Fuxi 上线前已经通过随机数算法预生成 144 亿条短 URL 并将其存储在 HDFS 文件系统中。系统上线运行后应用程序请求生成短 URL 的时候即输入长 URL请求返回短 URL请求通过负载均衡服务器被发送到短 URL 服务器集群短 URL 服务器再通过负载均衡服务器调用短 URL 预加载服务器集群。
短 URL 预加载服务器此前已经从短 URL 预生成文件服务器HDFS中加载了一批短URL 存放在自己的内存中这时只需要从内存中返回一个短 URL 即可同时将短 URL与长 URL 的映射关系存储在 HBase 数据库中时序图如下。 对于用户通过客户端请求访问短 URL 的过程即输入短 URL请求返回长 URL请求通过负载均衡服务器发送到短 URL 服务器集群短 URL 服务器首先到缓存服务器中查找是否有该短 URL如果有立即返回对应的长 URL短 URL 生成服务器构造重定向响应返回给客户端应用。
如果缓存没有用户请求访问的短 URL短 URL 服务器将访问 HBase 短 URL 数据库服务器集群。如果数据库中存在该短 URL短 URL 服务器会将该短 URL 写入缓存服务器集群并构造重定向响应返回给客户端应用。如果 HBase 中没有该短 URL短 URL 服务器将构造 404 响应返回给客户端应用时序图如下。 过期短 URL 清理服务器会每个月启动一次将已经超过有效期2 年的 URL 数据删除并将这些短 URL 追加写入到短 URL 预生成文件中。
为了保证系统高可用Fuxi 的应用服务器、文件服务器、数据库服务器都采用集群部署方案单个服务器故障不会影响 Fuxi 短 URL 的可用性。
对于 Fuxi 的高性能要求80% 以上的访问请求将被设计为通过缓存返回。Redis 的缓存响应时间 1ms 左右服务器端请求响应时间小于 3ms满足 80% 请求小于 5ms 的性能目标。对于缓存没有命中的数据通过 HBase 获取HBase 平均响应时间 10ms也可以满足设计目标中的性能指标。
对于 Redis 缓存内存空间估算业界一般认为超过 80% 请求集中在最近 6 天生成的短URL 上Fuxi 主要缓存最近六天生成的短 URL 即可。根据需求容量估计最近 6 天生成的短 URL 数量约 1 亿条因此需要 Redis 缓存服务器内存空间1亿 × 1KB 100GB
3、详细设计
详细设计关注重定向响应码、短 URL 预生成文件及加载、用户自定义短 URL 等几个关键设计点。
1、重定向响应码
满足短 URL 重定向要求的 HTTP 重定向响应码有 301 和 302 两种其中 301 表示永久重定向即浏览器一旦访问过该短 URL就将重定向的原始长 URL 缓存在本地此后不再请求短 URL 生成器直接根据缓存在浏览器HTTP 客户端的长 URL 路径进行访问。302 表示临时重定向每次访问短 URL 都需要访问短 URL 生成器。
一般说来使用 301 状态码可以降低 Fuxi 服务器的负载压力但无法统计短 URL 的使用情况而 Fuxi 的架构设计完全可以承受这些负载压力因此 Fuxi 使用 302 状态码构造重定向响应。
2、短 URL 预生成文件及预加载
Fuxi 的短 URL 是在系统上线前全部预生成的并存储在 HDFS 文件中。共 144 亿个短URL每个短 URL 6 个字符文件大小 144亿 × 6B 86.4GB。
文件格式就是直接将 144 亿个短 URL 的 ASC 码无分割地存储在文件中如下是存储了 3个短 URL 的文件示例
Wdj4FbOxTw9CHtvPM1所以如果短 URL 预加载服务器第一次启动的时候加载 1 万个短 URL那么就从文件头读取 60K 数据并标记当前文件偏移量 60K。下次再加载 1 万个短 URL 的时候再从文件60K 偏移位置继续读取 60K 数据即可。
因此Fuxi 除了需要一个在 HDFS 记录预生成短 URL 的文件外还需要一个记录偏移量的文件记录偏移量的文件也存储在 HDFS 中。同时由于预加载短 URL 服务器集群部署多台服务器会出现多台服务器同时加载相同短 URL 的情况所以还需要利用偏移量文件对多个服务器进行互斥操作即利用文件系统写操作锁的互斥性实现多服务器访问互斥。
应用程序的文件访问流程应该是写打开偏移量文件 - 读偏移量 - 读打开短 URL 文件 - 从偏移量开始读取 60K 数据 - 关闭短 URL 文件 - 修改偏移量文件 - 关闭偏移量文件。
由于写打开偏移量文件是一个互斥操作所以第一个预加载短 URL 服务器写打开偏移量文件以后其他预加载短 URL 服务器无法再写打开该文件也就无法完成读 60K 短 URL 数据及修改偏移量的操作这样就能保证这两个操作是并发安全的。
加载到预加载短 URL 服务器的 1 万个短 URL 会以链表的方式存储每使用一个短 URL链表头指针就向后移动一位并设置前一个链表元素的 next 对象为 null。这样用过的短URL 对象可以被垃圾回收。
当剩余链表长度不足 2000 的时候触发一个异步线程从文件中加载 1 万个新的短URL并链接到链表的尾部。
与之对应的 URL 链表类图如下。 URLNodeURL 链表元素类成员变量 uRL 即短 URL 字符串next 指向下一个链表元素。LinkedURLURL 链表主类成员变量 head 指向链表头指针元素uRLAmount 表示当前链表剩余元素个数。acquireURL() 方法从链表头指针指向的元素中取出短 URL 字符串并执行 urlAmount-- 操作。当 urlAmount 2000 的时候调用私有方法loadURL()该方法调用一个线程从文件中加载 1 万个短 URL 并构造成链表添加到当前链表的尾部并重置 uRLAmount。
3、用户自定义短 URL
Fuxi 允许用户自己定义短 URL即在生成短 URL 的时候由用户指定短 URL 的内容。为了避免预生成的短 URL 和用户指定的短 URL 冲突Fuxi 限制用户自定义短 URL 的字符个数不允许用户使用 6 个字符的自定义短 URL且 URL 长度不得超过 20 个字符。
但是用户自定义短 URL 依然可能和其他用户自定义短 URL 冲突所以 Fuxi 生成自定义短URL 的时候需要到数据库中检查冲突是否指定的 URL 已经被使用如果发生冲突要求用户重新指定。
4、URL Base64 编码
标准 Base64 编码表如下 其中“”和“/”在 URL 中会被编码为“%2B”以及“%2F”而“%”在写入数据库的时候又和 SQL 编码规则冲突需要进行再编码因此直接使用标准 Base64 编码进行短URL 编码并不合适。URL 保留字符编码表如下。 所以我们需要针对 URL 场景对 Base64 编码进行改造使用 URL 保留字符表以外的字符对 Base64 编码表中的 6263 进行编码将“”改为“-”将“/”改为“_”Fuxi 最终采用的 URL Base64 编码表如下。 4、总结
我们开头提到Fuxi 是一个高并发2 万 QPS、海量存储144 亿条数据、还需要10ms 的高性能平均响应时间的系统。但是我们后面看到Fuxi 的架构并不复杂。
这一方面是源于 Fuxi 的业务逻辑非常简单只需要完成短 URL 与长 URL 的映射关系生成与获取就可以了。另一方面则是源于开源技术体系的成熟比如一个 HDFS 集群可支持百万 TB 规模的数据存储而我们需要的存储空间只有区区不到 100GB都有点大材小用了。事实上Fuxi 选择 HDFS 更多的考量是利用 HDFS 的高可用HDFS 的自动备份策略为我们提供了高可用的数据存储解决方案。
同理高并发也是如此2 万 QPS 看起来不小但实际上由于业务逻辑简单单个数据都很小加上大部分请求数据可以通过 Redis 缓存获取所以实际响应时间是非常短的10ms 的平均响应时间使得 Fuxi 真正承受的并发压力只有 200。对于这样简单的业务逻辑以及 200 这样的并发压力我们使用配置高一点的服务器的话只需要一台短 URL 服务器其实就可以满足了。所以我们在短 URL 服务器之前使用负载均衡服务器这也是更多地为高可用服务。
往期推荐
1.高并发系统它的通用设计方法是什么? 2. 软件建模与文档架构师怎样绘制系统架构蓝图 3. 高并发架构设计方法面对高并发怎么对症下药
