基于BitMap思想的标签框架

背景

    自乐高搭建系统在活动落地页的搭建中推广之后，搭建系统的落地页和模块数量就迅速增长。但却并没有一个入口可以帮助研发迅速的统计线上页面和页面中各模块的使用情况，无法对一些可能存在性能风险的页面进行跟踪（部分模块的特性导致该模块无法静态化，可能存在性能风险）。因此需要一个 线上页面和模块的统计解决方案用于解决此类数据统计问题。

问题

    由于乐高搭建系统是一个新生的系统，目前仍有大量的需求在不断追加，页面和模块数量也在不断增长。因此 方案要求允许的统计维度和统计的方案高度灵活， 具备良好的扩展性能以应对不断增加的统计需求。

    经以往对于统计需求的设计经验，发现 对被统计对象进行打标签，可以 较好的满足上述的需求。只要对每个页面/模块打上对应的标签，例如存在风险标签，就可以将页面统计需求转换为标签的打标和查询，提高系统性能并降低复杂度。但由此又引申出一个新的问题，如何存储页面/模块的标签信息，使用一个数据库字段一个标签的形式，系统将变得很难扩展；而将标签存储为字符串的形式，又不利于数据查询。

解决方案

    经过进一步调研，发现基于位运算的BitMap算法能够很方便的解决上述问题，能 在灵活打标及方便查询的前提下满足高扩展性。因此，乐高搭建系统最后使用了基于BitMap思想的打标框架来解决上述统计问题，并取得了良好的效果。下面简单介绍一下BitMap算法和标签框架。

    从本质上讲，BitMap是一种用二进制位数代表数值，并用该位的二进制值代表该数值存在与否的算法。

    可以假设有一个取值为0-7的集合｛4，5，2，1，7｝，在java中可能使用一个Integer数组表示。但是在bitmap中，它可以简单的用一个字节来表示：10110110。这两者的对应关系可以见下图：

       

    Bit位从低到高依次表示0-7的数值，而该位为0则表示该数值在集合中不存在，为1则表示集合中存在该数值。这样，一个数字集合就被转换成一个字节，节省了大量的存储空间。而再次仔细观察该转换后的bit数值，可以发现BitMap的另一个优点，它的表示形式自带排序，这在某些情况下真是性能福音！

    注意到例子中使用的数字范围是0-7，那么如何表示更大范围的数据呢？也简单，将八位bit作为一个元素，拼成一个数组，就可以愉快的表示任意范围的数字了~

    以java为例，如果使用long类型作为bit的载体，那么long类型为64位，可以表示0-63的数据。但申请一个Long[N]的数组，就可以表示0~(64*N-1)的数据范围了。接下来的问题就是计算好数组索引的问题，这当然难不倒各位看官了~

BitMap算法的使用

    在上文中，我们了解了BitMap算法的基本概念和原理。那接下来就是这个算法能做什么，怎样应用到实际业务中。在算法介绍中，BitMap天然是用来排序数字集合并减少数据存储空间的。但BitMap的思想和原理可不止能干这点事情。简单的做个引导，学过数字电路OR其他奇怪的硬件课程的小伙伴应该知道，元器件的状态通常是使用元器件各引脚的电位高低来表示的。那么将Bit的位数与引脚对应、记录与元器件对应、高低电位与1/0数值对应，很自然地引申出，BitMap可以用来自由地标识记录或者对象的状态。换个更形象的描述，BitMap可以很方便地给对象/记录打标签。8个Bit位可以给一条记录打上8个标签，而这在以往的业务中可能需要8个boolean字段来表示。此外，你还可以很方便地对标签进行扩展，随意地打上第9个、第10个乃至更多的标签，而不需要一次次地新增数据库字段。以java中的64为Long类型为例，一个字段可以支持最大64个标签。当然，为了实现这个业务，需要设计一些枚举以及工具类来实现诸如标签枚举和Bit值的转换，以及更多的标签查询、修改等功能。

    那么，接下来就分享一下一个使用了BitMap思想和位运算的简易标签需求所需的核心代码吧~

一、定义标签枚举

    首先，你需要一个枚举类来列举需要为记录打上的标签，枚举的key就是Bit中的位数。为了方便使用，在枚举类中需要提供根据key列表获取枚举对象的方法。需要注意的是，标签的支持是有上限的，可不要设置超过上限的标签数以引起位移越界导致标签计算错误哦。如果需要打超过上限的标签，可以新增一个Long字段，或者使用其他支持位运算的对象。（在这里，Long[]数组可能并不可行，因为数据库可能不支持直接对数组类型的数据进行我们所期望的位运算，如果撰写复杂SQL实现数组索引的话，将引起较为严重的性能问题。）

