编辑推荐

网易数帆开源API网关与容器云项目，让云原生生产落地“多快好

网易汪源：统一负载与多云环境的“开放姿态”，才是云原生

网易数帆如何用 Kubernetes“原语”搞定云原生中间件

快手打新挤爆券商系统，网易数帆推出券商稳定性保障方案

探索智慧校园新模式，网易有数在教育行业的实践分享

金融行业大数据治理之路——数据模型篇

使用MySQL的位运算实现高效的权限管理小技巧

未来已来2018-09-06 09:42

作者：刘杰

【背景介绍】

这是一个在女装项目中碰到的实际问题，网站的权限管理与省份相关，权限管理涉及两种角色：网站运维人员，商家。网站的运维人员可以管理不同省份的商家，商家具有在不同省份进行销售的权限，即两种角色与省份均是1对多的关系。

举个例子，某运维账号A具有浙江，上海两处站点管理权限，商家账号B具有浙江销售权限，商家账号C具有上海销售权限，商家D具有江苏和浙江的权限。那么运维账号A只能管理BC，不能管理账号D，因为D具有A所不具有的江苏权限。

图1 权限对应关系图，A管理BC，无法管理D

那么问题来了，对于某个登录的运维账号，如何在大量商家账号中快速找出隶属于该运维账号的呢?

【抽象模型】

设运维账号具有的权限的省份集合是O，例如O={浙江，上海}，可以管理的商家账号集合为M。设商家账号集合为B，其中每个元素是商家销售站点的集合。例如B={B1,B2,B3,B4}，B1={浙江}，B2={上海}，B3={浙江，上海},B4={浙江，江苏}，那么计算该运维账号能够管理的商家账号的集合，即Bi∈B，如果Bi ⊆O，则Bi∈M。

图2 判断一个集合是否为另一个集合的子集

【普通解决方案】

从抽象模型来看，如果我们设计一张表存储商家和销售省份的对应关系，直观的想法是，对于给定的运维账号，遍历所有的商家账号(O(n))，然后对于每个商家账号计算其对应省份集合是否为运维账号省份集合的子集，判断集合A是否为集合B的子集的时间复杂度根据算法不同分别为:

根据子集的定义判断时间复杂度为O(n^2)
算法优化为先排序后后遍历的方法时间复杂度为O(nlgn)

因此整体的时间复杂度是O(n^2lgn)

【高效解决方案】

普通的解决方案，时间复杂度很大，且设计一张关系表存储商家和省份的对应关系占用较多空间，因此在时间和空间上都可以进一步提升。在减少存储空间上，我们容易联想上使用BitMap存储账号对应的省份关系，例如，假设一共有浙江，江苏，上海三个省份，则可以使用三位bit表示账号与省份对应权限，三位bit从高到低依次表示浙江，江苏，上海，那么：

001表示具有上海权限

011表示具有江苏和上海权限 110表示具有浙江和上海的权限

上面的例子中，O={浙江，上海},则bitVal(O)=110,B={B1,B2,B3,B4}，则bitVal(B)={100,001,101,011}。依次类推可以采用34位bit存储账号具有的省份权限。

在提升时间复杂度方面，可以采用位的与操作提高算法效率，因为如果集合A是集合B的子集，则满足bitVal(A)&bitVal(B)=bitVal(B)，bitVal表示对应的bitMap值。例如：

bitVal(O)&bitVal(B1)=110&100=100=bitVal(B1)，则B1∈M bitVal(O)&bitVal(B4)=110&011=010!=BitVal(B4)，则B4∉M

通过位与操作，可以通过一次操作判断出二者是否具有包含关系，时间复杂度为O(n)，我们可以将权限的bitmap的值设为数据库的一个字段，则判断是否为子集的操作都可以在数据库端完成。杭研所使用的分布式DDB最新版本已经支持了位操作，因此这个针对某个运维账号选择它可以管理的商家账号完全可以通过一个sql语句完成。

在实践中另一个提交效率的方法是在二进制与省份转换的中，直观的想法是遍历二进制的每一位，取出其为1的所有位得到其所表达的省份的集合，这个算法与一个面试题类似：计算一个二进制数的1的个数，代码如下：

int count=0;
while (fmt != 0) {
        long fmtleft = fmt & (fmt - 1);
        count++;
        fmt = fmtleft;
}

这个算法的一个改进之处是“略过”为所有为0的二进制数字。代码如下：

public static List<Long> getCodeListByProvinceFmt(long fmt) {
        List<Long> retList = new ArrayList<>();
        while (fmt != 0) {
        //通过减法略去所有为0的位
        long fmtleft = fmt & (fmt - 1);
        //计算此时最高位为1的数值，并转换成对应省份code
        long singleFmt = fmt - fmtleft;
        Long code = provinceCodeReverseMap.get(singleFmt);
        retList.add(code);
        fmt = fmtleft;
    }
    return retList;
}