阿里面试宝典（二十一）：面试题举例

问题导读

1.如何设计一个分布式环境下全局唯一的发号器?
2.UUID有哪些优点和缺点？
3.如何设计一个带有过期时间的LRU缓存？



上一篇
阿里面试宝典（二十）：持续集成、持续发布，jenkins
https://www.aboutyun.com/forum.php?mod=viewthread&tid=30209


一、设计一个分布式环境下全局唯一的发号器

1、UUID

常见的方式。可以利用数据库也可以利用程序生成，一般来说全球唯一。

优点：

1. 简单，代码方便。
2. 生成ID性能非常好，基本不会有性能问题。 \3. 全球唯一，在遇见数据迁移，系统数据合并，或者数据库变更
等情况下，可以从容应对。

缺点：

1. 没有排序，无法保证趋势递增。
2. UUID往往是使用字符串存储，查询的效率比较低。
3. 存储空间比较大，如果是海量数据库，就需要考虑存储量的问题。
4. 传输数据量大
5. 不可读。


2、数据库自增长序列或字段

最常见的方式。利用数据库，全数据库唯一。

优点：

1. 简单，代码方便，性能可以接受。
2. 数字ID天然排序，对分页或者需要排序的结果很有帮助。

缺点：

1. 不同数据库语法和实现不同，数据库迁移的时候或多数据库版本支持的时候需要处理。
2. 在单个数据库或读写分离或一主多从的情况下，只有一个主库可以生成。有单点故障的风险。
3. 在性能达不到要求的情况下，比较难于扩展。
4. 如果遇见多个系统需要合并或者涉及到数据迁移会相当痛苦。
5. 分表分库的时候会有麻烦。

优化方案：

针对主库单点，如果有多个Master库，则每个Master库设置的起始数字不一样，步长一样，可以是Master的个数。比如：Master1 生成的是 1，4，7，10，Master2生成的是2,5,8,11 Master3生成的是 3,6,9,12。这样就可以有效生成集群中的唯一ID，也可以大大降低ID生成数据库操作的负载。


3、数据库sequence表以及乐观锁

我们可以单独设置一张表，来存储所有表的下一个主键的值，例如现在有A、B、C三个表，sequence表结构如下



然后，每当需要获取下一个主键值的时候，首先使用select语句获取主键，然后使用数据库的乐观锁机制去update这个sequence表，更新成功则说明获取主键成功，更新失败则说明存在并发，当前主键被别的机器抢走了，需要重新select出新的主键，载update。例如要获取表B的下一个主键，需要发送sql

select id from sequence where name=B //获得id=100,更新sequence表
update sequence set id=id+1 where name=B and id=100
复制代码

优点：

1. 操作简单，使用乐观锁可以提高性能
2. 生成的id有序递增，连续
3. 可适用于分布式环境，可以进行分库分表

缺点:

1. 需要单独设置一张表，浪费存储空间
2. 数据库更新比较频繁，写压力太大

改进方案

可以将每次获取一个主键，改为每次获取500个或者更多，然后缓存再当前机器中，用完这500个后，再去请求数据库，做更新操作，可以减少数据库的读写压力，但是会造成主键的不连续


4、Redis生成ID

当使用数据库来生成ID性能不够要求的时候，我们可以尝试使用Redis来生成ID。这主要依赖于Redis是单线程的，所以也可以用生成全局唯一的ID。可以用Redis的原子操作 INCR和INCRBY来实现。

可以使用Redis集群来获取更高的吞吐量。假如一个集群中有5台Redis。可以初始化每台Redis的值分别是1,2,3,4,5，然后步长都是5。各个Redis生成的ID为：

A：1,6,11,16,21 B：2,7,12,17,22 C：3,8,13,18,23 D：4,9,14,19,24 E：5,10,15,20,25

这个，随便负载到哪个机确定好，未来很难做修改。但是3-5台服务器基本能够满足器上，都可以获得不同的ID。但是步长和初始值一定需要事先需要了。使用Redis集群也可以方式单点故障的问题。

另外，比较适合使用Redis来生成每天从0开始的流水号。比如订单号=日期+当日自增长号。可以每天在Redis中生成一个Key，使用INCR进行累加。

优点：

1. 不依赖于数据库，灵活方便，且性能优于数据库。
2. 数字ID天然排序，对分页或者需要排序的结果很有帮助。

缺点：

1. 如果系统中没有Redis，还需要引入新的组件，增加系统复杂度。
2. 需要编码和配置的工作量比较大。


5、Twitter的snowflake算法

snowflake 是 twitter 开源的分布式ID生成算法，其核心思想为，一个long型的ID：

41 bit 作为毫秒数 - 41位的长度可以使用69年

10 bit 作为机器编号 （5个bit是数据中心，5个bit的机器ID） - 10位的长度最多支持部署1024个节点

12 bit 作为毫秒内序列号 - 12位的计数顺序号支持每个节点每毫秒产生4096个ID序号




Snowflake图示

算法单机每秒内理论上最多可以生成1000*(2^12)，也就是400W的ID，完全能满足业务的需求。

snowflake算法可以根据自身项目的需要进行一定的修改。比如估算未来的数据中心个数，每个数据中心的机器数以及统一毫秒可以能的并发数来调整在算法中所需要的bit数。

优点：

1. 不依赖于数据库，灵活方便，且性能优于数据库。
2. ID按照时间在单机上是递增的。

缺点：

在单机上是递增的，但是由于涉及到分布式环境，每台机器上的时钟不可能完全同步，也许有时候也会出现不是全
局递增的情况。


二、设计一个带有过期时间的LRU缓存

问题描述

如何设计实现LRU缓存？且Set() 和 Get() 的复杂度为O(1)。

问题分析

LRU，全称Least Recently Used，最近最少使用缓存。




LRU算法的设计原则

如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小 也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰

而用什么数据结构来实现LRU算法呢？

可能大多数人都会想到：用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。 这种实现思路很简单，但是有什么缺陷呢？需要不停地维护数据项的访问时间戳，另外，在插入数据、删除数据以及访问数据时，时间复杂度都是O(n),数组的缺陷凸显无疑

那么有没有更好的实现办法呢？

那就是利用链表和HashMap。当需要插入新数据项，在链表中

命中，则把该节点移到链表头部 不存在，则新建一个节点，放在链表头部，若缓存满，则把链表最后一个节点删除即可。 在访问数据时，若数据项在链表中存在，则把该节点移到链表头部，否则返回-1 这样一来在链表尾部的节点就是最近最久未访问的数据项。

1）set(key,value)

若key在hashmap中存在，则先重置value，然后获取对应节点cur，将其从链表删除，并移到链表头 不存在，则新建一个节点，并将节点放到链表的头部。 当Cache满，删除链表最后一个节点

2）get(key)

若key在hashmap中存在，把对应的节点放到链表头，并返回对应value 若不存在，则返回-1 即保证基本的get/set同时，还要保证最近访问(get或put)的节点保持在限定容量的Cache中，如果超过容量则应该把LRU(近期最少使用)的节点删除掉。

当我们在get/set一个节点时都会把操作的这个节点移动到tail节点处，代表最新操作的节点，head节点永远指向最老的节点，当超过设定的容量时，我们就删除head节点指向的最老节点

就像是个LinkedHashMap，这样做的好处是，get/set在不冲突情况下可保证O(1)复杂度 也可通过双向链表保证LRU的删除/更新O(1)复杂度

当然可简化head和tail变成一个head节点，成环，这样head的next指向最旧的节点，prev指向最新的节点。


过期时间实现

维护一个线程
惰性删除

最新经典文章，欢迎关注公众号