系统设计相关

本文主要收录关于系统设计相关的问题学习笔记。

设计分布式ID生成器

现实中很多业务都有生成唯一ID的需求，如用户、微博、订单等，这些ID往往会作为数据库的主键要保证全局唯一。数据库会在该字段上做聚集索引，即此字段会影响各条数据在物理存储上的顺序。

ID要尽可能短来节省内存，同时使得索引效率更高。基本上64位能满足绝大多数场景。但通常并不需要这么多，可以根据业务需求预估ID最大值，然后选取合适的bit来表示ID。

查询时往往有排序分页需求，需要给每个数据添加一个时间字段，并在其上建立普通索引。但是普通索引访问较慢，所以尽量使得ID按时间粗略有序来节省这个字段。

• 全局唯一
• 按时间粗略有序
• 尽可能短

一些生成ID的常用方法：

• UUID: mongoDB自动给每条数据赋值ObjectId，保证不会重复，就是采用了UUID的算法。 ObjectID=4bytes timestamp + 3bytes 机器ID + 2bytes 进程ID + 3 bytes计数器。 优点是每个机器都可以独立产生ID，天然分布式，缺点是ID太长占用内存且查询效率低。
• 多台mysql服务器： 组成一个高性能的分布式发号器，通过轮询均衡的将请求发送给N个mysql中的任意一个，然后返回一个ID。Mysql不需要把所有的ID都记录，只需要记录最大MAX_ID即可。更新使用REPLACE INTO删除旧值，增加新值。缺点是ID不是严格递增的
• Snowflake: twitter的开源项目，专门生成ID。核心算法是0+ 41bit时间戳 + 13bit机器ID+10bit自增序列号。 41位时间戳可以表示～70年，10bit支持1023台机器，序列号支持1ms产生4095个id

设计短网址服务

当前互联网的网页总数大概是45亿，超过了2^32，但远远小于64位整数的上限值。微博的短网址服务用的是长度为7的字符串，可以看做是62位进制数，最大能表示62^7个网址，远大于45亿。

因此使用长度不超过7的字符串，由大小写字母+数字共62个字母组成。

一般来说一个长网址在不同地点不同用户等情况下生成的短网址应该不一样，这样在后端数据库可以更好的进行数据分析。入包含生成该网址的用户名、所在网站、http头的user agent信息等，因此长短网址最好是一对多映射。

通过hash计算短网址不可避免存在冲突，因此最好采用上节所使用的分布式ID生成器的方式如雪花算法来实现。

存储时以短网址作为key，长网址作为value存储在数据库中。可以使用传统的关系型数据库mysql postgresql，也可以使用任意一个分布式kv数据库，如redis，levelDB等。

重定向使用的是302临时重定向，因为如果使用301永久重定向的话搜索引擎会直接展示真实地址，导致我们无法根据短网址解析需要的用户信息等。

为了防止黑客网络攻击，短时间内向服务器发送大量请求导致耗光ID。

• 可以采用限制单日IP的请求总数，超过阈值直接拒绝服务。
• 同时可以用redis缓存，存储长网址->ID的映射，仅存储一天以内的数据并用LRU机制进行淘汰。

定时任务调度器

priorityBlockingQueue+Polling

• 用java.util.concurrent.PriorityBlockingQueue来作为优先级队列，同时保证了线程安全。如果使用java.util.PriorityQueue需要实现ReentrantLock用锁把队列保护起来
• 生产者通过while true循环生成随机任务进入队列
• 消费者起一个线程通过while true每隔几秒检查队列，有任务则取出来执行

轮询的缺点就是间隔时间不好把握，间隔长任务无法及时处理，间隔短耗费CPU。

PriorityBlockingQueue+时间差

将方案一中的while true改成查看堆顶的元素但不取出，如果任务过期则取出，反之计算一个时间差，sleep该时间差。

虽然消除了轮询的缺点，但是该方案同时也有自身缺陷。如果计算时间差之后又有新的小于该时间差的任务加入队列，会导致处理不及时。

