1. 定义

   总桶定义：表示总预算桶的模型

   分桶定义：表示用于分桶模型， 统计使用

   分桶：用于主流程中扣减的分桶，因为性能考虑，使用redis或者其他内存模型进行扣减

   分桶列表:预算桶中预算可用分桶的集合，不可用分桶的集合

2. 理念：

   �空间换取时间

3. 功能列表

   预算创建

   预算追加

   预算使用

   预算回滚

   预算查看

4. 数据模型

   <pre class="cm-s-default" style="color: rgb(89, 89, 89); margin: 0px; padding: 0px; background: none 0% 0% / auto repeat scroll padding-box border-box rgba(0, 0, 0, 0);">---总预算桶定义--
   create table budget_management_bucket(
   id bigint(20) unsigned auto_increment comment '预算id',
   gl_code varchar(20) comment '科目',
   total_quantity bigint(20) commment '总量',
   out_quantity bigint(20) comment '已发放量',
   sharding_quantity bigint(20) comment '单个分桶最多申请预算量',
   bucket_quantity int comment '初始分桶数量',
   adjust_cnt int comment '分桶预算最多可以调整次数',
   type varchar(20) comment '预算应用场景:大促,日常',
   type_rule longtext comment '子预算桶预算申请规则',
   status varchar(20) comment '状态：未生效，已生效，已失效',
   created_at datetime comment '创建时间',
   updated_at datetime comment '更新时间',
   primary_key (id)
   )
   ----子预算桶定义----
   create table sharding_budget_management_buckect(
   id bigint(20) unsigned auto_increment comment '子预算桶id',
   budget_id bigint(20) comment '预算id',
   sharding_bucket_key varchar(150) comment '分桶key',
   out_quantity bigint(20) comment '已经申请的总量',
   sharding_quantity bigint(20) comment '单个分桶最多申请预算量',
   out_cnt int comment '分桶已经申请次数',
   status varchar(20) comment '在线，离线',
   created_at datetime comment '创建时间',
   updated_at datetime comment '更新时间',
   primary_key (id)
   )

   -------内存key-value结构-----------
   分桶：
   key:分桶key
   value:当前剩余预算量

   分桶列表:
   key: 分桶列表key
   value :在线的分桶，离线的列表要即时删除</pre>

5. 业务架构

   image

6. 创建预算

   image

7. 预算扣减

   image

8. 申请预算

   image

9. 分桶下线

   image

10. 回滚预算

image

11.碎片回收

image

相关解释

1. 全局锁相关解释

   扣减预算的时候不用添加全局锁，redis本来就是单线程，不需要通过锁的方式扣减

   申请预算，分桶下线因为可能涉及到并发的问题，需要添加分桶的全局锁， 不让重复的操作

2. 预算应用场景

   分为大促模式和日常模式，大促模式一次性分配完所有的预算。日常模式涉及到预算的压缩，比如1年的可以压缩到每天分配，那么假如1年的预算是365万，那么每天的预算可以压缩到1万，预算申请的时候控制。

   日常模式中会存在子预算桶预算申请规则，规则可配置：与日期强相关(比如整点可以申请，每天可以申请，每月可以申请),与日期不相关(用完即可申请)

3. 为什么要使用分桶

上面讲到了空间换取时间的概念，我们尽量避免热点，分桶可以降低集中请求某一点造成的压力，假如一个 redis库的tps可以达到50000，那我们使用10分桶，分别放到10个redis库中，并行处理的时候我们可以达到 500000的tps，方便以后扩展。同时我们可以不局限redis，或者使用其他类型的数据库，不局限redis，不局限noSql。如果要求不高的情况，我们可以将分桶尽量扩大，理论上关系型数据库在分桶够大的时候，也是可以满足相应的指标的。

4.碎片回收

碎片回收是指将每个分桶的预算全部回收到总的桶定义中，然后重新分配预算,类似于jvm中垃圾回收算法中的标记清除算法，所有分桶下线，回收可用预算到总预算桶。再分配可用粪桶

