系统性能调优必知必会
陶辉
智链达 CTO,前阿里云 P8 高级技术专家
36367 人已学习
新⼈⾸单¥59
登录后,你可以任选4讲全文学习
课程目录
已完结/共 47 讲
系统性能调优必知必会
15
15
1.0x
00:00/00:00
登录|注册

03 | 索引:如何用哈希表管理亿级对象?

思考题
小结
降低哈希表的冲突概率
内存结构与序列化方案
为什么选择哈希表?
哈希表管理亿级对象

该思维导图由 AI 生成,仅供参考

你好,我是陶辉。
上一讲我们谈到,Ptmalloc2 为子线程预分配了 64MB 内存池,虽然增大了内存消耗,但却加快了分配速度,这就是以空间换时间的思想。
在内存有限的单片机上运行嵌入式程序时,我们会压缩数据的空间占用,以时间换空间;但在面向海量用户的分布式服务中,使用更多的空间建立索引,换取更短的查询时间,则是我们管理大数据的常用手段。
比如现在需要管理数亿条数据,每条数据上有许多状态,有些请求在查询这些状态,有些请求则会根据业务规则有条件地更新状态,有些请求会新增数据,每条数据几十到几百字节。如果需要提供微秒级的访问速度,该怎么实现?(注意,以上非功能性约束并不苛刻,对于低 ARPU,即每用户平均收入低的应用,使用更少的资源实现同等功能非常重要。)
这种情况你会面对大量数据,显然,遍历全部数据去匹配查询关键字,会非常耗时。如果使用额外的空间为这些数据创建索引,就可以基于索引实现快速查找,这是常用的解决方案。比如,我们用标准库里提供的字典类容器存放对象,就是在数据前增加了索引,其本质就是以空间换时间。
当然,索引有很多,哈希表、红黑树、B 树都可以在内存中使用,如果我们需要数据规模上亿后还能提供微秒级的访问速度,那么作为最快的索引,哈希表是第一选择。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