DelayQueue

改进后的priorityBlockingQueue，把计算时间差并让消费者等待该时间差的功能继承进了队列。消费者不需要关心时间差的事情，直接在while true循环中不断take即可。新的元素put时会唤醒所有等待的消费者线程。

为了避免多个消费者竞争，采用leader/follower模式，当一个线程时leader时它只需要一个时间差，其它follower无限等待。多个消费线程用take方法取任务，内部先加锁然后每个线程去peek头结点，如果leader不为空说明已经有线程在取，当前消费者无限等待。如果leader为空则设置leader为当前消费者并让其等待指定的时间。

需要注意的是take方法中会释放first=null，为了避免内存泄漏。如线程A获取first然后设置leader为A并让A等待一段时间；线程B同时进来获取first进入阻塞无限期等待，此时B持有first引用。A等待一定时间被唤醒后获得对象成功，出队后该对象应该被GC。但是此时B仍然持有此对象GC链路可达所以无法回收。极端情况下B无限休眠那么本该回收的对象就不能被GC销毁从而导致内存泄漏。

JDK中的ScheduledThreadPoolExecutor类似

时间轮 HashedWheelTimer

循环队列，每时间轮精度走一格。每个任务都需要一个字段记录圈数，每转一圈就-1，减到0就立刻取出。 Netty中已经有实现，性能高，插入和删除都是O（1），Linux内核定时器就是采用这种方案。

分布式定时任务调度器可以采用Redis的Zset和RabbitMQ等

设计一个线程安全的hashmap

hashmap有两种解决冲突的方案：开放地址法和链表法。

• 开放地址法，所有元素都在一个一维数组中，遇到冲突后按照一定规则向后探测。
  • 线性探测法：冲突后向后依次遍历，优点是计算速度快对CPU缓存友好，缺点是探测过程中会产生clustering现象，扎堆导致效率低下；
  • 二次探测法：通过一个i的二次函数计算，性能介于线性和双哈希之间；
  • 双哈希法：偏移量di由另外一个哈希函数计算
• 链表法，开放一个定长数组，每个格子指向一个桶，对每个元素计算出哈希并取模，找到对应的桶并插入该桶。发生冲突的元素会处于同一个桶中。

JDK7和JDK8中的java.util.HashMap采用了链表法，将其改为线程安全有几下几个方案：

• 所有public方法都加上synchronized，相当于一把全局锁，所有操作都要先获得锁。HashTable就是这样做的，性能低；
• 由于每个桶逻辑上都是独立的，将每个桶加一把锁，如果两个线程访问不同的桶就不需要争抢一把锁。这个方案并发性比前者好，不过锁的个数太多也会有很大开销；
• 锁分离技术，假设有1w个桶第二种方法就不适合，新建1w个ReetrantLock实例开销很大。可以将所有的桶均匀的划分为16个部分，每一部分成为一个segment，每个段上有一把锁。JDK7中的concurrentHashMap就是这个思路。
• JDK8中concurrentHashMap的实现又有很大变化，在锁分离的基础上，大量利用了CAS指令。并在底层存储有一个小优化，在链表长度太长>8时，链表就转换为红黑树。增删改查效率提升，该hashmap的实现代码从jdk7的1500行增长到6000+行

最近一个小时内访问频率最高的10个IP

• 实时输出
• 当前小时向前1小时
• QPS可能会达到10w/s

类似TopK，但是不需要Lossy Count或者Count-Min Sketch之类的算法。

QPS 10w/s，一小时大概有2^28.4个请求，可以在内存中建立3600个HashMap,放在一个数组中，每秒对应一个hashMap。IP为key出现的次数为Value，这样一小时最多有2^29个KV对，每个KV对占8字节，总内存大概时2^32字节，即4GB，单机可以储存。

同时建立一个大小为10的小根堆，用于存放当前出现次数最大的IP，堆顶是10个IP里频率最小的。每次新来一个请求将该秒中hashMap里对应的IP计数器增加1，并查询IP是否在堆里存在：