public enum EmTags {
    HAS_1(0,"存在标签1"),
    HAS_2(1,"存在标签2"),
    HAS_3(2,"存在标签3")
    ;

    private int key;
    private String desc;

    EmTags(int key, String desc){
        this.key = key;
        this.desc = desc;
    }

    public int getKey() {
        return key;
    }

    public String getDesc() {
        return desc;
    }

    public static EmTags getEmByKey(int key){
        List keys = new ArrayList();
        keys.add(key);
        List ems = getEmListByKeys(keys);
        return CollectionUtil.isEmpty(ems) ? null : ems.get(0);
    }

    public static List getEmListByKeys(List keys){
        List result = new ArrayList();
        if(CollectionUtil.isEmpty(keys)){
            return result;
        }
        for(Integer key : keys){
            for(EmTags tag : EmTags.values()){
                if(tag.getKey() == key){
                    result.add(tag);
                    break;
                }
            }
        }
        return result;
    }
}

     然后， 你需要一个简单的工具类来进行标签枚举到bit位的转换，这些转换将是打标、查询等功能的必经之路。

    // 根据给定的标签枚举列表返回对应的bit值
    public static long getBitByTags(Set tagsList){
        long result = 0;
        if(CollectionUtils.isEmpty(tagsList)){
            return result;
        }
        long base = 1;
        for(EmTags emTags : tagsList){
            result = result | base << emTags.getKey();
        }
        return result;
    }
    // 给出查询满足所有标签的记录所需的bit值列表
    public static List getQueryBitsByTags(List tagsList){
        List result = new ArrayList<>();
        if(CollectionUtils.isEmpty(tagsList)){
            return result;
        }
        long base = 1;
        for(EmTags emTags : tagsList){
            result.add(base << emTags.getKey());
        }
        return result;
    }
    // 根据给定的bit值返回所需的标签枚举列表
    public static List getTagsByBit(long bitValue){
        List result = new ArrayList<>();
        if(bitValue == 0){
            return result;
        }
        for(EmTags emTags : EmTags.values()){
            if((bitValue & 1 << emTags.getKey()) != 0){
                result.add(emTags);
            }
        }
        return result;
    }

     bit和标签枚举列表的转换应该很好理解，但是在getQueryBitsByTags方法中为什么会返回一个List<Long>呢？因为标签查询需要涵盖两个场景，一个是查询结果只要满足给定标签列表中的任意一个标签，另一种是查询结果要满足给定标签列表中的所有标签。详细的对应关系……等说到mysql对bit运算的支持，以及如何查询满足标签的记录时候，大家就明白了。

三、标签Bit与数据库交互

     最后， 你需要大约四个SQL来完成 对记录进行打标签（按位或）、取消标签（取反按位与）、查询满足任一标签的记录（按位与）、查询满足所有标签的记录（循环按位与）的功能。

<update id="addTag" parameterType="map">
    UPDATE pg_page_tags SET
    page_tags = page_tags | #{addTags, jdbcType = BIGINT}
    WHERE page_id = #{pageId, jdbcType = BIGINT}
</update>

<update id="deleteTag" parameterType="map">
    UPDATE pg_page_tags SET
    page_tags = page_tags & ~#{addTags, jdbcType = BIGINT}
    WHERE page_id = #{pageId, jdbcType = BIGINT}
</update>

<select id="queryPagesByTagsBit" parameterType="map">
    SELECT <include refid="Base_Column_List"/> FROM pg_page_tags
    WHERE page_tags & #{tagsBit, jdbcType = BIGINT}
</select>

<select id="queryPagesByTagsBit" parameterType="map">
    SELECT <include refid="Base_Column_List"/> FROM pg_page_tags
    WHERE page_status = 1
    <if test="list != null">
        AND
        <foreach collection="list" item="item" separator=" AND ">
            page_tags & #{item, jdbcType = BIGINT}
        </foreach>
    </if>
</select>

@Target({ElementType.TYPE})
// 表示可以在运行时获取到该注解
@Retention(RetentionPolicy.RUNTIME)
public @interface TagCheck {
    // 注解有一个标签枚举类型的值
    EmTags value();
}

public interface TagCheckFacade {
    Boolean checkTag(Map args);
}

三、注解及接口实现   

    然后，所有用于提供标签判断的类都需要添加上@TagCheck注解以及实现TagCheckFacade中的checkTag方法。用于表示该类用于检查哪个标签，以及具体的实现逻辑。