哈希表管理亿级对象的技术方法在面向海量用户的分布式服务中扮演着重要角色。本文深入介绍了哈希表的基本原理、应用以及在生产环境中管理大规模数据所面临的挑战和解决方法。首先,文章强调了哈希表在处理大规模数据时的高效性和实用性,同时针对哈希冲突问题提出了解决方案,包括链接法和开放寻址法,并分析了它们在序列化和灾备恢复方面的优劣势。此外,还探讨了如何降低哈希表的冲突概率,包括调优哈希函数和扩容策略。在讨论扩容时,文章提出了分阶段迁移的方法,以保证在扩容过程中持续提供正常服务。总的来说,本文通过简洁清晰的语言和实际案例,帮助读者快速了解了哈希表管理大规模数据的技术特点和挑战,为读者提供了有益的技术参考。文章还提到了哈希表的运行时间不随着业务规模增长而变化,以及哈希表不支持范围查询与遍历,需要考虑红黑树、B树等索引。此外,还强调了在亿级数据下需要注重内存的节约使用,以及优化哈希函数是降低哈希冲突的重要手段。整体而言,本文为读者提供了深入了解哈希表管理大规模数据的重要知识和技术思路。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《系统性能调优必知必会》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(19)

  • 最新
  • 精选
  • 杨春鹏
    老师,数据在内存中的连续性,对于该数据的序列化的效率上的性能是如何体现的呢

    作者回复: 这样可以把整块内存复制到磁盘上,或者发送到网卡上,而不用重新耗费CPU进行一次编码,先将分散的内存信息转换到一块连续的内存。杨春鹏,不知道我这样表达你理解了么?

    2020-05-12
    12
  • 杨文宇
    链表的内存地址不连续,是如何让影响序列化的?老师能具体说一下么

    作者回复: 你好杨文宇,当数组外的还有链表中的元素时,序列化就必须遍历所有元素,比如,至少要做1次循环,把每1个遍历到的元素的值,序列化写入至另一段内存中。而使用闭散列时,直接将这个数组占用的内存,直接作为序列化后的数据即可。

    2020-05-18
    5
  • 忆水寒
    从这篇文章,我能想到以下内容: 1、哈希桶选择素数,这个其实是有科学研究的。不同的数据规模选中不同的哈希桶大小,能够保证数据更均匀。 2、Reids中没有使用红黑树而是使用了跳表skiplist,因为shiplist支持区间查找。 3、哈希算法在数据库的分库分表中也常用到,比如第一次计算哈希值找到对应的数据库。 4、在MySQL数据库中使用B+树做索引,是因为可以减少树的高度,同时也可以使磁盘IO加载按照页方式(一页4K)加载。 这样尽可能的多加载到连续数据到内存进行处理。 5、位图bitmap其实在布隆过滤器中使用的比较多,主要是用于判断一个数据是否存在。核心思想就是内部有几个不同的哈希函数, 映射到不同的bit位。如果同一个数据映射的这些bit位都有值,则可以认为该数据存在。 6、哈希算法经过演化(优化)成一致性哈希算法,在分布式系统中节点故障时迁移数据影响范围比较小,其核心思想是两次哈希运算。 关于思考题,我就举一个我熟悉的场景来分析吧。 之前,我们的监控系统和其他厂商接口,对方抓包分析得出我们会有大量重复消息,导致对方处理压力很大,因此我们需要过滤重复信息。 由于我们需要管理数十万个设备运行,所以我们将这些设备划分为两层管理。 第一层,由于设备是接入最近的控制中心的,因此我们第一层按照控制中心进行管理。 第二层,在同一个控制中心,也会有不同的设备,因此我们按照设备的类型进行第二层维护。 第三层,才是我们真正的设备。所以我基于三层管理设备(可以看成三次哈希索引维护),查找更新的效率大大提高了。 我只能想到这么多,希望也能看看其他大牛们的场景。
    2020-05-04
    18
    73
  • 范闲
    1.Redis里的HASH用的是链表法,但是有渐进式Hash的方法进行动态扩容. 对于数据内部的持久化用的是RDB和AOF,所以没有序列化的需求 2.布隆过滤器是Hash的一个应用。真未必真,假一定假。因为有多个hash函数,对于不同的请求判断可能会出现Hash冲突,所以会有真未必真 3. 哈希还可以用在向量检索上.LSH局部敏感哈希是说有一组哈希函数使得两组相近的点具有相同的哈希值 4.分布式上的一致性哈希使得数据扩容更容易。
    2020-05-18
    8
  • 而立斋
    es的倒排索引,可能更偏应用层一些哈!底层的原理都差不多
    2020-05-06
    3
  • 小喵喵
    老师,请教下使用skiplist来构建索引,以下场景有什么缺陷吗? 假设一个用户积分表有1亿数据,从数据库中读出来,然后构建skiplist,用户表中的数据有更改时(比如新增、修改、删除)时整条记录的时间戳会发生变化,然后定时去根据时间戳来更新skiplist中的数据。
    2020-05-04
    2
  • 侠影
    1, java为什么用链接法,而不用开放地址法? 2, 哈希函数保留信息那里,电话号码是不应该%一个>10000的素数?QQ号这个想不明白… 3, 扩容时后台迁移,进行判断来选取新旧哈希表。还是比较模糊,新旧哈希表不会让内存压力增大吗?有没有code可以share下,辅助理解。
    2020-05-12
    2
    1
  • 云学
    很喜欢这种风格的分享,有场景,有优劣势分析,落地关键点,老师能否讲下NoSql里为什么喜欢使用LSM
    2020-05-09
    1
  • 我来也
    文中说的msync(它可以按地址及长度来分段刷新),确实经典. 不需要备份后的内容是某一时刻的准确逻辑备份. (先备份的是老时间点数据,后备份的可能是新时间点的数据) 但通过oplog的方式修复哈希表,可以保证数据最终的一致性.
    2020-05-04
    1
  • 凉人。
    B+树索引,业务场景为Mysql索引,主要好处,减少B树过长,磁盘I/O过多情况,一般为2层-3层,支持范围查询。
    2020-05-04
    1
收起评论
显示
设置
留言
19
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部