• 不存在则把该IP在3600个HashMap的计数器加起来，与堆顶出现次数进行比较。大于则替换
• 如果已经存在，把堆内该IP的计数器+1，并相应调整

此外需要一个后台常驻线程，每过1s就把最旧的那个HashMap销毁，并为当前1s新建一个HashMap，以此来维持一个一小时窗口

每次查询top 10 IP就把堆内元素返回即可。

为什么不用IP+时间作为key，单个HashMap存储？ 答：这样无法淘汰1小时前的数据，只能全量扫描删除；另外key字符串内存占用远大于int，导致单机无法满足。

KV存储引擎

LevelDB整体结构

内存随机读写甚至比硬盘的顺序读要慢，因此要尽量避免随机读写。 LevelDB采用一种SSTable的数据结构来实现，SSTable是一组按照key排序好的KV对，key和value都是字节数组。SSTable既可以存储在内存，也可以在硬盘，底层使用LSM Tree来存放有序的KV对。

• MemTable。内存中的SSTable，新数据先写入此处，然后批量写入磁盘。
• Log文件，写Memtable之前先写Log文件，用WAL方式，可以用来恢复数据。
• Immutable MemTable，内存中的MemTable达到一定大小后就不再接收新的数据，产生新的memtable来接收。Immutable memTable随后会写入硬盘变成SST文件。
• SSTable文件，文件尾部追加一块索引，记录key->offset,提高随机读的效率。有多层组成，每层中单个文件的容量成倍增长。
• Manifest文件，记录SST文件不同level的分布，以及元信息
• Current文件，当前manifest的文件名。

SST文件末尾的索引都要放在内存中，减少读索引时的一次IO；

所有读都要先看memtable，没有再查看内存中的索引。所有写都只能写到memtable，sst文件不可修改。定期把immutable memtable写入硬盘成为sst文件。定期对sst文件进行合并。删除通过追加tombstone值表示删除key，在定期合并sst时丢弃。更新通过追加新的kv到文件末尾，读取文件时新数据最先被读到。

memtable里的数据时按照key有序的，因此插入新数据时需要把kv插入到合适的位置来保证key的有序性。其底层核心数据是一个跳表。

数据流采样

当有一个无限的整数数据流，如何随机的从中抽取k个整数来？

k=1时只需要随机抽取一个样本出来：1）第一个整数到来时保存这个数；2）第2个整数到达时以1/2的概率使用这个整数替换第一个数；3）第i个整数到来时以1/i的概率使用第i个整数替换被选中的数。

当K>1时，需要随机采样多个样本，方法跟上面类似，把1变成K即可。

基数估计（Cardinality Estimation）

独立访客UniqueVisitor等数据流中不同元素个数的统计是基数估计问题。

• HashSet，存在大数据场景下单机内存不足问题。
• 通过bitmap不存储元素本身，假设知道不同元素的个数上限为N，开一个长度为N的bit数组，此方法缺点是bitmap的长度和实际基数无关而是与基数的上限有关，假设存在1亿基数需要12.5M的bitmap。
• LinearCounting,选择一个哈希函数h结果服从均匀分布，开一个长度为m的bitmap初始化为0，数据流每来一个元素计算其哈希值并对m取模然后将该位置置1.查询时如果还有u个bit为0，则总数近似为-mlog（u/m），其中m由基数大小和容许误差决定，假设基数大约为n，允许误差为e，m>(e^t-t-1)/(et)^2,其中t=n/m
• LogLog Counting， 均匀随机化，选取一个哈希函数h应用于所有元素，然后对哈希值进行基数估计。对每个哈希值从高到低找到第一个1出现的位置，取这个位置的最大值设为p，基数约为2^p。（通过分桶平均的思想来降低误差，相当于多次求平均）缺点是基数不大的情况下该计算方法误差很大。
  • 哈希碰撞可以忽略不计，即尽量避免冲突 * h结果均匀分布
  • 哈希后的结果是固定长度