@Component
// 标签检查注解，标识该类用于判断页面是否满足EmTags.XXX标签
@TagCheck(EmTags.XXX)
public class XXXTagService implements TagCheckFacade {
    @Override
    // 实现checkTag方法，用于判断是否满足标签
    public Boolean checkTag(Map<String, Object> args) {
        // TODO 具体判断逻辑
        return true;
    }
}

   这样，一个扩展实现的标签判断逻辑就扩展完成了。

四、标签服务中心

   接着，我们需要提供一个标签服务中心，用于在应用中保存标签判断逻辑的具体实现类，以便在应用中动态的提供服务。实现也很简单，一个key为标签枚举，vaule为TagCheckFacade接口的Map就行了。

@Component
public class TagServiceCenter {
    private Map checkFacadeMap = new HashMap<>();

    public void registTagCheckService(EmTags emTags, TagCheckFacade tagCheckFacade){
        checkFacadeMap.put(emTags, tagCheckFacade);
    }

    public TagCheckFacade getTagCheckService(EmTags emTags){
        return checkFacadeMap.get(emTags);
    }
}

   最后，我们还需要一个服务注册器，用于在各标签服务类加载之后，将它们注册到上述的服务中心中。实现不难，只需要实现BeanPostProcessor中的 postProcessAfterInitialization方法，判断构建的bean是否实现了 TagCheckFacadehue接口并加上了@TagCheck注解。如果都实现了，就存入注册中心的map中。

@Component
public class TagCheckServiceRegister implements ApplicationContextAware, BeanPostProcessor {

    private ApplicationContext applicationContext;
    private final Log logger = LogFactory.getLog(getClass());

    @Override
    // ApplicationContextAware， 管理ApplicationContext
    public void setApplicationContext(ApplicationContext applicationContext) throws BeansException {
        this.applicationContext = applicationContext;
    }

    @Override
    public Object postProcessBeforeInitialization(Object bean, String beanName) throws BeansException {
        return bean;
    }

    @Override
    public Object postProcessAfterInitialization(Object bean, String beanName) throws BeansException {
        // 判断该bean是否实现该接口
        if(TagCheckFacade.class.isAssignableFrom(bean.getClass())){
        // 获取注解
            TagCheck tagCheck = bean.getClass().getAnnotation(TagCheck.class);
            if(tagCheck != null){
                TagServiceCenter tagServiceCenter = applicationContext.getBean(TagServiceCenter.class);
                // 获取注解中标识的标签枚举
                EmTags emTags = tagCheck.value();
                tagServiceCenter.registTagCheckService(emTags, (TagCheckFacade) bean);
            }
        }
        return bean;
    }

}

六、标签框架全家福

    好了，一个简单的标签框架就这样搭建完毕了。最后如果需要判断某个页面是否满足某个标签。只需要准备好数据，然后使用如下代码就可以了：

Map args;
// 获取标签绑定的判断实现逻辑
TagCheckFacade tagCheckFacade = tagServiceCenter.getTagCheckService(EmTags.XXX);
// 调用判断标签的逻辑
Boolean result = tagCheckFacade.checkTag(args);

    当然，如果是批量判断或者统计的话，直接遍历Tag枚举会更加方便。

HashSet tagsResult = new HashSet<>();
Map args = new HashMap<>();
for(EmTags emTags : EmTags.values()){
    TagCheckFacade tagCheckFacade = tagServiceCenter.getTagCheckService(emTags);
    if(tagCheckFacade != null && tagCheckFacade.checkTag(args)){
        tagsResult.add(emTags);
    }
}

标签系统的移植性

    经过上文可以发现，整个标签框架实现很简单，通过上述的核心代码进行扩展和二次开发并非难事。

    如要需要以jar包形式提供移植方案的话。因为枚举类型不支持Spring配置枚举值，因此需要转换标签的记录形式，但此外整体思想和框架不变。

     实际上，在该业务开发中，使用的算法实际上只有一个位运算，跟BitMap的算法似乎关系不大，但确实是BitMap算法的思想将标签和bit以及位运算结合在一起，方便地实现了标签的各种功能~而再往更深层次挖掘，是否可以进一步将各种配置（例如一些以json格式存放的配置值）抽象成标签形式，以配置key作为标签key进行关联，是否开启某项配置以是否打标的形式表示。是否可以减少重复数据的存取、解析等等。进一步优化数据库结构以及算法性能呢？这样的话，或许BItMap算法能带给我们更多~