# 系统设计

## 海量数据处理

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

* 哈希表 (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](https://hackernoon.com/probabilistic-data-structures-bloom-filter-5374112a7832) [详解布隆过滤器的原理、使用场景和注意事项](https://www.jianshu.com/p/2104d11ee0a2)

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

* 使用A文件建立布隆过滤器
* 遍历B文件中的每一个元素，判断是否在A中出现过

## 服务化架构的演进

### MVC架构

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

### RPC架构

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

### SOA架构

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

### 微服务架构

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

## 高并发系统设计

### 1. 秒杀系统

[如何设计一个秒杀系统](https://www.cnblogs.com/wangzhongqiu/p/6557596.html)

#### 场景特点

* 秒杀时大量用户会在同一时间同时进行抢购，网站瞬时访问流量激增。
* 秒杀一般是访问请求数量远远大于库存数量，只有少部分用户能够秒杀成功。
* 秒杀业务流程比较简单，一般就是下订单减库存。

#### 架构设计理念

* **限流：** 因为只有少部分用户能够秒杀成功，所以要限制大部分流量，只允许少部分流量进入服务后端。
* **削峰：**对于秒杀系统瞬时会有大量用户涌入，所以在抢购一开始会有很高的瞬间峰值，高峰值流量是压垮系统很重要的原因。实现削峰的常用的方法有利用缓存和消息中间件等技术。
* **内存缓存：**秒杀系统最大的瓶颈一般都是数据库读写，由于数据库读写属于磁盘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. 抢红包系统

[高并发系统的限流](https://www.cnblogs.com/haoxinyue/p/6792309.html)