• HyperLogLog Counting，在LLC基础上进行优化，通过使用调和平均数替代几何平均数降低离群值的干扰，并加入分段偏差纠正。

频率估计

如何计算数据流中任意元素的频率？Frequency Estimation问题。

• hashMap，存在单机内存无法存在的问题；
• 数据分片+hashmap，通过多台机器来满足内存需求；
• Count-Min Sketch，和布隆过滤器类似，优点是节约内存，缺点是对于出现次数较少的元素准确性较差；
  • 选定d个hash函数，开一个d*m的二维数组作为哈希表；
  • 对于每个元素，分别使用d个hash计算hash值，然后对m取余，在对应位置上增1。二维数组上的每个整数称为sketch；
  • 要查询某个元素的频率，只需要取出d个sketch，返回最小的那个。
• Count-Mean-Min Sketch，进行了如下改进显著改善在长尾数据上的精确度。
  • 来一个查询，首先按照count-min sketch正常流程取出d个sketch；
  • 对每个hash函数，估算出一个噪音，噪音等于该行所有整数的平均值（除了被查询的元素）
  • 用该行的sketch-该行的噪音作为真正的sketch
  • 返回d个sketch的中位数

TopK 频繁项

寻找数据流中最频繁出现的k个元素，如微博热搜榜，访问网站次数最多的前10个IP地址等。

• hashMap+Heap，用hashMap存放所有元素出现的次数，用小根堆存放目前出现过的最频繁的k个元素。数据量大时存在内存不足的情况。
  • 每次从数据流进来一个元素，如果hashmap中存在则把对应计数器+1，不存在则插入；
  • 在堆中查找该元素，如果找到则把堆中计数器+1并调整堆。反之将元素的次数和堆顶元素比较，如果大于则替换堆顶元素并调整堆。
• 多机hashMap+Heap，hash分配，每个节点独立计算后再合并。
• Count-Min Sketch + Heap，使用Count-Min Sketch代替hashmap保证内存使用。
• Lossy Counting，近似算法，思想是出现频率高的元素不太可能-1后变为0，低频元素不断被清理出去，这样内存占用会保持在一个很低的水平。
  • 建立一个hashmap，用于存放每个元素的出现次数；
  • 建立一个窗口；
  • 等待数据流不断流进这个窗口，直到窗口满后统计每个元素出现的频率，统计结束后每个元素的频率-1，然后将出现次数为0的元素从hashmap中删除
  • 返回建立窗口循环执行

成员查询

给定一个无限的数据流和一个有限的集合，如何判断数据流中的元素是否在这个集合？

布隆过滤器：

• 解决redis缓存穿透
• 爬虫时过滤已经获取的网址
• 垃圾邮件过滤

经过k个哈希函数计算该数据，返回K个计算出的hash值；将k个hash值映射到对应的K个二进制的数组下标；把数据下表对应位置置1。

查询时同样利用k个哈希函数计算数据对应的k个hash值，找到对应下标。如果存在一处元素值为0，说明该数据不在。反之则认为数据存在。

优点：1）存储二进制数据占用空间小；2）插入和查询速度快；3）保密性好，不存在原始数据。
缺点：1）两个不同数据计算的hash值相同存在误判可能。2）删除困难。

Guava实现的布隆过滤器将数据放在了本地，分布式场景不适合。此时可以使用redis封装好的Redisson。

范围查询

给定一个无限的整数数据流，如何查询在某个范围内的元素出现的总次数？如select count(key) where key >=left and key <= right;

可以利用计算频率时的方法Count-Min Sketch计算每个元素的频率，将指定范围内所有元素的sketch加起来就是范围内的元素总数了。 但是因为每个sketch都是近似值，多个近似值相加误差被放大。

解决方法就是使用不同分辨率的Count-Min sketch，第一个sketch每个格子存放单个元素的频率，第二个sketch每个格子存放两个元素的频率（把元素的hash值最低位bit去掉，即>>1），依次类推。

