大数据存储处理-bitmap的艺术

举报
仙士可 发表于 2023/06/21 16:53:22 2023/06/21
【摘要】 引言有这样的一个面试题:给20亿个不重复的unsigned int的整数的文件,每一行一个数字，没排过序的，然后再给一个数，如何快速判断这个数是否在那20亿个数当中？在php中,其实是有sort 和in_array函数可以实现的,例如:<?php$arr = [ 5,8,1,3,54,745,123];var_dump($arr);sort($arr);var_dump($arr);var...

引言

有这样的一个面试题:

给20亿个不重复的unsigned int的整数的文件,每一行一个数字，没排过序的，然后再给一个数，如何快速判断这个数是否在那20亿个数当中？

在php中,其实是有sort 和in_array函数可以实现的,例如:

<?php
$arr = [
  5,8,1,3,54,745,123
];
var_dump($arr);
sort($arr);
var_dump($arr);
var_dump(in_array(31,$arr));
var_dump(in_array(54,$arr));
复制

这样就可以直接实现排序和判断了

但是事实上真的如此吗?我们要考虑下,20亿个数有多大.

在64位环境下,php的int占用为8个字节

20亿个数字,需要占用8*20亿*8/1024/1024/1024约等于15G的内存

很明显,大多数人的电脑,或者服务器都没有这么大的内存,那么我们该怎么才能实现这个需求呢?

用户签到问题

或许有人会觉得这个问题不切实际,"谁特么没事闲着蛋疼算这个?"

那好,这个问题先放一边,我们换个问题

假设网站有1亿用户,现在需要增加个签到功能,用于奖励那些活跃用户 现在需要你实现以下功能:

1:记录某个用户每年的签到情况 2:统计某一个月份没有断签的用户

3:查看某个用户的连续签到情况

这个问题看起来很简单啊,新增一个记录表,每天签到则新增一条记录,用户加个索引

直接where查询用户就行了

统计没有断签也简单啊,where 月份区间 count一下就行了

至于连续签到情况,增加个字段表示连续签到就行了

这个方案确实是可以解决,那么同样的,

1亿用户,假设每天有3000万人签到,那么一个月,一年下来,数据将会是:30000000*365差不多是100亿的数据...

bitmap

那么根据上面2个需求场景,当在数据量大的情况下时,处理将会非常复杂,那该怎么做呢?那就是使用bitmap

什么是bitmap?简单来说就是位图.

二进制

首先我们从二进制讲起,众所周知,计算机最后的操作都是二进制操作,数据存储原始都是二进制存储的.

但是具体该怎么理解这个呢? 由于在一般情况,计算机识别不同的状态只能通过"断电","通电" 2种状态,

举个例子,有座岛屿,岛上的人需要别人送饭给他们吃,但是如果每天吃一种菜,会腻,然后没有电话什么的,该怎么告诉岛外的人,他们想吃什么呢?

然后,他们想到了一种方法,在岛上建了2座灯塔,如果亮一座灯塔就代表要吃猪肉,如果亮两座灯塔就代表要吃牛肉

这样,他们就可以区分2种菜了,再后来,猪肉牛肉吃腻了,想吃羊肉,鸡肉怎么办呢?

他们又想到了一种办法,由于2座灯塔是不一样的位置,所以他们约定了,

第一座灯塔亮,第二座不亮,表示猪肉, 01 第一座灯塔不亮,第二座亮,代表牛肉, 10

第一座灯塔亮,第二座亮,代表羊肉,  11

第一座灯塔不亮,第二座灯塔不亮,代表鸡肉 00

这样,他们用2座灯塔,可以表示4种不同的信息,这就是最原始的二进制了

通过二进制,我们可以用多个 简单的 "开","关"去代表非常大的信息

例如1T的硬盘,都是通过以上这种方法存储的值

二进制数字

通过上面的二进制介绍,我们了解了二进制的存储原理,那么,二进制数据是怎么表示的呢?

同样,因为只有"开","关" 两种状态,我们分别用1,0表示

