海量数据处理

1. 海量数据处理

1.1 什么是数据处理

数据的存储 + 计算

1.2 什么是海量数据处理

数据量太大，无法在短时间内迅速解决，或者是数据太大，导致无法一次性装入内存的数据处理

1.3 海量数据处理的常用方法

1. 巧用数据结构（bitmap、hash、布隆过滤器、堆）

2. 分治法：把规模大的数据转化为规模小的数据，逐个击破

3. 海量数据处理场景

4. 40亿个QQ号，如何判断一个QQ号是否存在?

5. 给定1000万个整数，内存限制1MB，如何对他们进行排序?

6. 给定1GB单词，内存限制1MB，如何找到出现频率最高的100个单词?

7. 内存限制4GB，如何对100亿URL查重?

8. 1000万字符串，其中有些是重复的，需要去重，保留没有重复的字符串。请怎么设计和实现?

9. 给定10亿个手机号，如何快速判断一个手机号是否存在?

10. 海量数据处理方法应用

本文详细介绍二叉树的基本概念、常见类型及实现方式。

hash

hashtable底层结构

概述

• 可以理解成目录，要翻看内容可以直接通过目录找到页数，翻过去看
• hashtable 扮演者类似目录这样一个快速索引角色

结构

代码定义

结构图

• 最外层是一个 dictht，字段如下
• *table：指向实际 hash 存储。存储看成一个数组
• size：哈希大小。实际就是 dictEntry 有多少元素空间
• sizemask：哈希表大小的掩码表示，总是等于 size-1.这个属性和哈希值一起决定一个键一个被放在 table 数组的哪个索引上面，规则是：Index = hash&sizemask
• used：表示已经使用的节点数量

list

是什么

redis list 是一组连接起来的字符串集合

list 最大元素个数是 2^32-1，新版是 2^64-1

适合场景

作为一个列表存储，属于比较底层的数据结构，可以使用的场景非常多。

存储一批任务数据，一批消息等

常用操作

写

set

是什么

是一个不重复、无序的字符串集合

如果是 intset 编码时，其实是有序的，整体看成无序的就行

适合场景

适合无序集合场景，如某个用户关注了哪些公众号

set 还提供了查交集，并集的功能

常用操作

写

string

string

string 是最基本的 k-v 结构，key 是唯一表示，value 是具体的值。

• value 可以是字符串或数字（整数、浮点数）
• value 最多可以容纳的数据长度是 512M
• 可以通过配置项修改proto-max-bulk-len

常用操作

常用操作聚集在 创建、查询、更新、删除

zset

是什么

• zset 就是有序集合，可以叫 sorted set。
• 是一组按关联积分有序的字符串集合，这个分数是给抽象概念，任何指标都可以抽象成分数
• 积分相同的情况下，按字典序排序

使用场景

游戏排行榜。

常用操作

写

压缩列表

压缩列表是什么

• 压缩列表：排列紧凑的列表
• 压缩列表在 redis 中有两种编码形式
• ziplist
• listpack：5.0 引入，直到 7.0 完全取代 ziplist，成为 ziplist 的进阶版本

解决什么问题

压缩列表是 list 的底层数据结构，压缩列表作为底层数据结构能提供紧凑型的数据存储方式，能节约内存（节省链表指针的开销），小数据量时遍历访问性能好（连续+缓存命中率高）

跳表

是什么

• 跳表是有序集合 zset 底层数据结构，也是 zset 的灵魂所在。
• 跳表本质还是链表

• 虽然链表结构简单清晰，但是查询某个节点的效率比较低，为了调高查找性能，引入了跳表。
• 跳表在链表基础上，给链表增加了多级索引，通过索引可以一次实现多个节点的跳跃，调高性能

跳表的结构