性能文章>分布式ID|源码解析美团Leaf双Buffer优化方案>

分布式ID|源码解析美团Leaf双Buffer优化方案原创

10月前
285246
  • 分布式ID的使用场景

  • 基于MySql的初步方案

  • 第一次优化:Leaf-segment数据库方案

  • 第二次优化:Leaf-segment 双buffer优化

  • 源码解析双buffer优化方案

背景

在复杂分布式系统中,往往需要对大量的数据和消息进行唯一标识。如在美团点评的金融、支付、餐饮、酒店、猫眼电影等产品的系统中,数据日渐增长,对数据分库分表后需要有一个唯一ID来标识一条数据或消息,数据库的自增ID显然不能满足需求;特别一点的如订单、骑手、优惠券也都需要有唯一ID做标识。
此时一个能够生成全局唯一ID的系统是非常必要的。
概括下来,那业务系统对ID号的要求有哪些呢?
1、全局唯一性:不能出现重复的ID号,既然是唯一标识,这是最基本的要求。
2、趋势递增:在MySQL InnoDB引擎中使用的是聚集索引,由于多数RDBMS使用B-tree的数据结构来存储索引数据,在主键的选择上面我们应该尽量使用有序的主键保证写入性能。
3、单调递增:保证下一个ID一定大于上一个ID,例如事务版本号、IM增量消息、排序等特殊需求。
4、信息安全:如果ID是连续的,恶意用户的扒取工作就非常容易做了,直接按照顺序下载指定URL即可;如果是订单号就更危险了,竞对可以直接知道我们一天的单量。所以在一些应用场景下,会需要ID无规则、不规则。
上述1、2、3对应三类不同的场景,3和4的需求还是互斥的,无法使用同一个方案满足。
同时除了对ID号码自身的要求,业务还对ID号生成系统的可用性要求极高,想象一下,如果ID生成系统瘫痪,整个美团点评支付、优惠券发券、骑手派单等关键动作都无法执行,这就会带来一场灾难。
由此总结下一个ID生成系统应该做到如下几点:
平均延迟和TP999延迟都要尽可能低;
可用性5个9;
高QPS。

数据库生成

以MySQL举例,利用给字段设置auto_increment_increment和auto_increment_offset来保证ID自增,每次业务使用下列SQL读写MySQL得到ID号。
1 begin;
2 REPLACE INTO Tickets64 (stub) VALUES ('a');
3 SELECT LAST_INSERT_ID();
4 commit;

这种方案的优缺点如下:
优点:
非常简单,利用现有数据库系统的功能实现,成本小,有DBA专业维护。
ID号单调自增,可以实现一些对ID有特殊要求的业务。
缺点:
强依赖DB,当DB异常时整个系统不可用,属于致命问题。配置主从复制可以尽可能的增加可用性,但是数据一致性在特殊情况下难以保证。主从切换时的不一致可能会导致重复发号。
ID发号性能瓶颈限制在单台MySQL的读写性能。
对于MySQL性能问题,可用如下方案解决:在分布式系统中我们可以多部署几台机器,每台机器设置不同的初始值,且步长和机器数相等。比如有两台机器。设置步长step为2,TicketServer1的初始值为1(1,3,5,7,9,11…)、TicketServer2的初始值为2(2,4,6,8,10…)。
如下所示,为了实现上述方案分别设置两台机器对应的参数,TicketServer1从1开始发号,TicketServer2从2开始发号,两台机器每次发号之后都递增2。
1 TicketServer1:
2 auto-increment-increment = 2
3 auto-increment-offset = 1
4
5 TicketServer2:
6 auto-increment-increment = 2
7 auto-increment-offset = 2
假设我们要部署N台机器,步长需设置为N,每台的初始值依次为0,1,2…N-1,那么整个架构就变成了如下图所示:

