美团点评Leaf双buffer思想

本是古典何须时尚 2022-11-05 10:58 292阅读 0赞

### 文章目录 ###

*  Leaf——美团点评分布式ID生成系统
 *  优化
 *  代码
 *  思路
 *  优化

# Leaf——美团点评分布式ID生成系统 #

[点我，跳过去瞄一眼][Link 1]

# 优化 #

> 在文章中也讲到关于优化，有个双buffer的情况

下面是我关于双buffer的一个设计思路，然后生成id的话使用随机，（ps：我们后台是使用雪花算法生成，这里偷下懒）

# 代码 #

package com.example.demo;
    
    import com.alibaba.fastjson.JSON;
    import org.slf4j.Logger;
    import org.slf4j.LoggerFactory;
    import org.springframework.stereotype.Component;
    
    import javax.annotation.PostConstruct;
    import java.math.BigDecimal;
    import java.math.RoundingMode;
    import java.util.ArrayList;
    import java.util.List;
    import java.util.concurrent.ThreadLocalRandom;
    import java.util.concurrent.atomic.AtomicInteger;
    import java.util.concurrent.atomic.AtomicLong;
    
    /** * Created on 2021/3/5. * 只能注入去使用 * * @author yangsen */
    @Component
    public class MyIdUtils { 
    
        @PostConstruct
        public void initClass(){ 
            init();
        }
        
        private static Logger logger = LoggerFactory.getLogger(MyIdUtils.class);
    
        private int bufferMaxSize = 30;
    
        private List<Integer> buffer1 = new ArrayList<>();
    
        private List<Integer> buffer2 = new ArrayList<>();
    
        private AtomicLong number = new AtomicLong(0);
    
        private AtomicInteger status = new AtomicInteger(0);
    
        private MyIdUtils() { 
    
        }
    
        public static void main(String[] args) { 
            MyIdUtils utils = new MyIdUtils();
            utils.init();
            for(int i = 0;i<50;i++){ 
                new Thread(() -> { 
                    logger.info(JSON.toJSONString(utils.getIdList(4)));
                    logger.info(JSON.toJSONString(utils.getIdList(4)));
                    logger.info(JSON.toJSONString(utils.getIdList(7)));
                    logger.info(JSON.toJSONString(utils.getIdList(9)));
                }).start();
            }
    
        }
    
    
        public List<Integer> getIdList(Integer size) { 
            //判断当前buffer1消耗了多少数量
            synchronized(this){ 
                if (number.intValue() % 2 == 0) { 
                    //在第一个buffer
                    return getList(size, buffer1, buffer2);
                } else { 
                    return getList(size, buffer2, buffer1);
                }
            }
        }
    
        private List<Integer> getList(Integer size, List<Integer> firstList, List<Integer> lastList) { 
            while (status.get()!=0){ 
                try { 
                    Thread.sleep(100);
                } catch (InterruptedException e) { 
                    e.printStackTrace();
                }
            }
            BigDecimal consumeSize = new BigDecimal(String.valueOf(size));
            BigDecimal maxSize = new BigDecimal(String.valueOf(bufferMaxSize));
            //这个100实际业务应该是qps的6倍
            double level = maxSize.subtract(consumeSize).divide(maxSize, 3, RoundingMode.FLOOR).doubleValue();
            logger.info("level:" + level + "," + firstList.size() + "," + lastList.size());
            if (level <= 0.9 && lastList.size() == 0) { 
                //就是消耗超过10%的时候，初始化下一个buffer2
                status.incrementAndGet();
                new Thread(() -> { 
                    logger.info("第二个buffer init...");
                    for (int i = 0; i < bufferMaxSize; i++) { 
                        lastList.add(ThreadLocalRandom.current().nextInt(0, 1000));
                    }
                    status.set(0);
                }).start();
                while (status.get()!=0){ 
                    try { 
                        Thread.sleep(100);
                    } catch (InterruptedException e) { 
                        e.printStackTrace();
                    }
                }
            }
            if (firstList.size() < size) { 
                logger.info("第二个buffer拿...");
                //buffer1.size 一个很大的值，是平时qps的6倍。如果这时消耗值大于buffer1的数量，说明buffer1快没了
                int lastSize = size - firstList.size();
                List<Integer> list = lastList.subList(0, lastSize);
                List<Integer> resultList = new ArrayList<>(firstList);
                resultList.addAll(list);
                logger.info("number:" + number.incrementAndGet());
                //清空
                lastList.removeAll(list);
                firstList.removeAll(resultList);
                return resultList;
            }
            logger.info("第一个buffer拿...");
            List<Integer> list = new ArrayList<>(firstList.subList(0, size));
            firstList.removeAll(list);
            return list;
        }
    
        public void init() { 
            logger.info("第一个buffer init...");
            for (int i = 0; i < bufferMaxSize; i++) { 
                buffer1.add(ThreadLocalRandom.current().nextInt(0, 1000));
            }
        }
    
    }