查找范围时，从粗粒度到细粒度找多个区间，不重不漏的完整覆盖区间，把相应的值加起来即可。

设计模式在外卖业务的应用

设计模式在外面业务中的实践

• 面向对象设计模式七大基本原则

  • 开闭原则：OpenCloseP，对扩展开放对修改关闭
  • 单一职责原则：SingleResponsibleP，实现类要单一职责
  • 里氏代换原则：Liskov SubsitutionP，不要破坏继承体系
  • 依赖倒转原则：Dependency InversionP，面向接口编程
  • 接口隔离原则：Interface SegregationP，设计接口时要精简单一
  • 合成聚合复用原则：Composite/Aggregation Reuse P
  • 最少知识原则，迪米特法则， Least KnowledgeP，Law of Demeter， 指导降低耦合

• 美团邀请用户返奖业务场景
  首先根据用户状态判断是否满足返奖，如果满足继续判断用户是新用户还是老用户，从而给予不同的奖励方案：

  • 新用户
    • 普通奖励（固定额度）
    • 梯度奖励（根据用户邀请人数给予不同奖励金额）
  • 老用户：根据老用户属性来计算返奖金额，为了评估不同的邀新效果，老用户也会存在多种返奖机制

考虑开闭原则，对于返奖流程保持封闭，对可能扩展的返奖规则进行开放。将返奖规则抽象为返奖策略。在DDD中返奖策略是一个值对象，通过工厂方式生产针对不同用户的奖励策略值对象。

返奖规则和设计模式实践

工厂模式：工厂方法模式和抽象工厂模式。定义一个用于创建对象的接口，让子类决定实例化哪个对象。工厂方法是一个类的实例化延迟到子类。
// 抽象的产品
public abstract class Product {
public abstract void method();
}
//定义一个具体产品
class ProductA extends Product {
@Override
public void method(){}
}
//抽象的工厂
abstract class Factory {
abstract Product createProduct(Class c);
}
//具体的工厂可以生产相同的产品
class FactoryA extends Factory {
@Overrid
Product createProduct(Class c) {
Product pro = (Product) Class.forName(c.getName()).newInstance();
return pro;
}
}

策略模式：定义一系列算法，将每个算法都封装起来，且支持互换。是一种对象行为模式
//定义一个抽象接口
public interface Strategy {
void strategyImplementation();
}

public class StrategyA implements Strategy {
  @Override
  public void strategyImplementation(){}
}

//封装策略，屏蔽高层模块对策略、算法的直接访问，屏蔽可能存在的策略变化
public class Context {
  private Strategy strategy = null;
  public Context(Strategy strategy) {
    this.strategy = strategy;
  }
  public void doStrategy(){
    strategy.strategyImplementation();
  }
}

工程实践：我们可以使用工厂模式生成不同的策略，同时使用策略模式来进行不同策略的执行。

//抽象策略
public abstract class RewardStrategy {
  public abstract void reward(long userId);
  public void insertRewardAndSettlement(long userId, int reward) {}; //更新用户信息及结算
}

//新用户返奖具体策略A
public class newUserRewardStrategyA extends RewardStrategy {
  @Override
  public void reward(long userId) {...} //具体计算逻辑
}
//老用户返奖具体策略A
public class oldUserRewardStrategyA extends RewardStrategy {
  @Override
  public void reward(long userId) {...}
}
//抽象工厂
public abstract class StrategyFactory<T> {
  abstract RewardStrategy createStrategy(Class<T> c);
}
//具体工厂创建具体的策略
public class FactoryRewardStrategyFactory extends StrategyFactory {
  @Override
  RewardStrategy createStrategy(Class c) {
    RewardStrategy product = null;
    try {
      product = (RewardStrategy) Class.forName(c.getName()).newInstance();
    } catch (Exception e) {}
    return product;
  }
}

