系统设计

海量数据处理

海量数据处理中常用的数据结构有：

  • 哈希表 (HashMap)

  • 堆 (Heap)

  • 前缀树 (Trie)

  • 位图 (BitMap)

  • 布隆过滤器 (Bloom Filter).

  1. 统计一万个单词中出现最频繁的前10个单词。

  • 可以使用前缀树Trie统计每个单词出现的次数

  • 使用小顶堆计算出现最频繁的10个单词

  1. 搜索引擎会记录用户的查询串，每个查询串的长度为1-255字节。目前有1000万条查询串，这些记录重复度比较高，去重后不超过300万条。一个查询串的重复度越高就越热门。请统计最热门的10个查询串，要求使用的内存不能超过1G。

300万 * 255字节 = 765M，不会超过1G

  • 可以使用哈希表统计每个查询串出现次数

  • 使用小顶堆统计结果

  1. 统计100亿个IP中出现次数最多的前10个IP.

每个IP地址是一个32位二进制数，占4字节，100亿个IP大约占用37G的空间，需要采用MapReduce的思想分批处理。

  • 分割任务：设计一个哈希函数（例如f(IP) = IP % 100），将100亿个IP分成100份

  • 计算子任务：使用小顶堆计算每份IP中出现次数最多的前10个IP

  • 合并：将100个子任务的计算结果进行合并，使用小顶堆计算最终结果

  1. 在2.5亿个整数中找出不重复的整数。

  • 对每一个整数使用 2 bit来表示它出现的次数：00-不存在，01-出现一次，10-出现多次，11-无意义

  • 扫描这2.5亿个整数，修改Bitmap中相应位：如果是00变01，01变10，10保持不变

  • 扫描完成后，将Bitmap中对应位是01的整数输出即可

  1. A、B两个文件中各存放50亿条URL，每条URL占用64字节，内存限制是16G，请找出A、B文件共同的URL.

Probabilistic Data structures: Bloom filter 详解布隆过滤器的原理、使用场景和注意事项

假设布隆过滤器的错误率p为0.01，则位数组大小m约为输入元素个数n的10倍，50亿 * 10个Bit大约占用6.25G (计算公式请参考上面的文章)

  • 使用A文件建立布隆过滤器

  • 遍历B文件中的每一个元素，判断是否在A中出现过

服务化架构的演进

MVC架构

当业务规模很小时，将所有功能都不熟在同一个进程中，通过双机或者负载均衡器实现负债分流；此时，分离前后台逻辑的MVC架构是关键。

RPC架构

当垂直应用越来越多，应用之间交互不可避免，将核心和公共业务抽取出来，作为独立的服务，实现前后台逻辑分离。此时，用于提高业务复用及拆分的RPC框架是关键。

SOA架构

随着业务发展，服务数量越来越多，服务生命周期管控和运行态的治理成为瓶颈，此时用于提升服务质量的SOA服务治理是关键。

微服务架构

通过服务的原子化拆分，以及微服务的独立打包、部署和升级，小团队的交付周期将缩短，运维成本也将大幅度下降。

高并发系统设计

1. 秒杀系统

如何设计一个秒杀系统

场景特点

  • 秒杀时大量用户会在同一时间同时进行抢购，网站瞬时访问流量激增。

  • 秒杀一般是访问请求数量远远大于库存数量，只有少部分用户能够秒杀成功。

  • 秒杀业务流程比较简单，一般就是下订单减库存。

架构设计理念

  • 限流： 因为只有少部分用户能够秒杀成功，所以要限制大部分流量，只允许少部分流量进入服务后端。

  • 削峰：对于秒杀系统瞬时会有大量用户涌入，所以在抢购一开始会有很高的瞬间峰值，高峰值流量是压垮系统很重要的原因。实现削峰的常用的方法有利用缓存和消息中间件等技术。

  • 内存缓存：秒杀系统最大的瓶颈一般都是数据库读写，由于数据库读写属于磁盘IO，性能很低，如果能够把部分数据或业务逻辑转移到内存缓存，效率会有极大地提升。

架构方案

前端方案

  • 页面静态化：将活动页面上的所有可以静态的元素全部静态化，并尽量减少动态元素，通过CDN来抗峰值。；

  • 禁止重复提交：用户提交之后按钮置灰，禁止重复提交 ；

  • 用户限流：在某一时间段内只允许用户提交一次请求，比如可以采取IP限流。

后端方案

  1. 网关层

限制用户访问频率：我们上面拦截了浏览器访问的请求，但针对某些恶意攻击或其它插件，在服务端控制层需要针对同一个访问uid，限制访问频率。

  1. 服务层

上面只拦截了一部分访问请求，当秒杀的用户量很大时，即使每个用户只有一个请求，到服务层的请求数量还是很大。比如我们有100W用户同时抢100台手机，服务层并发请求压力至少为100W。

  • 采用消息队列缓存请求：可以先将这些请求缓存到消息队列，数据库层订阅消息减库存，减库存成功的请求返回秒杀成功，失败的返回秒杀结束。

  • 利用缓存应对读请求：对类似于12306等购票业务，是典型的读多写少业务，大部分请求是查询请求，所以可以利用缓存分担数据库压力。

  • 利用缓存应对写请求：缓存也是可以应对写请求的，比如我们就可以把数据库中的库存数据转移到Redis缓存中，所有减库存操作都在Redis中进行，然后再通过后台进程把Redis中的用户秒杀请求同步到数据库中。

具体实现方案

我们可以利用Redis实现一个秒杀系统。采用Redis 最简单的key-value数据结构，用一个原子类型的变量值(AtomicInteger)作为key，把用户id作为value，库存数量便是原子变量的最大值。对于每个用户的秒杀，我们使用 RPUSH key value插入秒杀请求， 当插入的秒杀请求数达到上限时，停止所有后续插入。

然后我们可以在台启动多个工作线程，使用 LPOP key 读取秒杀成功者的用户id，然后再操作数据库做最终的下订单减库存操作。

当然，上面Redis也可以替换成消息中间件如ActiveMQ、RabbitMQ等，也可以将缓存和消息中间件组合起来，缓存系统负责接收记录用户请求，消息中间件负责将缓存中的请求同步到数据库。

2. 抢红包系统

高并发系统的限流

上一页分布式系统

最后更新于