# 思路 #

1.  首先有两个buffer，buffer1，buffer2
2.  一上来肯定先初始化buffer1，最大值在那篇文章也讲了一般是Qps的6倍数（保证吞吐性）
3.  然后批量进行获取唯一id，首先从buffer1拿，这里不存在说一次性把整个buffer1拿完，像集群一起获取的话，这个buffer1的数量也是设计很大，取值的话就取完，然后buffer1剔除这些值。
4.  如果说这时消耗的量已经占据整个buffer1数量的10%，会去初始化buffer2，来增加切换buffer的时候的柔顺。
5.  细节，切换的时候就是buffer1不够去拿buufer2的时候，这里用了AtomicLong去控制一下具体路由到哪个buffer
6.  然后有时多线程的话考虑到一个并发安全性，在getIdList的方法加了锁
7.  以及在初始化buffer2的时候，加了个status，来控制等到buffer2初始化完才能取值。
8.  一开始是buffer1，用完之后是buffer2，buffer2用完之后，把他们两调换下位置，循环往复

# 优化 #

1.  随机数换成雪花算法
2.  锁的那里需要再细化
3.  等待buffer2初始化完成之后，sleep那里也需要再优化优化

[Link 1]: https://tech.meituan.com/2017/04/21/mt-leaf.html

发表评论取消回复

表情：

评论列表（有 0 条评论，292人围观）

还没有评论，来说两句吧...

相关阅读

相关美团 Leaf分布式ID解决方案

前言看了一下美团的分布式ID的解决方案，谈谈自己的理解和思考。其中参考博客就是美团的分布式ID leaf的链接，可以直接跳转去看。 Leaf-segment 数...

「爱情、让人受尽委屈。」/ 2024年04月17日 15:19/ 0 赞/ 86 阅读

相关 Leaf：美团分布式ID生成服务开源

Leaf是美团基础研发平台推出的一个分布式ID生成服务，名字取自德国哲学家、数学家莱布尼茨的一句话：“There are no two identical leaves in

你的名字/ 2023年10月18日 15:21/ 0 赞/ 139 阅读

相关美团点评的DBProxy实践

本文整理自美团点评技术沙龙第10期：数据库技术架构与实践。美团点评技术沙龙由美团点评技术团队主办，每月一期，每期沙龙邀请美团点评及其它互联网公司的技术专家分享来自一线的实践

朱雀/ 2023年10月17日 19:41/ 0 赞/ 161 阅读

相关 Leaf——美团点评分布式ID生成系统

背景在复杂分布式系统中，往往需要对大量的数据和消息进行唯一标识。如在美团点评的金融、支付、餐饮、酒店、猫眼电影等产品的系统中，数据日渐增长，对数据分库分表后需要有一个唯

我不是女神ヾ/ 2023年10月17日 19:28/ 0 赞/ 73 阅读

相关美团Leaf实战（分布式Id算法）

文章目录 1、 Leaf-segment号段模式 1.1 数据库配置 1.2 导入并修改leaf项目 1.3 Leaf-se

深藏阁楼爱情的钟/ 2023年10月11日 17:16/ 0 赞/ 39 阅读

相关美团点评Leaf双buffer思想

文章目录 Leaf——美团点评分布式ID生成系统优化代码思路优化 Leaf——美团点评分布式ID生成系统 [点我，跳过去瞄一

本是古典何须时尚/ 2022年11月05日 10:58/ 0 赞/ 293 阅读

相关美团点评分布式ID生成系统Leaf介绍

美团点评分布式ID生成系统Leaf介绍 1. Leaf-segment数据库方案第一种Leaf-segment方案，在使用数据库的方案

旧城等待，/ 2022年06月15日 02:36/ 0 赞/ 471 阅读

相关美团点评——改试卷

题目描述：在上小学的时候，我们经常碰到这样的事情：考试完后老师懒得改试卷，于是让我们同桌互换试卷后为对方批改。但是后来老师发现这样做容易出现作弊，于是他想了一个新办法。老师

缺乏、安全感/ 2022年06月09日 10:30/ 0 赞/ 245 阅读

相关美团点评——K的倍数

题目描述：序列中任意个连续的元素组成的子序列称为该序列的子串。现在给你一个序列P和一个整数K，询问元素和是K的倍数的子串的足底啊长度。比如序列\[1,2,3,4,5

我不是女神ヾ/ 2022年06月09日 10:29/ 0 赞/ 305 阅读

相关 Leaf——美团点评分布式ID生成系统

Leaf——美团点评分布式ID生成系统照东 ·2017-04-21 18:34 背景在复杂分布式系统中，往往需要对大量的数据和消息进行唯一标识。如在美团点评的

水深无声/ 2022年05月17日 05:59/ 0 赞/ 297 阅读