public class RewardContext {
  private RewardStrategy strategy;
  public RewardContext(RewardStrategy strategy) {
    this.strategy = strategy;
  }
  public void doStrategy(long userId) {
    int rewardMoney = strategy.reward(userId);
    insertRewardAndSettlement(long userId, int reward) {
      insertReward(userId, rewardMoney);
      settlement(userId);
    }
  }
}

public class InviteRewardImpl {
//返奖主流程
public void sendReward(long userId) {
    FactorRewardStrategyFactory strategyFactory = new FactorRewardStrategyFactory();  //创建工厂
    Invitee invitee = getInviteeByUserId(userId);  //根据用户id查询用户信息
    if (invitee.userType == UserTypeEnum.NEW_USER) {  //新用户返奖策略
        NewUserBasicReward newUserBasicReward = (NewUserBasicReward) strategyFactory.createStrategy(NewUserBasicReward.class);
        RewardContext rewardContext = new RewardContext(newUserBasicReward);
        rewardContext.doStrategy(userId); //执行返奖策略
    }if(invitee.userType == UserTypeEnum.OLD_USER){}  //老用户返奖策略，... 
  }
}

通过这两个模式的组合，当我们系统需要增加一种返奖策略时，只需要实现RewardStrategy接口即可，无需考虑其他的改动。

返奖流程和设计模式实践

当受邀人在下单后，返奖后台接收到下单记录，此时邀请人进入返奖流程。

• 在接收到订单消息后，用户进入带校验状态，此时对订单进行返奖规则校验； （是否使用红包，红包是否在有效期，订单是否满足一定金额）
• 若校验通过，用户进入预返奖状态，并放入延迟队列。若校验未通过，用户进入不返奖状态，结束流程；
• T+N天后，处理延迟消息，若用户没有对订单进行退款，则进入待返奖状态。若用户退款，则进入不返奖状态，结束流程；
• 执行返奖，若成功进入完成状态，结束流程。反之，进入待补偿状态；
• 待补偿状态的用户会由任务定期触发补偿机制，直到返奖成功，进入完成状态，保障流程结束。

状态模式：当一个对象内在状态改变时，允许其改变行为，这个对象看起来像是改变了类。

//定义一个抽象的状态类
public abstract class State {
  Context context;
  public void setContext(Context context) {
    this.context = context;
  }
  public abstract void handle1();
  public abstract void handle2();
}
//定义状态A
public class ConcreteStateA extends State{
  @Override
  public void handle1() {} //本状态下必须要处理的事情
  @Override
  public void handle2() {
    super.context.setCurrentState(Context.ConcreteStateB); //切换到状态B
    super.context.handle2()；// 执行状态B的任务
  }
}
//定义状态B
public class ConcreteStateA extends State{
  @Override
  public void handle2() {} //本状态下必须要处理的事情
  @Override
  public void handle1() {
    super.context.setCurrentState(Context.ConcreteStateA); //切换到状态A
    super.context.handle1()；// 执行状态A的任务
  }
}
//定义一个上下文管理环境
public class Context {
  public final static ConcrestateA concreteStateA = new ConcreteStateA();
  public final static ConcreStateB concreteStateB = new ConcreateStateB();

  private state currentState;
  public state getCurrentState(){return currentState;}

  public void setCurrentState(State currentState){
    this.currentState = currentState;
    this.currentState.setContext(this);
  }
  public void handle1() { this.currentState.handle1();}
  public void handle2() { this.currentState.handle2();}
}
//定义client执行
public class Client {
  public static void main(String[] args) {
    Context context = new Context();
    context.setCurrentState(new ConcrestateA());
    context.handle1();
    context.handle2();
  }
}

工程实践：

//返奖状态执行的上下文
public class RewardStateContext {
  private RewardState rewardState;