那么

数字0 00

数字1 01

数字2 10

数字3 11

数字4 100

数字5 101

数字6 110

数字7 111

在64位环境上,int的表示使用了64位的开关,即每个数字(比如0,11,52),都需要占用64位8字节的存储空间,最大存储值为9223372036854775807二进制表示为64个1(1111111111111111...)

那么,我们知道了php的数字存储方式,能否想办法节省存储呢?当然是可以的

在上面我们发现,由于一个数字表示需要64个开关(64位),我们完全可以这样做:

由于数字以0开始,所以0位应该存储在第一个开关 

数字1,我们在第2个开关记为1  010

数字3,我们在第3个开关记为1  100

数字63,我们在第64个开关记为1 1000000....

假设0-63只有这3个数字,那么我们存储为10000000000000000000000000000000000000000000000000000000000000110 的二进制数据

这样,我们只需要一个64位(8字节)的数字,就能表示0-63 存在的数了....

比原来的1个数字就得占用8字节,最多可节省63倍的空间!!!!

这种存储方式,就叫做bitmap

php的二进制

那上面提到的,在第n个开关记为1的操作,在php怎么实现呢?我们需要了解一下php的位运算

如下代码

<?php
/**
 * Created by PhpStorm.
 * User: Tioncico
 * Date: 2019/1/15 0015
 * Time: 15:21
 */
$a = 0B0001;
$b = 0B0010;
$c = 0B1010;
$d = 0B0011;
//与运算 &,将2边都为1的数置为1,其他为0
//例如0001&1010=0000,0001&0011=0001
echo decbin($a&$c).PHP_EOL;
echo decbin($a&$d).PHP_EOL;

//或运算 |,将2边有一个为1的数置为1,都为0的则为0
//例如0001|1010=1011
echo decbin($a|$c).PHP_EOL;

//异或运算 ^,将2边一个为0,一个为1的置为1,其他为0
//例如0001^1010=1011
echo decbin($a^$c).PHP_EOL;

// 左移运算 << ,将数字中的位往左移n位
// 例如0010<<2=1000,0010<<1=0100
echo decbin($b<<1).PHP_EOL;

// 右移运算 >> ,将数字中的位往右移n位
// 例如1010>>1=0101 1010>>2=0010
echo decbin($c>>1).PHP_EOL;
echo decbin($c>>2).PHP_EOL;
复制

那如何存储0-63的数字呢?

<?php
/**
 * Created by PhpStorm.
 * User: Tioncico
 * Date: 2019/1/15 0015
 * Time: 15:21
 */
$a = 0B0;

//存储数字3
$num=3;
$num = 1<<($num);//将1往左移3位,1=>1000
$a=$a|$num;//1000

//存储数字5
$num=5;
$num = 1<<($num);//将1往左移5位,1=>100000
$a=$a|$num;//101000

//存储数字14
$num=14;
$num = 1<<($num);//将1往左移14位
$a=$a|$num;//100000000101000

echo decbin($a);
复制

通过这方法,我们即可使用一个数字,记录64个数字的存在

解决题1

php代码(由于20亿数字太大,本人生成200万个数字去进行2种方法内存的比对)

<?php
/**
 * Created by PhpStorm.
 * User: Apple
 * Date: 2019/1/7 0007
 * Time: 16:59
 */
//将一个200万的数组随机打乱写入到文件
$arr = range(1,2000000);
shuffle($arr) ;

foreach ($arr as $value){
    file_put_contents('num.txt',$value.PHP_EOL,FILE_APPEND);
}
复制

生成文件之后,单文件大小为14540kb

使用常规方法操作数组,需要占用64 M作用的内存(数组需要占用大量内存)

<?php
/**
 * Created by PhpStorm.
 * User: Apple
 * Date: 2019/1/7 0007
 * Time: 16:59
 */