5.分桶创建算法

分桶数量可以指定，如果是数量类的预算,1000数量一个桶，如果金额类的预算1000000一个桶

随机算法样例，真实情况的group是分桶的key

<pre class="cm-s-default" style="color: rgb(89, 89, 89); margin: 0px; padding: 0px; background: none 0% 0% / auto repeat scroll padding-box border-box rgba(0, 0, 0, 0);">package com.constant.hash.demo;

import java.util.*;

/**

• 一致性hash算法达到负载均衡

• 在预算分桶计算可以实现获取平均化的获取每个分桶中的数据避免出现热点的问题，可以动态增加减少节点

• 添加虚拟节点

• @author <a href="mailto:zhaoxiaotao@terminus.io">tony</a>

• com.constant.hash.demo

• 2018/12/14 10:39

• hash-demo
  */
  public class ConsistentHashingWithVirtualNode {
  //真实节点
  private static String[] groups = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111", "192.168.0.3:111", "192.168.0.4:111"};

  //真实节点集合
  private static List<String> realGroups = new LinkedList<>();

  //虚拟节点
  private static SortedMap<Integer, String> virtualNodes = new TreeMap<>();
  //每个真实节点关联的虚拟节点个数
  private static final int VIRTUAL_NODE_NUM = 1000;

  static {
  realGroups.addAll(Arrays.asList(groups));

   //将虚拟节点添加到环上
   for (String realGroup : realGroups) {
       for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {
           String virtualNodeName = getVirtualNodeName(realGroup, i);
           int hash = HashUtil.getHash(virtualNodeName);
           //System.out.println("[" + virtualNodeName + "] lauched @" + hash);
           virtualNodes.put(hash, virtualNodeName);
  
       }
   }
  

  }

  //虚拟节点名称
  private static String getVirtualNodeName(String realName, int num) {
  return realName + "&&VN" + String.valueOf(num);
  }
  //真实节点名称
  private static String getRealNodeName(String virtualName) {
  return virtualName.split("&&")[0];
  }

  //获取节点
  private static String getServer(String widgetKey) {
  int hash = HashUtil.getHash(widgetKey);
  SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
  String virtualNodeName;
  if (subMap == null || subMap.isEmpty()) {
  virtualNodeName = virtualNodes.get(virtualNodes.firstKey());
  } else {
  virtualNodeName = subMap.get(subMap.firstKey());
  }
  return getRealNodeName(virtualNodeName);
  }

  public static void main(String[] args) {
  Map<String, Integer> resMap = new HashMap<>();
  for (int i = 0; i < 1000; i++) {
  Integer widgetId = (int) (Math.random() * 100000);
  String group = getServer(widgetId.toString());
  if (resMap.containsKey(group)) {
  resMap.put(group, resMap.get(group) + 1);
  } else {
  resMap.put(group, 1);
  }
  }

   resMap.forEach((k, v) -> {
       System.out.println("group " + k + ":" + v + "(" + v / 10.0D + "%)");
   });
  

  }
  }</pre>

<pre class="cm-s-default" style="color: rgb(89, 89, 89); margin: 0px; padding: 0px; background: none 0% 0% / auto repeat scroll padding-box border-box rgba(0, 0, 0, 0);">package com.constant.hash.demo;

/**

• fnv1_32_hash算法
• @author <a href="mailto:zhaoxiaotao@terminus.io">tony</a>
• com.constant.hash.demo
• 2018/12/14 10:31
• hash-demo
  */
  public class HashUtil {
  public static int getHash(String str) {
  final int p = 16777619;
  int hash = (int) 2166136261L;
  for (int i = 0; i < str.length(); i++) {
  hash = (hash ^ str.charAt(i)) * p;
  }
  hash += hash << 13;
  hash ^= hash >> 7;
  hash += hash << 3;
  hash ^= hash >> 17;
  hash += hash << 5;
  if (hash < 0) {
  hash = Math.abs(hash);
  }
  return hash;
  }
  }</pre>

碎片收集算法