  public void setRewardState(RewardState currentState) {this.rewardState = currentState;}
  public RewardState getRewardState() {return rewardState;}
  public void echo(RewardStateContext context, Request request) {
      rewardState.doReward(context, request);
  }
}
public abstract class RewardState {
  abstract void doReward(RewardStateContext context, Request request);
}
//待校验状态
public class OrderCheckState extends RewardState {
  @Override
  public void doReward(RewardStateContext context, Request request) {
    orderCheck(context, request);  //对进来的订单进行校验，判断是否用券，是否满足优惠条件等等
  }
}
//待补偿状态
public class CompensateRewardState extends RewardState {
  @Override
  public void doReward(RewardStateContext context, Request request) {
    compensateReward(context, request);  //返奖失败，需要对用户进行返奖补偿
  }
}
//预返奖状态，待返奖状态，成功状态，失败状态(此处逻辑省略)
//..
public class InviteRewardServiceImpl {
  public boolean sendRewardForInvtee(long userId, long orderId) {
    Request request = new Request(userId, orderId);
    RewardStateContext rewardContext = new RewardStateContext();
    rewardContext.setRewardState(new OrderCheckState());
    rewardContext.echo(rewardContext, request);  //开始返奖，订单校验
    //此处的if-else逻辑只是为了表达状态的转换过程，并非实际的业务逻辑
    if (rewardContext.isResultFlag()) {  //如果订单校验成功，进入预返奖状态
      rewardContext.setRewardState(new BeforeRewardCheckState());
      rewardContext.echo(rewardContext, request);
    } else {//如果订单校验失败，进入返奖失败流程，...
      rewardContext.setRewardState(new RewardFailedState());
      rewardContext.echo(rewardContext, request);
      return false;
    }
    if (rewardContext.isResultFlag()) {//预返奖检查成功，进入待返奖流程，...
      rewardContext.setRewardState(new SendRewardState());
      rewardContext.echo(rewardContext, request);
    } else {  //如果预返奖检查失败，进入返奖失败流程，...
      rewardContext.setRewardState(new RewardFailedState());
      rewardContext.echo(rewardContext, request);
      return false;
    }
    if (rewardContext.isResultFlag()) {  //返奖成功，进入返奖结束流程，...
      rewardContext.setRewardState(new RewardSuccessState());
      rewardContext.echo(rewardContext, request);
    } else {  //返奖失败，进入返奖补偿阶段，...
      rewardContext.setRewardState(new CompensateRewardState());
      rewardContext.echo(rewardContext, request);
    }
    if (rewardContext.isResultFlag()) {  //补偿成功，进入返奖完成阶段，...
      rewardContext.setRewardState(new RewardSuccessState());
      rewardContext.echo(rewardContext, request);
    } else {  //补偿失败，仍然停留在当前态，直至补偿成功（或多次补偿失败后人工介入处理）
      rewardContext.setRewardState(new CompensateRewardState());
      rewardContext.echo(rewardContext, request);
    }
    return true;
  }
}

投放系统中的设计模式

投放业务就是要在资源位中展示符合当前用户的资源。首先运营人员会配置需要展示的资源，以及对资源进行过滤的规则。

为了实现对过滤规则的解耦，对单个规则值对象修改封闭，对规则集合组成的过滤链开放。在资源位过滤时引入责任链模式。

责任链模式：多个对象都有机会处理请求，避免了请求的发送者和接受者之间的耦合。将这些对象连成一条链，并沿着传递该请求，直到有对象处理它为止。

//定义一个抽象的handler
public abstract class Handler {
  private Handler nextHandler;
  private int level;
  public Handler(int level) {
    this.level = level;
  }
  public setNextHandler(Handler handler) {
    this.nextHandler = handler;
  }
  public final void handleMessage(Request request) {
    if (level == request.getRequestLevel()) {
      this.echo(request);
    } else {
      if (this.nextHandler != null) {
        this.nextHandler.handleMessage(request);
      } else {
        System.out.Println("end");
      }
    }
  }
  public abstract void echo(Request request);
}
//定义一个具体handlerA
public class HandlerA extends Handler {
  public Handler(int level) {
    super(level);
  }
  @Override
  public void echo(Request request) {
    System.out.println("我是处理者1,我正在处理A规则");
  }
}
...
//客户端实现
class Client {
  public static void main(String[] args) {
    HandleRuleA handleRuleA = new HandleRuleA(1);
    HandleRuleB handleRuleB = new HandleRuleB(2);
    handleRuleA.setNextHandler(handleRuleB);  //这是重点，将handleA和handleB串起来
    handleRuleA.echo(new Request());
  }
}