ini_set('memory_limit', '1024M');
$arr = [];
$filePath = './num.txt';//文件
$fp=fopen($filePath,"r");
while(!feof($fp)){//循环读取文件数据
    $data=fgets($fp);
    $arr[]=(int)$data;//转换成int类型,默认char占用更多
    unset($data);
}
fclose($fp);
sort($arr);
//var_dump($arr);
echo "内存使用峰值:",(((memory_get_peak_usage())/1024/1024).'MB'),PHP_EOL;//内存使用:64.376541137695MB
echo "200w int大约占用:",2000000*8/1024/1024,'MB';
复制

使用bitmap方式存储,只需要占用1.37MB!

<?php
/**
 * Created by PhpStorm.
 * User: Apple
 * Date: 2019/1/7 0007
 * Time: 16:59
 */
$arr = [];
$filePath = './num.txt';//文件
$fp=fopen($filePath,"r");
//取得文件大小
$fileSize=filesize($filePath);
while(!feof($fp)){//循环读取文件数据
    $data= fgets($fp);
    //每64个数字存储为一组
    $key = intval($data/64);
    if (isset($arr[$key])){
        $arr[$key] = $arr[$key]| (1<<($data%64));
    }else{
        $arr[$key] = 1<<($data%64);
    }
}
sort($arr);
fclose($fp);
echo "内存使用:",(((memory_get_usage())/1024/1024).'MB');//内存使用:1.3764343261719MB
复制

可能有人问,那排序呢?你没有排序啊?

由代码和上面的说明可发现,在分别存储数据之后,数组已经算是排好序了

例如$arr[0],代表着0-63的数字范围

$arr[1],代表着64-127的数字范围

不需要进行再次排序了.

bitmap数据处理

我们已经获得了一个排序好的数组,

那么我们给出一个数字,如何判断该数字是否存在呢?

其实上面我们有讲到位运算

举个例子

当有个一组(1-64个数字)组成的int时,它的二进制应该为:

111111111111111111111...1111111

当这数字不存在时,二进制应该有一位为0,例如数字64-127,假设缺少65这个数字,它的二进制表达式为

111111111111111111111111111111111111111111111111111111111111101  (第二位为0)

那怎么判断呢?

与运算方法

$num = 77799999997;
var_dump(checkBitNum($arr, $num));
function checkBitNum($array, $num)
{
//判断是否有这个键名
    $key = intval($num / 64);
//    if (isset($array[$key])) {为了测试位运算,先把直接判断注释
    $bitToNum = 1 << ($num % 64);//算出这个数字的二进制位数
    echo "二进制位数为:" . decbin($bitToNum), PHP_EOL;
    //使用与运算
    //如果两边都为1,则置为1,其他则为0
    //$array[$key]有这个数字,则$num%64+1的二进制位数为1,与运算$bitToNum,则会等于$bitToNum,如果不为1,则等于0
    $tempNum = $array[$key] & $bitToNum;
    echo "计算结果为:" . decbin($tempNum), PHP_EOL;
    if ($tempNum != $bitToNum) {
        return false;
    }
    return true;
//    } else {
//        return false;
//    }
}
复制

另一种方法,或运算方法:

function checkBitNum($array, $num)
{
//判断是否有这个键名
    $key = intval($num / 64);
//    if (isset($array[$key])) {为了测试位运算,先把直接判断注释
    $bitToNum = 1 << ($num % 64);//算出这个数字的二进制位数
    echo "二进制位数为:" . decbin($bitToNum), PHP_EOL;
    //使用或运算
    //如果两边有一个为1,则置为1,否则为0
    //$array[$key]有这个数字,则$num%64+1的二进制位数为1,或运算$bitToNum($bitToNum该位为1,其他为0),结果将会等于$array[$key]
    //如果$array[$key]没有这个数字,则或运算之后,$array[$key]该位会置为1,结果将不会等于$array[$key]
    $tempNum = $array[$key] | $bitToNum;
    echo "arr[key]为:" . decbin($array[$key]), PHP_EOL;
    echo "计算结果为:" . decbin($tempNum), PHP_EOL;
    if ($tempNum != $array[$key]) {
        return false;
    }
    return true;
//    } else {
//        return false;
//    }
}
复制