这种架构貌似能够满足性能的需求,但有以下几个缺点:
系统水平扩展比较困难,比如定义好了步长和机器台数之后,如果要添加机器该怎么做?假设现在只有一台机器发号是1,2,3,4,5(步长是1),这个时候需要扩容机器一台。可以这样做:把第二台机器的初始值设置得比第一台超过很多,比如14(假设在扩容时间之内第一台不可能发到14),同时设置步长为2,那么这台机器下发的号码都是14以后的偶数。然后摘掉第一台,把ID值保留为奇数,比如7,然后修改第一台的步长为2。让它符合我们定义的号段标准,对于这个例子来说就是让第一台以后只能产生奇数。扩容方案看起来复杂吗?貌似还好,现在想象一下如果我们线上有100台机器,这个时候要扩容该怎么做?简直是噩梦。所以系统水平扩展方案复杂难以实现。
ID没有了单调递增的特性,只能趋势递增,这个缺点对于一般业务需求不是很重要,可以容忍。
数据库压力还是很大,每次获取ID都得读写一次数据库,只能靠堆机器来提高性能。

Leaf方案实现

There are no two identical leaves in the world

德国哲学家、数学家莱布尼茨

综合对比上述几种方案,每种方案都不完全符合我们的要求。所以Leaf分别在上述第二种和第三种方案上做了相应的优化,实现了Leaf-segment和Leaf-snowflake方案。
Leaf-segment数据库方案
第一种Leaf-segment方案,在使用数据库的方案上,做了如下改变:- 原方案每次获取ID都得读写一次数据库,造成数据库压力大。改为利用proxy server批量获取,每次获取一个segment(step决定大小)号段的值。用完之后再去数据库获取新的号段,可以大大的减轻数据库的压力。- 各个业务不同的发号需求用biz_tag字段来区分,每个biz-tag的ID获取相互隔离,互不影响。如果以后有性能需求需要对数据库扩容,不需要上述描述的复杂的扩容操作,只需要对biz_tag分库分表就行。
数据库表设计如下:
1  CREATE TABLE `leaf_alloc` (
2   `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT COMMENT '主键',
3  `biz_tag` varchar(128) NOT NULL DEFAULT '' COMMENT '标签名',
4  `max_id` bigint(20) NOT NULL DEFAULT '1' COMMENT '目前Segment的id',
5  `step` int(11) NOT NULL COMMENT '步长',
6   `desc` varchar(256) NOT NULL DEFAULT '' COMMENT '描述',
7   `create_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '创建时间',
8   `update_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '更新时间',
9   PRIMARY KEY (`id`) USING BTREE,
10   UNIQUE KEY `uk_biz_tag` (`biz_tag`) USING BTREE
11)  ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8mb4
重要字段说明:
biz_tag用来区分业务,
max_id表示该biz_tag目前所被分配的ID号段的最大值,
step表示每次分配的号段长度。
原来获取ID每次都需要写数据库,现在只需要把step设置得足够大,比如1000。那么只有当1000个号被消耗完了之后才会去重新读写一次数据库。读写数据库的频率从1减小到了1/step,大致架构如下图所示:

test_tag在第一台Leaf机器上是1~1000的号段,当这个号段用完时,会去加载另一个长度为step=1000的号段,假设另外两台号段都没有更新,这个时候第一台机器新加载的号段就应该是3001~4000。同时数据库对应的biz_tag这条数据的max_id会从3000被更新成4000,更新号段的SQL语句如下:
begin
UPDATE leaf_alloc SET max_id=max_id+step WHERE biz_tag=xxx
SELECT tag, max_id, step FROM leaf_alloc WHERE biz_tag=xxx
commit
说明:此处使用了数据库事务。

这种模式有以下优缺点:

优点:
Leaf服务可以很方便的线性扩展,性能完全能够支撑大多数业务场景。
ID号码是趋势递增的8byte的64位数字,满足上述数据库存储的主键要求。
容灾性高:Leaf服务内部有号段缓存,即使DB宕机,短时间内Leaf仍能正常对外提供服务。
可以自定义max_id的大小,非常方便业务从原有的ID方式上迁移过来。

缺点:
ID号码不够随机,会泄露发号量信息,不太安全。
TP999数据波动大,当号段使用完之后还是会hang在更新数据库的I/O上,TP999数据会出现偶尔的尖刺。
DB宕机会造成整个系统不可用。

双buffer优化

对于第二个缺点,Leaf-segment做了一些优化,简单的说就是:
Leaf 取号段的时机是在号段消耗完的时候进行的,也就意味着号段临界点的ID下发时间取决于下一次从DB取回号段的时间,并且在这期间进来的请求也会因为DB号段没有取回来,导致线程阻塞。如果请求DB的网络和DB的性能稳定,这种情况对系统的影响是不大的,但是假如取DB的时候网络发生抖动,或者DB发生慢查询就会导致整个系统的响应时间变慢。
为此,我们希望DB取号段的过程能够做到无阻塞,不需要在DB取号段的时候阻塞请求线程,即当号段消费到某个点时就异步的把下一个号段加载到内存中。而不需要等到号段用尽的时候才去更新号段。这样做就可以很大程度上的降低系统的TP999指标。
详细实现如下图所示:

采用双buffer的方式,Leaf服务内部有两个号段缓存区segment。当前号段已下发10%时,如果下一个号段未更新,则另启一个更新线程去更新下一个号段。当前号段全部下发完后,如果下个号段准备好了则切换到下个号段为当前segment接着下发,循环往复。
每个biz-tag都有消费速度监控,通常推荐segment长度设置为服务高峰期发号QPS的600倍(10分钟),这样即使DB宕机,Leaf仍能持续发号10-20分钟不受影响。

每次请求来临时都会判断下个号段的状态,从而更新此号段,所以偶尔的网络抖动不会影响下个号段的更新。

Leaf高可用容灾

对于第三点“DB可用性”问题,我们目前采用一主两从的方式,同时分机房部署,Master和Slave之间采用半同步方式同步数据。同时使用数据库中间件做主从切换。
当然这种方案在一些情况会退化成异步模式,甚至在非常极端情况下仍然会造成数据不一致的情况,但是出现的概率非常小。
如果你的系统要保证100%的数据强一致,可以选择使用“类Paxos算法”实现的强一致MySQL方案,如MySQL 5.7前段时间刚刚GA的MySQL Group Replication。

但是运维成本和精力都会相应的增加,根据实际情况选型即可。

同时Leaf服务分IDC部署。服务调用的时候,根据负载均衡算法会优先调用同机房的Leaf服务。在该IDC内Leaf服务不可用的时候才会选择其他机房的Leaf服务。同时服务治理平台OCTO还提供了针对服务的过载保护、一键截流、动态流量分配等对服务的保护措施。

双buffer优化方案的源码解析

(1)Leaf服务启动时进行数据初始化:

   /**
     * SegmentIDGenImpl初始化到Spring容器时会被调用
     *
     * @return
     */
    @Override
    public boolean init() {
        logger.info("Init ...");
        // 确保加载到kv后才初始化成功
        /**
         * 把DB中的biz_tag【key】、max_id、step
         * 初始化到jvm中的 Map<String, SegmentBuffer> cache 中
         */
        updateCacheFromDb();
        /**
         * 更新标识initOK
         * 说明:
         * 使用volatile解决变量initOK对多线程的可见性问题
         * private volatile boolean initOK = false;
         */
        initOK = true;
        /**
         * 把DB中新insert的biz_tag【key】、max_id、step
         * 加入到Map<String, SegmentBuffer> cache 
         */
        updateCacheFromDbAtEveryMinute();
        return initOK;
    }

(2)提供分布式ID服务的API
com.sankuai.inf.leaf.server.controller.LeafController#getSegmentId

    /**
     * 双buffer优化方案API
     * 根据key【业务标识(biz_tag)】来生成分布式ID
     *
     * @param key
     * @return 新的ID
     */
    @RequestMapping(value = "/api/segment/get/{key}")
    public String getSegmentId(@PathVariable("key") String key) {
        return get(key, segmentService.getId(key));
    }

com.sankuai.inf.leaf.segment.SegmentIDGenImpl#get

    /**
     * 双buffer架构获取分布式ID
     *
     * @param key 业务标识
     * @return 新的分布式ID:业务ID+最大的数字
     */
    @Override
    public Result get(final String key) {
        /**
         * 检查数据库里的业务标识biz_tag、步长step、max_id都加载到内存中了
         */
        if (!initOK) {
            /**
             * 没有加载完成,后面没有check的逻辑,得到的分布式ID很大可能性是不对的。
             * 要确保服务的确定性,此时抛出异常是合适的
             */
            return new Result(EXCEPTION_ID_IDCACHE_INIT_FALSE, Status.EXCEPTION);
        }
        if (cache.containsKey(key)) {
            /**
             * 如果业务标识存在,则要使用步长step和max_id来生成分布式ID
             */
            SegmentBuffer buffer = cache.get(key);
            if (!buffer.isInitOk()) {
                /**
                 * 如果max_id数据没有准备好,则
                 */
                synchronized (buffer) {
                    /**
                     * 不同的Jvm是不同的号段。
                     * 只需要在jvm范围内确保线程安全即可
                     */
                    if (!buffer.isInitOk()) {
                        try {
                            /**
                             * 更新号段
                             */
                            updateSegmentFromDb(key, buffer.getCurrent());
                            logger.info("Init buffer. Update leafkey {} {} from db", key, buffer.getCurrent());
                            buffer.setInitOk(true);
                        } catch (Exception e) {
                            logger.warn("Init buffer {} exception", buffer.getCurrent(), e);
                        }
                    }
                }
            }
            /**
             * 如果数据库里的数据初始化到jvm内存完成,直接getAndIncrement获取自增的id
             */
            return getIdFromSegmentBuffer(cache.get(key));
        }
        /**
         * 如果业务标识key在jvm中不存在,则无法继续后续处理,抛异常
         */
        return new Result(EXCEPTION_ID_KEY_NOT_EXISTS, Status.EXCEPTION);
    }

com.sankuai.inf.leaf.segment.SegmentIDGenImpl#updateSegmentFromDb


    /**
     * 更新号段
     * (1)设置号段的起始值:maxId-step
     * (2)设置jvm当前号段的maxId
     * (3)设置步长step
     *
     * @param key     指定的业务标识biz_tag
     * @param segment 存放了新的号段范围的Segment
     */
    public void updateSegmentFromDb(String key, Segment segment) {
        StopWatch sw = new Slf4JStopWatch();
        SegmentBuffer buffer = segment.getBuffer();
        LeafAlloc leafAlloc;
        if (!buffer.isInitOk()) {
            /**
             * 如果jvm中的号段信息没有完成db到jvm的初始化
             * 则:
             * (1)获取下一个号段的值
             * maxId=maxId+step
             * (2)更新jvm中的step,有可能step被更新过了
             *
             * updateMaxIdAndGetLeafAlloc的说明:
             * (1)更新maxId
             * (2)查询最新maxId,step的操作要在一个事务中。
             * 这个地方展开讲一下:此处是使用数据库更新行锁来达到一个全局互斥锁的效果
             *
             */
            leafAlloc = dao.updateMaxIdAndGetLeafAlloc(key);
            buffer.setStep(leafAlloc.getStep());
            buffer.setMinStep(leafAlloc.getStep());//leafAlloc中的step为DB中的step
        } else if (buffer.getUpdateTimestamp() == 0) {
            /**
             * 第一次更新号段信息:
             * (1)获取下一个号段的值 maxId=maxId+step
             * (2)更新jvm中的step,有可能step被更新过了
             * (3)更新updateTimestamp
             *
             * updateMaxIdAndGetLeafAlloc的说明:
             * (1)更新maxId
             * (2)查询最新maxId,step的操作要在一个事务中。
             * 这个地方展开讲一下:此处是使用数据库更新行锁来达到一个全局互斥锁的效果
             *
             */
            leafAlloc = dao.updateMaxIdAndGetLeafAlloc(key);
            buffer.setUpdateTimestamp(System.currentTimeMillis());
            buffer.setStep(leafAlloc.getStep());
            buffer.setMinStep(leafAlloc.getStep());//leafAlloc中的step为DB中的step
        } else {
            /**
             * 如果号段消费超过预期,且step小于最大步长不超过100,0000
             * 则按下面的规则加大step
             */
            long duration = System.currentTimeMillis() - buffer.getUpdateTimestamp();
            int nextStep = buffer.getStep();
            if (duration < SEGMENT_DURATION) {
                if (nextStep * 2 > MAX_STEP) {
                    //do nothing
                } else {
                    nextStep = nextStep * 2;
                }
            } else if (duration < SEGMENT_DURATION * 2) {
                //do nothing with nextStep
            } else {
                nextStep = nextStep / 2 >= buffer.getMinStep() ? nextStep / 2 : nextStep;
            }
            logger.info("leafKey[{}], step[{}], duration[{}mins], nextStep[{}]", key, buffer.getStep(), String.format("%.2f", ((double) duration / (1000 * 60))), nextStep);
            LeafAlloc temp = new LeafAlloc();
            temp.setKey(key);
            temp.setStep(nextStep);
            /**
             *
             * updateMaxIdByCustomStepAndGetLeafAlloc说明:
             * (1)更新maxId、step
             * (2)查询最新maxId,step的操作要在一个事务中。
             * 这个地方展开讲一下:此处是使用数据库更新行锁来达到一个全局互斥锁的效果
             * 与updateMaxIdAndGetLeafAlloc相比,多更新了step
             */
            leafAlloc = dao.updateMaxIdByCustomStepAndGetLeafAlloc(temp);
            buffer.setUpdateTimestamp(System.currentTimeMillis());
            buffer.setStep(nextStep);
            buffer.setMinStep(leafAlloc.getStep());//leafAlloc的step为DB中的step
        }
        // must set value before set max
        /**
         * (1)设置号段的起始值:maxId-step
         * (2)设置jvm当前号段的maxId
         * (3)设置步长step
         */
        long value = leafAlloc.getMaxId() - buffer.getStep();
        segment.getValue().set(value);
        segment.setMax(leafAlloc.getMaxId());
        segment.setStep(buffer.getStep());
        sw.stop("updateSegmentFromDb", key + " " + segment);
    }
Leaf动态调整Step:

假设服务QPS为Q,号段长度为L,号段更新周期为T,那么Q * T = L。
最开始L长度是固定的,导致随着Q的增长,T会越来越小。
但是Leaf本质的需求是希望T是固定的。
那么如果L可以和Q正相关的话,T就可以趋近一个定值了。
所以Leaf每次更新号段的时候,根据上一次更新号段的周期T和号段长度step,来决定下一次的号段长度nextStep:

T < 15min,nextStep = step * 2
15min < T < 30min,nextStep = step
T > 30min,nextStep = step / 2

至此,满足了号段消耗稳定趋于某个时间区间的需求。当然,面对瞬时流量几十、几百倍的暴增,该种方案仍不能满足可以容忍数据库在一段时间不可用、系统仍能稳定运行的需求。因为本质上来讲,Leaf虽然在DB层做了些容错方案,但是号段方式的ID下发,最终还是需要强依赖DB。

com.sankuai.inf.leaf.segment.SegmentIDGenImpl#getIdFromSegmentBuffer

    /**
     * 从SegmentBuffer中获取biz_tag对应号段在内存中的最大值
     * 最大值超出当前号段的最大值后,要更新jvm中的号段,然后再获取最大值
     *
     * @param buffer
     * @return 当前jvm中biz_tag对应号段在内存中的最大值
     */
    public Result getIdFromSegmentBuffer(final SegmentBuffer buffer) {
        /**
         * 为解决超出jvm已经申领号段范围的问题,增加while(true)
         * 1. 如果超过jvm中的号段范围,更新下一个号段
         * 2. 将最新的max_id更新到数据库,
         * 3、将最新的数据加载到jvm,
         * 4、然后再获取当前号段的getAndIncrement
         */
        while (true) {
            /**
             * 使用ReadWriteLock解决getAndIncrement获取最新id时的线程安全问题
             */
            buffer.rLock().lock();
            try {
                final Segment segment = buffer.getCurrent();
                if (!buffer.isNextReady() && (segment.getIdle() < 0.9 * segment.getStep()) && buffer.getThreadRunning().compareAndSet(false, true)) {
                    /**
                     * 如果(1)下一个号段没有ready
                     * 且(2)当前号段已下发10%时,如果下一个号段未更新,
                     * 且(3)更新下一个号段的线程
                     * 则另启一个更新线程去更新下一个号段
                     */
                    service.execute(new Runnable() {
                        @Override
                        public void run() {
                            /**
                             * 开始准备下一个号段的号段范围
                             */
                            Segment next = buffer.getSegments()[buffer.nextPos()];
                            /**
                             * 一个标识,用来标识下一个号段范围是否更新完成
                             */
                            boolean updateOk = false;
                            try {
                                /**
                                 * 执行 更新下一个号段 的操作
                                 */
                                updateSegmentFromDb(buffer.getKey(), next);
                                /**
                                 * 号段范围更新完成,更新标识
                                 */
                                updateOk = true;
                                logger.info("update segment {} from db {}", buffer.getKey(), next);
                            } catch (Exception e) {
                                logger.warn(buffer.getKey() + " updateSegmentFromDb exception", e);
                            } finally {
                                if (updateOk) {
                                    /**
                                     * 更新状态时,打开写锁。获取id的过程都卡住
                                     */
                                    buffer.wLock().lock();
                                    /**
                                     * 下一个号段已更新完成
                                     */
                                    buffer.setNextReady(true);
                                    /**
                                     * 更新号段的线程的状态设置为非运行中
                                     */
                                    buffer.getThreadRunning().set(false);
                                    /**
                                     * 更新下一个号段的所有状态更新完成,释放写锁,当前jvm可以正常生成指定biz_tag的分布式id
                                     */
                                    buffer.wLock().unlock();
                                } else {
                                    /**
                                     * 下一个号段没有更新成功,则将更新线程退出前将线程状态置为false
                                     */
                                    buffer.getThreadRunning().set(false);
                                }
                            }
                        }
                    });
                }
                /**
                 * getAndIncrement来获取下一个id
                 */
                long value = segment.getValue().getAndIncrement();
                if (value < segment.getMax()) {
                    /**
                     * 如果新的id在号段范围内,则获取成功
                     */
                    return new Result(value, Status.SUCCESS);
                }
            } finally {
                /**
                 * 第一轮获取id,unlock。
                 * 因为readLock与writeLock是互斥,此处不释放readLock则会阻塞 更新线程去更新下一个号段
                 */
                buffer.rLock().unlock();
            }
            /**
             * 自旋等待更新号段线程执行完成
             */
            waitAndSleep(buffer);
            /**
             * 因为当前并不能100%确定更新线程已经成功执行完成
             * 加写锁。本方法入口处的 buffer.rLock().lock();也会被阻塞
             */
            buffer.wLock().lock();
            try {
                final Segment segment = buffer.getCurrent();
                /**
                 * getAndIncrement获取id
                 */
                long value = segment.getValue().getAndIncrement();
                if (value < segment.getMax()) {
                    return new Result(value, Status.SUCCESS);
                }
                /**
                 * 走到此处,说明更新线程还没有执行完成
                 */
                if (buffer.isNextReady()) {
                    /**
                     * 更新线程操作完成。
                     * 则切换SegmentBuffer
                     */
                    buffer.switchPos();
                    /**
                     * 如果新SegmentBuffer用完了,然后再启动更新线程
                     * 更新线程的运行状态置为false。
                     */
                    buffer.setNextReady(false);
                } else {
                    /**
                     * 到此处,说明两个SegmentBuffer都没有ready,是出问题了
                     */
                    logger.error("Both two segments in {} are not ready!", buffer);
                    return new Result(EXCEPTION_ID_TWO_SEGMENTS_ARE_NULL, Status.EXCEPTION);
                }
            } finally {
                /**
                 * 释放wLock,不然这个整个方法就会被阻塞了
                 */
                buffer.wLock().unlock();
            }
        }
    }

com.sankuai.inf.leaf.segment.SegmentIDGenImpl#waitAndSleep

    /**
     * 自旋等待号段更新线程更新完成
     * 最多等待100s
     *
     * @param buffer
     */
    private void waitAndSleep(SegmentBuffer buffer) {
        int roll = 0;
        while (buffer.getThreadRunning().get()) {
            roll += 1;
            if (roll > 10000) {
                try {
                    TimeUnit.MILLISECONDS.sleep(10);
                    break;
                } catch (InterruptedException e) {
                    logger.warn("Thread {} Interrupted", Thread.currentThread().getName());
                    break;
                }
            }
        }
    }

详见:https://github.com/helloworldtang/Leaf.git


相关信息汇总

1、可用性5个9

2、什么是聚集索引

MySQL数据库中innodb存储引擎,B+树索引可以分为聚簇索引(也称聚集索引,clustered index)和辅助索引(有时也称非聚簇索引或二级索引,secondary index,non-clustered index)。
将索引列字段和行记录数据维护在了一起,通过聚集索引能直接获取到整行数据。也就是说,索引的叶子节点包含了完整的一条数据记录。

MySql的Innodb引擎的主键索引就是基于聚集索引实现的
例如数据库中有一张 user 表,id 为主键

那么基于这张表的主键 id 建立的聚集索引,如下图所示

3、非聚集索引


Innodb 以 age 建立的非聚集索引如下图

聚集索引可以避免“回表”,为什么聚集索引只能存在一个呢?
是为了节省磁盘空间 和 保证数据的一致性。
回表:当通过非聚集索引来查询数据时,存储引擎会根据索引字段定位到最底层的叶子节点,并通过叶子节点获得指向主键索引的主键 id,然后通过主键 id 去主键索引(聚集索引)上找到一个完整的行记录.这个过程被称为 回表

                         [K2,K5]
                          /    \
                   [K0,K1]   [K3,K4,K6,K7]

    /          |        |         |         \
 [--,K0]    [K0,K1]  [K1,K2]   [K2,K3]  [K3,K4,K5]  [K5,K6]  [K6,K7]  [K7,--]              
       |          |         |         |         |        |        |         |
    [5,6,9]  [2,7,12]  [1,8,16]  [3,4,10]  [13,15,19] [11,14,20] [17,18,21] [22,28,30]

参考
https://www.cnblogs.com/xiaomaomao/p/16196006.html
https://tech.meituan.com/2017/04/21/mt-leaf.html
https://dev.mysql.com/doc/refman/5.7/en/group-replication.html
https://blog.csdn.net/LO_YUN/article/details/126795183
https://www.processon.com/view/link/643c3d7bec0f2b0724eb208e

 

点赞收藏
bit01
请先登录,查看4条精彩评论吧
快去登录吧,你将获得
  • 浏览更多精彩评论
  • 和开发者讨论交流,共同进步

为你推荐

解锁 ElasticJob 云原生实践的难题

解锁 ElasticJob 云原生实践的难题

【云原生•监控】Micrometer打造SpringBoot服务的可观测能力

【云原生•监控】Micrometer打造SpringBoot服务的可观测能力

一文讲透消息队列RocketMQ实现消费幂等

一文讲透消息队列RocketMQ实现消费幂等

一次 Rancher go 应用内存占用过高问题排查

一次 Rancher go 应用内存占用过高问题排查

6
4