栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

5.算法进阶——kafka消息查询(二分法)——稀疏索引与B+树索引的对比

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

5.算法进阶——kafka消息查询(二分法)——稀疏索引与B+树索引的对比

Kafka介绍

Kafka 是一款性能强大且相当常用的分布式消息队列,常常用于对流量进行消峰、解耦系统和异步处理部分逻辑以提高性能的场景。
在kafka中,所有的消息都以日志的形式存储。这种日志只允许追加新数据,不允许修改之前文件内容

日志文件的存储方式:每个topic有多个partition,每个patition有多个有序日志段

已知offset,如何查找日志

即如何为日志文件建立一个索引,这里很关键的一个问题在于offset是自然线性增长的,是有序的

我们来看一个topic中一个patition的日志文件格式:

00000000000000000000.log //消息体本身日志
00000000000000000000.index //索引
00000000000000000000.timeindex //时间索引
00000000000000000035.log
00000000000000000035.index
00000000000000000035.timeindex

我理解前面属于相较于物理第一个文件的绝对偏移量,而后面的部分属于相对偏移量。

index文件内容是两种偏移的对应关系,即 相对位置——绝对位置

如图我们可以看见offset的存储并不是连续的,所以我们查找只能查找到一个大概的范围

其实这是一种时空效率的权衡,用稀疏不连续的索引,使用了更少的空间

内存放不下索引文件怎么办

Kafka 的做法是基于 mmap 技术,将硬盘上的文件和内存进行映射;当然由于硬盘的空间可能比内存大很多,所以并不能够直接将内存在物理层面上与磁盘进行一一映射,这里我们需要引入虚拟内存的手段。

几种常见索引对比

MySQL innodb: B+ Tree
Oracle/Mongodb:B Tree
Kafka:稀疏索引

B+ 树就是为了磁盘存储而生,可以减少磁盘的访问次数,同时也可提供顺序访问

Kafka 采用顺序稀疏索引文件,同一分区的 log 都是顺序写的,采用稀疏索引,一方面节省空间,只要找个开始的位置,顺序遍历即可,这也和场景有关,消息是按分区顺序写入,消费端是按分区顺序成批拉取,二分找到起始位置,顺序读取即可,读写磁盘都是分区内顺序读写

为什么mysql一定要用树索引?
决定因素在于树是支持删改的,线性索引删改成本很高。至于稀疏索引的顺序批量查询,B+树叶子节点之间也有连接,也可支持

为什么kafka用稀疏索引?
这是由于他存储的内容是日志,只负责追加,不需要做删改

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/951265.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号