Bitmap数据类型是什么？能用来干什么？
Redis 的 Bitmap 数据类型是一种位图数据结构，可以表示大量的二进制位，并对这些位进行高效的位操作。Bitmap 在许多实际场景中都有广泛的应用，以下是几个常见的使用场景：
用户在线状态：
Bitmap 可以用于记录用户的在线状态，每个用户使用一个位来表示在线或离线。可以通过设置或清除相应的位来更新用户的在线状态，以及进行快速的查询和统计在线用户数量。
签到系统：
Bitmap 可以用于实现用户的签到系统。每个用户使用一个位表示每天是否签到，可以通过设置或清除相应的位来记录用户的签到情况，并对签到数据进行统计和分析。
布隆过滤器（Bloom Filter）：
Bloom Filter 是一种概率型数据结构，用于快速判断一个元素是否存在于集合中，而不需要实际存储元素本身。Bitmap 可以用作 Bloom Filter 的底层数据结构，用于表示集合的位图，通过设置相应的位来表示元素的存在。
去重与重复计数：
Bitmap 可以用于去重和重复计数的场景。每个元素使用一个位来表示是否已经出现过，可以通过设置或清除相应的位来进行去重操作，并使用位操作来计算重复元素的数量。
用户兴趣标签：
Bitmap 可以用于记录用户的兴趣标签，每个标签使用一个位表示用户是否拥有该标签。可以通过设置或清除相应的位来更新用户的兴趣标签，以及进行快速的标签匹配和查询。
总的来说，Redis 的 Bitmap 数据类型可以应用于许多需要高效处理位操作的场景，如状态记录、标记和计数等。由于 Bitmap 的存储和操作效率非常高，可以在很小的内存空间下存储大量的二进制位，因此在需要处理大规模位操作的场景下，Bitmap 是一个非常有用的数据类型。
从本质上来讲，bitmap提供了一个指定的内存快，其中每一个bit都有0和1两种状态，用来表示对应位置不同的状态，这种数据结构使得在仅需要标识两种状态的数据的时候非常节约内存。
但Bitmap也存在非常明显的缺陷：
当样本分布极度不均匀的时候，BitMap会造成很大空间上的浪费。
若数据的类型Int64，并且数据分布的跨度比较大，则也无法满足对内存的要求。
当元素不是整型的时候，BitMap就不适用了。
BitMap只能保存整形数据，对于字符串类型的数据则不合适使用。
接下来我们假定一个前提，我们的数据ID都是整数，且不是非常离散，我们就可以很好的利用bitmap的特性进行一些实际操作。
常用命令
SETBIT：设置比特位值
GETBIT：查询比特位值
BITCOUNT：统计比特值为1的数量
BITPOS：查询第一个比特值为0或1的偏移量
BITOP：对Bitmap做逻辑与、或、异或、非操作
BITFIELD：将Bitmap看作由多个整数组成的，对其中的整数操作
状态标记
实际场景：假设我们现在有5000台物联网设备，要实时同步他们的在线状态。
传统的解决方案可以在数据库中加个字段，但状态的更新会导致数据库的频繁写入，不是很优雅。
这个时候就可以使用bitmap数据类型来进行存储，仅需不到1kb的内存(626 Byte)，就能存储所有设备的在线状态，并且能很方便的计算当前实时在线的设备数量。
代码实例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 | // DeviceOnlineStatus 设备在线状态结构体定义 type DeviceOnlineStatus struct { DeviceGroupName string } // getOnlineStatusKey 组装在线状态key func (dos *DeviceOnlineStatus) getOnlineStatusKey() string { return dos.DeviceGroupName + "OnlineStatusKey" } // Init 初始化设备数，预先分配内存，提高效率 func (dos *DeviceOnlineStatus) Init(totalDeviceCount int64) error { cacheKey := dos.getOnlineStatusKey() exists, err := redisClient.Exists(context.Background(), cacheKey).Result() if err != nil { return err } else if exists != 0 { _, err := redisClient.Del(context.Background(), cacheKey).Result() if err != nil { return err } } // 这里默认0表示默认不在线 _, err = redisClient.SetBit(context.Background(), cacheKey, totalDeviceCount, 0).Result() return err } // SetOnlineStatus 根据设备ID更新在线状态 func (dos *DeviceOnlineStatus) SetOnlineStatus(isOnline bool, deviceID int64) error { cacheKey := dos.getOnlineStatusKey() bitValue := 0 if isOnline { bitValue = 1 } _, err := redisClient.SetBit(context.Background(), cacheKey, deviceID-1, bitValue).Result() return err } // GetOnlineDeviceCount 获取当前在线设备数量 func (dos *DeviceOnlineStatus) GetOnlineDeviceCount() (int64, error) { cacheKey := dos.getOnlineStatusKey() return redisClient.BitCount(context.Background(), cacheKey, nil).Result() } // DeviceIsOnline 判断某个设备是否在线 func (dos *DeviceOnlineStatus) DeviceIsOnline(deviceID int64) (bool, error) { cacheKey := dos.getOnlineStatusKey() result, err := redisClient.GetBit(context.Background(), cacheKey, deviceID-1).Result() if err != nil { return false, err } return result == 1, nil } // TestDeviceOnlineStatistics 测试代码 func TestDeviceOnlineStatistics() { status := DeviceOnlineStatus{ DeviceGroupName: "TrafficViolationCamera", } // 初始化，5000台设备，预先分配内存 err := status.Init(5000) if err != nil { log.Fatalln(err.Error()) } // 本地map，验证数据是否正确 localStatistics := map[int64]bool{} for i := 1; i < 10_001; i++ { // 执行一万次状态更新 deviceID := rand.Int63n(4999) + 1 // 随机一个设备ID置为在线状态 online := (deviceID%2 == 0) // 仅双数在线，单数忽略 err = status.SetOnlineStatus(online, deviceID) if err != nil { log.Fatalln(err.Error()) } if online { localStatistics[deviceID] = true } else { delete(localStatistics, deviceID) } } // 获取总的在线设备数 count, err := status.GetOnlineDeviceCount() if err != nil { log.Fatalln(err.Error()) } fmt.Println( "online device count from redis:", count, ", online device count from map:", len(localStatistics), ) // 判断2662号设备是否在线 fmt.Println(status.DeviceIsOnline(2662)) } |
运行结果：
此处由于使用随机数，每次的运行结果不一样，但仅需对比本地统计和Redis bitmap统计数据量是否一致即可。
1 | online device count from redis: 2161 , online device count from map: 2161 |
从结果可知，随机出来的样本在线设备数基本在2500上下浮动，此时map的内存占用大概20kb左右，并且会随着数量增加而增加，但Redis bitmap的内存占用使用为626 Byte。
而且Redis 可以支持分布式服务器多端同时操作同一个状态，从内存和分布式友好来讲，这个场景下Redis bitmap完胜。
数据去重
实际场景：假设我们网站总共有一亿用户，网站每天访问次数假设也是一亿，现在需要统计每天访问的独立用户数，而且需要零误差（如果允许一定误差可以使用HyperLogLog）。
前提条件，用户标识为整数。
此时如果我们使用传统数据库或者KV数据库来进行统计的话，内存和计算的开销都会非常大。
这里如果我们使用bitmap进行存储计算，可以降低实现难度和内存开销。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | func TestBitmapUVStatistics() { uvStatisticsKey := "RedisUVStatisticsKey" // 统计数据key // 删除原有数据，清空原有统计，可以在每天0点定时执行，保证数据精确 _, err := redisClient.Del(context.Background(), uvStatisticsKey).Result() if err != nil { log.Fatalln(err.Error()) } // 初始化一个长度一亿bit的bitmap数据，并全部用0填充 _, err = redisClient.SetBit(context.Background(), uvStatisticsKey, 100_000_000, 1).Result() if err != nil { log.Fatalln(err.Error()) } for i := 0; i < 100_000_000; i++ { // 模拟一亿次随机的用户请求 userID := rand.Int63n(100_000_000) // ID随机，肯定会出现重复 // 对应ID的位设置为1 _, err = redisClient.SetBit(context.Background(), uvStatisticsKey, userID, 1).Result() if err != nil { log.Fatalln(err.Error()) } } // 计算值为1的位总数 uv, err := redisClient.BitCount(context.Background(), uvStatisticsKey, nil).Result() if err != nil { log.Fatalln(err.Error()) } fmt.Println("uv statistics result:", uv) } 运行结果：uv statistics result: 63207823 |
这里的原理是利用用户ID作为偏移量，如果用户访问过了，那么用户ID对应的位置bit设置为1，其他没有访问过的位置则是0，最后只需要计算为1的位有多少即可。
注意：这里一亿多次的Redis请求大概需要耗时20分钟左右，请耐心等待。
布隆过滤器
什么是布隆过滤器？
判断目标值是否在一个集合中是比较常见的业务场景。
通常在数据量比较小的时候我们可以直接使用哈希表来实现，但随着数据量的增大，对应的资源消耗也会急剧提升。
为了应对大量的资源消耗，引入布隆过滤器这个概念，其核心思想是在布隆过滤器中如果某个数据存在时，这个数据有可能不存在; 但当布隆过滤器说，某个数据不存在时，那么这个数据一定不存在。
布隆过滤器实现原理
使用bitmap替代原有的哈希表数据结构，以节省内存；使用多个哈希函数计算出key的不用hash值存入bitmap中，若其中任何一个hash值对应的位不为1，则这个数据不存在。
BitMap虽然能够在一定情况下减少的内存的消耗，但是BitMap也存在以下局限性：
当样本分布极度不均匀的时候，BitMap会造成很大空间上的浪费。若数据的类型Int64，并且数据分布的跨度比较大，则也无法满足对内存的要求。
当元素不是整型的时候，BitMap就不适用了。BitMap只能保存整形数据，对于字符串类型的数据则不合适使用。
BitMap只能处理整形数据，对于字符串或其他key类型则不能适用。所以需要把key映射为整形，以适应bitmap数据类型。
布隆过滤器误识别的原因在于hash冲突，因此减少hash冲突可以降低布隆过滤器误识别率。
hash冲突和BitMap数组的大小以及hash函数的个数以及每个hash函数本身的好坏有关。可以采用以下方法降低hash冲突的概率：
多个hash，增大随机性，减少hash碰撞的概率。
扩大数组范围，使hash值均匀分布，进一步减少hash碰撞的概率。
golang+redis实现布隆过滤器
过滤器主体：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 | import ( "context" "fmt" "log" "strconv" "github.com/beego/beego/v2/server/web" "github.com/redis/go-redis/v9" uuid "github.com/satori/go.uuid" ) // BloomFilter 布隆过滤器 type BloomFilter struct { // 为什么这里使用uint32，而不是其他类型，因为Redis单个key限制内存大小为512MB，整好是2^32，实际可操作offset为2^32-1 Size uint32 // 过滤器名称，根据业务不同设置唯一名字 FilterName string // Redis客户端 redisClient *redis.Client } // NewBloomFilter 初始化布隆过滤器 // size 过滤器大小，单位bit // filterName 过滤器名称 func NewBloomFilter(size uint32, filterName string) *BloomFilter { if size == 0 { size = 1024 * 1024 // 默认一亿 } dbHost, _ := web.AppConfig.String("aliyun.redis.endpoint") dbPort, _ := web.AppConfig.String("aliyun.redis.port") dbPassword, _ := web.AppConfig.String("aliyun.redis.password") dbnum, _ := web.AppConfig.Int("aliyun.redis.dbnum") redisClient := redis.NewClient(&redis.Options{ Addr: dbHost + ":" + dbPort, Password: dbPassword, DB: dbnum, }) bf := &BloomFilter{ Size: size, FilterName: filterName, redisClient: redisClient, } _, err := redisClient.SetBit(context.Background(), filterName, int64(size), 0).Result() if err != nil { log.Fatalln(err.Error()) } return bf } // magic code 三个都是质数 var seeds = []uint64{311, 3011, 30011} // Set 设置key存在 func (bf *BloomFilter) Set(key string) error { for _, seed := range seeds { hash := bf.Hash(key, seed) _, err := bf.redisClient.SetBit(context.Background(), bf.FilterName, int64(hash), 1).Result() if err != nil { return err } } return nil } // Exists 查询key是否存在 func (bf *BloomFilter) Exists(key string) (bool, error) { for _, seed := range seeds { hash := bf.Hash(key, seed) result, err := bf.redisClient.GetBit(context.Background(), bf.FilterName, int64(hash)).Result() if err != nil { return false, err } else if result != 1 { return false, nil } } return true, nil } |
hash函数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | // Hash 布隆过滤器使用的hash函数，此处如果key是整数且小于size，直接转换成uint64 // 本函数来源于Redis官方插件RedisBloom项目，bloom.c，改写为go语言 // https://github.com/RedisBloom/RedisBloom // key 需要hash的key // seed 种子, 一般使用质数 func (bf *BloomFilter) Hash(key string, seed uint64) uint64 { // 如果key是整数且小于size，直接转换成uint64 keyIntValue, err := strconv.ParseInt(key, 10, 64) if err == nil { if keyIntValue < int64(bf.Size) { return uint64(keyIntValue) } } const m uint64 = 0xc6a4a7935bd1e995 const r uint64 = 47 data := []byte(key) var len int = len(data) h := seed ^ (uint64(len) * m) end := len / 8 for i := 0; i < end; i++ { k := uint64(data[0]) | uint64(data[1])<<8 | uint64(data[2])<<16 | uint64(data[3])<<24 | uint64(data[4])<<32 | uint64(data[5])<<40 | uint64(data[6])<<48 | uint64(data[7])<<56 data = data[8:] k *= m k ^= k >> r k *= m h ^= k h *= m } switch len & 7 { case 7: h ^= uint64(data[6]) << 48 fallthrough case 6: h ^= uint64(data[5]) << 40 fallthrough case 5: h ^= uint64(data[4]) << 32 fallthrough case 4: h ^= uint64(data[3]) << 24 fallthrough case 3: h ^= uint64(data[2]) << 16 fallthrough case 2: h ^= uint64(data[1]) << 8 fallthrough case 1: h ^= uint64(data[0]) h *= m } h ^= h >> r h *= m h ^= h >> r return h % uint64(bf.Size) } |
测试代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | func TestBloomFilter() { // 测试订单ID这种连续的数字 orderFilter := NewBloomFilter(5000000, "OrderIDBloomFilter") for i := 0; i < 10000; i++ { tempKey := strconv.FormatInt(int64(i*500), 10) if err := orderFilter.Set(tempKey); err != nil { log.Fatalln(err) } } existsCount := 0 for i := 0; i < 10000; i++ { tempKey := strconv.FormatInt(int64(i*500), 10) if exists, err := orderFilter.Exists(tempKey); err != nil { log.Fatalln(err) } else if exists { existsCount += 1 } } fmt.Println("连续ID过滤器中找到的数量：", existsCount) // uuid这种不连续的值 uuidFilter := NewBloomFilter(500000, "UUIDBloomFilter") keysArray := make([]string, 500000) for i := 0; i < 500000; i++ { tempKey := uuid.NewV4().String() keysArray[i] = tempKey if err := uuidFilter.Set(tempKey); err != nil { log.Fatalln(err) } } existsCount = 0 for _, key := range keysArray { if exists, err := uuidFilter.Exists(key); err != nil { log.Fatalln(err) } else if exists { existsCount += 1 } } fmt.Println("非连续ID过滤器中找到的数量：", existsCount) count, err := uuidFilter.redisClient.BitCount(context.Background(), uuidFilter.FilterName, nil).Result() if err != nil { log.Fatalln(err) } fmt.Println("过滤器中1的数量：", count) } |
运行结果：
连续ID过滤器中找到的数量： 10000
非连续ID过滤器中找到的数量： 500000
过滤器中1的数量： 499171
从结果可知，如果是已知范围的连续ID，那么布隆过滤器的准确度可以达到100%，且内存占用非常经济，仅有bitmap的大小。
如果是不连续的数据，数据不存在的准确定由于hash函数的碰撞问题，使用三次hash后最终的准确度依然有95%左右，但是从内存占用和准确度考虑，已经能够满足日常需求。
总结
bitmap 可以理解为一块持续的内存，可以操作和查看每一个位（bit）
优点：
空间效率高：Redis Bitmap 使用紧凑的位表示数据，适用于大规模数据集中的高效存储，可以节省内存空间。
快速操作：Redis 提供了丰富的位图操作命令，如设置位、清除位、计数位等，这些操作都能在常数时间内完成，具有高效性能。
支持位运算：Redis Bitmap 支持位运算操作，如与、或、异或等，使得可以对多个位图进行复杂的逻辑操作。
缺点：
存储空间受限：Redis Bitmap 存储的数据是位级别的，因此适合存储的数据类型有一定限制，只能表示二进制的状态或标记，不适合存储复杂结构的数据。
内存占用随数据增长：虽然 Redis Bitmap 可以节省内存空间，但是当位图中的位数增加时，所需的内存空间也会随之增加，可能会对内存造成一定的压力。
总结来说，Redis Bitmap 是一种高效的数据结构，适用于位级别的数据存储和位操作。它具有空间效率高、快速操作和支持位运算等优点，但存储空间受限、内存占用随数据增长等缺点需要注意。
程序猿老龚（龚杰洪）原创，版权所有，转载请注明出处.