这样,我们就已经使用bitmap,存储空间小,速度快,解决了大量简单数据下的排序,判断

解决用户签到问题

在前面,我们已经通过了bitmap,解决了大数据存储排序问题,那么问题二的签到问题怎么办呢?

很简单,我们继续使用bitmap即可,

通过bitmap的特性,我们可以如下实现:

<?php
/**
 * Created by PhpStorm.
 * User: Apple
 * Date: 2019/1/7 0007
 * Time: 16:59
 */

$data = [];
$data = saveSign($data, '01-01');
$data = saveSign($data, '01-02');
$data = saveSign($data, '01-03');
$data = saveSign($data, '01-05');
$data = saveSign($data, '01-30');
$data = saveSign($data, '01-29');
$data = saveSign($data, '01-31');

foreach ($data as$key=> $value){
    echo "{$key}月份签到情况:".decbin($value);//输出11100000000000000000000000101110
    //从右往左看,每一位代表一天,1代表已签到
}
function saveSign($data, $date)
{
    //以月份为最小单位存储
    $dateArr = explode('-',$date);
    $key = $dateArr[0];
    if (isset($data[$key])){
        $data[$key] = $data[$key]| (1<<((int)$dateArr[1]%64));
    }else{
        $data[$key] = 1<<((int)$dateArr[1]%64);
    }
    return $data;
}
复制

计算方法和上面一样,只需要通过与或预算就能清楚签到情况

对比如下:

数据库直接存储:1亿用户,假设每天有3000万人签到,那么一个月,一年下来,数据将会是:30000000*365差不多是100亿的数据...

数据库存储bitmap:1亿用户,假设每天有3000万人签到,如果按月份储存bitmap,一年下来,数据将会是:30000000*12只有3亿

bitmap缺点

前面说这么多,那bitmap有缺点吗?当然有

1:bitmap不能存储多状态情况,bitmap只有0和1 两个状态,无法做多状态的存储

2:bitmap不能存储重复数据,bitmap是通过不同的位数,代表不同的数据和不同的状态,不能通过bitmap存储重复的数据

3:bitmap不能做非运算,什么叫非运算呢?和缺点1类似,由于bitmap只有0和1两种状态,当你要查询0状态时,由于int 的位数问题,你可能会查出不在限定位数的0,例如上面的签到数据,当你要取出所有未签到天数时,可能会取出当月32-63号的数据,当然你可自己判断

4:bitmap受int位数限制,在32位机器上,int只有32位4个字节,所以你一个int数据只能最多存储32条数据

其他

关于第二个签到问题补充

在很多情况下,我们可能需要的是记录某一天有多少个会员的签到情况,而不是某个会员的签到情况,那这个能用bitmap吗?

当然可以,我们需要采用会员id横向存储,例如:

<?php
/**
 * Created by PhpStorm.
 * User: Apple
 * Date: 2019/1/7 0007
 * Time: 16:59
 */

$data = [];

$data = saveSign($data, 1);
$data = saveSign($data, 2);
$data = saveSign($data, 63);
$data = saveSign($data, 4);
$data = saveSign($data, 117);
$data = saveSign($data, 98);
$data = saveSign($data, 654);
$data = saveSign($data, 235);
foreach ($data as$key=> $value){
    echo "今天第{$key}批会员签到情况:".decbin($value).PHP_EOL;//输出11100000000000000000000000101110
    //从右往左看,每一位代表一天,1代表已签到
}
function saveSign($data, $userId)
{
    $key = intval($userId / 64);
    if (isset($data[$key])) {
        $data[$key] = $data[$key] | (1 << ($userId % 64));
    } else {
        $data[$key] = 1 << ($userId % 64);
    }
    return $data;
}
复制

我们以天为单位,把签到的会员id存入数据中,数据库只需要查询某一天的bitmap数据,就能得到某一天的所有会员签到情况

【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
大数据
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入