工程实践：

//定义一个抽象的规则
public abstract class BasicRule<CORE_ITEM, T extends RuleContext<CORE_ITEM>>{
  //有两个方法，evaluate用于判断是否经过规则执行，execute用于执行具体的规则内容。
  public abstract boolean evaluate(T context);
  public abstract void execute(T context) {
}

//定义所有的规则具体实现
//规则1：判断服务可用性
public class ServiceAvailableRule extends BasicRule<UserPortrait, UserPortraitRuleContext> {
  @Override
  public boolean evaluate(UserPortraitRuleContext context) {
    TakeawayUserPortraitBasicInfo basicInfo = context.getBasicInfo();
    if (basicInfo.isServiceFail()) {
      return false;
    }
    return true;
  }
  @Override
  public void execute(UserPortraitRuleContext context) {}
}
//规则2：判断当前用户属性是否符合当前资源位投放的用户属性要求
public class UserGroupRule extends BasicRule<UserPortrait, UserPortraitRuleContext> {
  @Override
  public boolean evaluate(UserPortraitRuleContext context) {}

  @Override
  public void execute(UserPortraitRuleContext context) {
    UserPortrait userPortraitPO = context.getData();
    if(userPortraitPO.getUserGroup() == context.getBasicInfo().getUserGroup().code) {
      context.setValid(true);
    } else {
      context.setValid(false);
    }
  }
}
//规则3：判断当前用户是否在投放城市，具体逻辑省略
public class CityInfoRule extends BasicRule<UserPortrait, UserPortraitRuleContext> {}
//规则4：根据用户的活跃度进行资源过滤，具体逻辑省略
public class UserPortraitRule extends BasicRule<UserPortrait, UserPortraitRuleContext> {} 

//我们通过spring将这些规则串起来组成一个一个请求链
<bean name="serviceAvailableRule" class="com.dianping.takeaway.ServiceAvailableRule"/>
<bean name="userGroupValidRule" class="com.dianping.takeaway.UserGroupRule"/>
<bean name="cityInfoValidRule" class="com.dianping.takeaway.CityInfoRule"/>
<bean name="userPortraitRule" class="com.dianping.takeaway.UserPortraitRule"/>

<util:list id="userPortraitRuleChain" value-type="com.dianping.takeaway.Rule">
    <ref bean="serviceAvailableRule"/>
    <ref bean="userGroupValidRule"/>
    <ref bean="cityInfoValidRule"/>
    <ref bean="userPortraitRule"/>
</util:list>

//规则执行
public class DefaultRuleEngine{
  @Autowired
  List<BasicRule> userPortraitRuleChain;
  public void invokeAll(RuleContext ruleContext) {
    for(Rule rule : userPortraitRuleChain) {
      rule.evaluate(ruleContext)
    }
  }
}

责任链模式最重要的优点就是解耦，将客户端与处理者分开，客户端不需要了解是哪个处理者对事件进行处理，处理者也不需要知道处理的整个流程。在我们的系统中，后台的过滤规则会经常变动，规则和规则之间可能也会存在传递关系，通过责任链模式，我们将规则与规则分开，将规则与规则之间的传递关系通过Spring注入到List中，形成一个链的关系。当增加一个规则时，只需要实现BasicRule接口，然后将新增的规则按照顺序加入Spring中即可。当删除时，只需删除相关规则即可，不需要考虑代码的其他逻辑。从而显著地提高了代码的灵活性，提高了代码的开发效率，同时也保证了系统的稳定性。