跳转至

bitmap算法在测试系统中的应用

在我们测试平台中，有很多测试手机，对于某些手机，我们预计它只能跑特定的任务，或者某个手机会有一些特定的状态，如充电中，人工操作，手机清理中，当手机处于不同的状态会有一些不同的处理动作，此时我们会有哪些解决方案呢？

首先想到的应该是打标签，在数据库中新创建一个字段，比如叫tag，修改某个手机的状态，就修改一下这个tag字段。

但是这里有一个问题，如果某个手机拥有两个或者更多的标签，比如该手机正在充电，并且人工操作，那个我这个标签应该设置为多少？ 如果在mysql中可以将该字段设置为charging,oping, 但是我们进行搜索的时候就有些麻烦了，比如我要过滤出正在充电的手机，sql 语句大概是这样的

1
select * from db_phone where tag like '%charging%'

即使这样可以查询到所有正在充电的手机，但是之后如果想要再进行一些排序等操作就没法进行了。

更麻烦的是更新状态，如果手机不充电了，那么要将charging从tag中移除，然后再把别的状态重新写入。

还有一种解决方法是在数据库中添加字段，但是这样的操作，每添加一个tag就要修改数据库，多添加一个字段，以后如果标签越来越多，字段也会越来越多，对于之前的系统稳定性也有有一些影响。

此时我们可以考虑使用bitmap。

bitmap 简介

我们知道，数字是可以转换为二进制的，如3的二进制是11， 4是100，bitmap主要利用了二进制的运算，按位与、按位或操作

1
2
3
 0 0 1    0 0 1
&0 0 1   |0 0 1
=0 0 1   =0 0 1

我们可以将相应的位设定为对应的标识，如第一位表示是否是正在充电的手机，第二位表示为是否正在人工操作，1为是，0为否。

这样我们就可以通过这些二进制的数字表示手机的标签信息，如001 表示手机正在充电，010 表示手机正在进行人工操作，011 表示手机正在充电并且人工操作。

数据的查询

当我们想要查找所有手机中正在充电的手机，我们可以使用按位与运算，查找tag字段和001 进行与运算以后等于001的数据。

假如数据库中有以下几条数据

id devices tag
1 a,b 001
2 2,3,5 010
3 all 101
4 6,7 110

那么使用

1
select * from db_test where tag & 001 = 001

将会把tag中最后位为1的数据全部过滤出来即上表中的id为1和3的数据。

更新数据

当需要更新数据的时候，可以使用sql语句直接进行更新, 如

1
update db_test set tag=b'111' where id=1

但是更多的情况下，你是不知道三个字段的值，你只想更新其中某一位为0或者1，又分为两种情况

  1. 写1值， 可以利用任何值和0做或运算，不改变原来的值，和1做或运算，都将变为1的特性进行操作，如更新某个手机为充电状态，即更新末位为1,只需要和001进行或运算。
1
update db_test set tag=tag|001 where id=1
  1. 写0值，可以利用任何值与1做与运算，都不改变原值，和0做与运算都将变为0的特性，如我想解除某个手机的充电状态，即更新末位为0，只需要和110进行与运算即可
1
update db_test set tag=tag&110 where id=1

bitmap 的应用

之前有一个需求，测试系统中有很多个虚拟机，如win7, win8, win10, 不同的虚拟机内所安装的组件不同，有的安装office, 有的既安装了office也安装的360浏览器，此时，如果有一个任务，需要在有安装office的虚拟机中运行，那么作为任务的派发管理，应该优先将任务分到哪台虚拟机呢？

很显然，需要优先将任务分配到只安装了office的虚拟机中，因为如果将任务分配到既安装office又安装了360浏览器的虚拟机中，那么如果之后有一个需要在360浏览器环境的系统中运行，那么此时就会因为没有可用的系统来造成资源的浪费。

此时我们就可以使用bitmap来解决这个问题，先将安装了office的所有虚拟机过滤出来，再根据tag值，选择一个分值最小的进行分配

1
2
SELECT * from db_test WHERE tag&001=001
ORDER BY tag ASC

这样按照升序进行排列，派发的时候选择分值最小的进行任务分配。

bitmap的局限

使用bitmap的字段只有0和1，对就的状态就是 是 或者 否 ，如果你的状态有多种，比如说手机电量，如果状态有充满，良好，不足，极低等状态则不能使用bitmap，在mysql中bitmap最多只有64位。

并且使用bitmap要写好文档，否则项目维护人员根本不知道哪个位表示的是什么意思。