系统性能调优必知必会
陶辉
智链达CTO、前阿里云高级技术专家
立即订阅
3564 人已学习
课程目录
已更新 6 讲 / 共 34 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 万变不离其宗,性能优化也有章可循
免费
基础设施优化 (5讲)
01 | CPU缓存:怎样写代码能够让CPU执行得更快?
02 | 内存池:如何提升内存分配的效率?
03 | 索引:如何用哈希表管理亿级对象?
04 | 零拷贝:如何高效地传输文件?
05 | 协程:如何快速地实现高并发服务?
系统性能调优必知必会
15
15
1.0x
00:00/00:00
登录|注册

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

陶辉 2020-05-04
你好,我是陶辉。
上一讲我们谈到,Ptmalloc2 为子线程预分配了 64MB 内存池,虽然增大了内存消耗,但却加快了分配速度,这就是以空间换时间的思想。
在内存有限的单片机上运行嵌入式程序时,我们会压缩数据的空间占用,以时间换空间;但在面向海量用户的分布式服务中,使用更多的空间建立索引,换取更短的查询时间,则是我们管理大数据的常用手段。
比如现在需要管理数亿条数据,每条数据上有许多状态,有些请求在查询这些状态,有些请求则会根据业务规则有条件地更新状态,有些请求会新增数据,每条数据几十到几百字节。如果需要提供微秒级的访问速度,该怎么实现?(注意,以上非功能性约束并不苛刻,对于低 ARPU,即每用户平均收入低的应用,使用更少的资源实现同等功能非常重要。)
这种情况你会面对大量数据,显然,遍历全部数据去匹配查询关键字,会非常耗时。如果使用额外的空间为这些数据创建索引,就可以基于索引实现快速查找,这是常用的解决方案。比如,我们用标准库里提供的字典类容器存放对象,就是在数据前增加了索引,其本质就是以空间换时间。
当然,索引有很多,哈希表、红黑树、B 树都可以在内存中使用,如果我们需要数据规模上亿后还能提供微秒级的访问速度,那么作为最快的索引,哈希表是第一选择。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《系统性能调优必知必会》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(12)

  • 忆水寒
    从这篇文章,我能想到以下内容:
    1、哈希桶选择素数,这个其实是有科学研究的。不同的数据规模选中不同的哈希桶大小,能够保证数据更均匀。
    2、Reids中没有使用红黑树而是使用了跳表skiplist,因为shiplist支持区间查找。
    3、哈希算法在数据库的分库分表中也常用到,比如第一次计算哈希值找到对应的数据库。
    4、在MySQL数据库中使用B+树做索引,是因为可以减少树的高度,同时也可以使磁盘IO加载按照页方式(一页4K)加载。
       这样尽可能的多加载到连续数据到内存进行处理。
    5、位图bitmap其实在布隆过滤器中使用的比较多,主要是用于判断一个数据是否存在。核心思想就是内部有几个不同的哈希函数,
        映射到不同的bit位。如果同一个数据映射的这些bit位都有值,则可以认为该数据存在。
    6、哈希算法经过演化(优化)成一致性哈希算法,在分布式系统中节点故障时迁移数据影响范围比较小,其核心思想是两次哈希运算。
    关于思考题,我就举一个我熟悉的场景来分析吧。
    之前,我们的监控系统和其他厂商接口,对方抓包分析得出我们会有大量重复消息,导致对方处理压力很大,因此我们需要过滤重复信息。
    由于我们需要管理数十万个设备运行,所以我们将这些设备划分为两层管理。
    第一层,由于设备是接入最近的控制中心的,因此我们第一层按照控制中心进行管理。
    第二层,在同一个控制中心,也会有不同的设备,因此我们按照设备的类型进行第二层维护。
    第三层,才是我们真正的设备。所以我基于三层管理设备(可以看成三次哈希索引维护),查找更新的效率大大提高了。
    我只能想到这么多,希望也能看看其他大牛们的场景。
    2020-05-04
    7
    14
  • 小喵喵
    老师,请教下使用skiplist来构建索引,以下场景有什么缺陷吗?
    假设一个用户积分表有1亿数据,从数据库中读出来,然后构建skiplist,用户表中的数据有更改时(比如新增、修改、删除)时整条记录的时间戳会发生变化,然后定时去根据时间戳来更新skiplist中的数据。
    2020-05-04
    1
  • eason2017
    老师好,这个您举例说明的基数是256,但是,您图片里是用255取余呢?为啥?
    2020-05-08
  • 陛下
    看的好累,我唯一用过的索引,就是在数据库里,给表中经常要查询的字段建索引,索引类型好像是B树
    2020-05-07
  • Aaron
    在mysql中假如有一个user表,在该表的name字段建立一个索引,此时会创建一个b+tree,那么b+tree的非叶子结点存储的是什么?构造树结构肯定是有序的,此时name的索引树是怎么保证有序的?
    2020-05-07
  • 那时刻
    Python里的dict底层实现是采用了开放地址法。
    在把数据从哈希表中分离出来,提升哈希表的灵活性内容里,存放数据的数组D里采用链表把空闲空间链接起来,如果采用位图呢?是否可以减少存放链表所用指针的空间?
    2020-05-06
  • 𢘫
    es的倒排索引,可能更偏应用层一些哈!底层的原理都差不多
    2020-05-06
  • 鹤鸣
    开放寻址法还没接触过,不过有些细节值得推敲:
    1、当hash表已经存储的比较满的时候,需要依次使用不同的hash函数去计算键值的实际存储位置,这时可能会尝试很多个hash函数。
    2、假设有一组hash函数来依次用于哈希计算,那么会出现key1经hash1函数计算占据了pos1, key2经hash1函数计算也要占据pos1,此时hash函数变更,key2被放到了pos2,然后key3经hash1函数计算恰好又要占据pos2,pos2已经被占据了,那么key3又得经过hash2函数重新计算得到pos3。也就是说,key3的冲突是之前key2冲突的后遗症。
    2020-05-05
  • xindoo
    自荐下我之前写的关于Bloomfilter的博客,https://zxs.io/s/1d ,Bloomfilter作为bitmap的改进,牺牲了准确率换来了更强大的存储能力。
    2020-05-04
  • 苏菲的世界
    要知道,减少哈希桶的尺寸,就意味着同等内存下可以扩大哈希数组,从而降低装载因子。
    不减少尺寸为什么不可以扩大哈希数组呀,为什么扩大哈希数组会降低装载率?
    2020-05-04
  • 我来也
    文中说的msync(它可以按地址及长度来分段刷新),确实经典.

    不需要备份后的内容是某一时刻的准确逻辑备份.
    (先备份的是老时间点数据,后备份的可能是新时间点的数据)
    但通过oplog的方式修复哈希表,可以保证数据最终的一致性.
    2020-05-04
  • 凉人。
    B+树索引,业务场景为Mysql索引,主要好处,减少B树过长,磁盘I/O过多情况,一般为2层-3层,支持范围查询。
    2020-05-04
收起评论
12
返回
顶部