权限设计算法基础

た入场券 2023-03-01 09:04 20阅读 0赞

权限管理在一个系统中是不可或缺的，总的来说还是一个数学的问题。

## 最笨的方法 ##

之前这个系统的权限管理是通过配置文件来处理的，大概流程是这样的，把用户分成多个用户组，然后每个用户组对应着多个用户的 id，每次访问页面的时候，都会读取这个配置文件的信息，判断登录用户的 id 属于哪个用户组，然后在页面判断这个用户组是否有访问这个链接的权限。配置文件的格式是这样的:`{"adm" : [1,2,34], "dev" : [5,6,1]}`这样会带来什么问题呢？有以下几个：

*  权限管理混乱，一个用户 id 可能会在多个权限组中
 *  每次更新配置文件，都要重新上线，麻烦
 *  页面有太多的 if 判断语句，造成代码可读性差

这是没有应用一点的数学方法来解决，等于是写死，故称为“笨方法”。

## 8421 码 ##

能不能有聪明点的方法呢？这是肯定的。这个问题可以归纳为——如何用占位最少的状态，包含多种的子状态？ 我们每次查询权限和维护时，都对这个资源的权限内容与用户的权限进行运算，便可以得知最终是否拥有权限去执行下一步；维护的时候也是，无非是增加权限和删除权限，却又不影响其他的权限。8421 码就是一种简单的解决方案，而且它是最基础的权限算法，必须掌握。

8421码，又称为 BCD 码。参见[《简单权限控制-8421法则》][-8421]、[《“与”和“或”运算实现权限管理》][Link 1]，这里主要是使用到 `&` 位与运算符的操作，而文中虽然提到“ `|` 位或运算符”，但实际更便于我们理解的说法，是十进制的加法操作。`2 | 4 =6` 即是 `2 + 4 = 6`。

8421 码缺点是权限数量有限，当权限越多，那么权限会越来越大，为 2 的 n 次方全部相加，维护起来不仅存储占空间，而且运算效率也不高。例如[这文章][Link 2]和[这篇文章][Link 3]介绍的。

## Long 类型移位算法 ##

对此，我们想到了二进制的解决方法。我们知道，权限状态无非就两有，即有或无，所以可以用 boolean 值来保存，而 boolean 类型可以用“位 Bit”来保存。Java 中 Long 类型占 8 个字节，那么 Long 其实能够保存 64 个 boolean 值，即可保存 64 个操作项的权限。

在“用户”表中保存这个 Long 值，需要将第 N 个操作权限设置为 `true` 时，只需从右向左数到第 N 位，将其值设为 1 即可，反之设为 0；需要检查第 N 位的权限值时，只需将 long 值右移 N 位，再 `&1`，即可得到权限值。本框架的权限算法就是采用这个的。如果对于移位不理解，其实无所谓，因为我们已经封装好，看如何调用实现即可（除非你想知其所以然，就要另请高贤了）。

试用 JavaScript 写出实现如下。

/** * 检查是否有权限 * @return {Boolean} true = 有权限，反之无 */
    function check(num, pos) { 
    	num = num >>> pos;
    	return (num & 1) === 1;
    }
    
    /** * 设置权限 */
    function set(num, pos, v) { 
    	var old = check(num, pos);
    	
    	if (v) { // 期望改为无权限
    		if (!old) // 原来有权限
    			num = num + (1 << pos);// 将第 pos 位设置为 1
    
    	} else { // 期望改为有权限
    		if (old) // 原来无权限
    			num = num - (1 << pos);// 将第 pos 位设置为 0
    	}
    	
    	return num;
    }
    
    var num = 0;
    num = set(num, 1, true);//设置[权限项60]为true
    num = set(num, 3, true);//设置[权限项3]为true
    num = set(num, 5, true);//设置[权限项3]为true
    num = set(num, 6, true);//设置[权限项3]为true
    num = set(num, 8, true);//设置[权限项3]为true
    
    alert(check(num, 60));//检查[权限项60]的权限
    alert(check(num, 1));//检查[权限项1]的权限
    alert(check(num, 3));//检查[权限项3]的权限

算法出处参见[《两种简单权限算法(二)》][Link 4]，还有[一种复杂点的][Link 5]。[《权限设计\[摘录\]》][Link 6]也是不错的文章。

## 实现 ##

TODO

## 其他资源 ##

*  [关于权限管理设计文章整理,希望对大家有所帮助][Link 7]
 *  [深入学习RBAC系列模型——RBAC0模型的开发与学习心得][RBAC_RBAC0]
 *  [用户、角色和权限开发  
    ][Link 8]
 *  [Google Dirve的权限设计][Google Dirve]

## SSO 单点登录 ##

*  [单点登录系统（SSO）详细设计说明书（上篇） ][SSO_]
 *  [新浪微博如何实现 SSO 的分析][SSO]

## 附录 ##

在接触 8421 码之前，我还了解过“质因数分解”的算法。利用“唯一分解定理”：任何一个大于 1 的自然数 N,如果 N 不为质数，那么 N 可以唯一分解成有限个质数的乘积，唯一分解定理。例如用质数2、3、 5、7、11…组成权限集合，某用户的权限为其子集中各整数的乘积，如 210 = 2*3*5\*7。但问题仍然是乘积会随着权限增多而变得很大。于是放弃了。

现在写过的代码保存于此。

package com.ajaxjs.user.role;
    
    import java.util.*;
    
    public class RoleUtil { 
    	/** * 分析这个数是不是质数 * * @param num */
    	public static boolean isZhishu(int num) { 
    		switch (num) { 
    		case 1:
    		case 2:
    		case 3:
    			return true;
    		}
    
    		int temp = 0;
    		for (int i = 2; i < num / 2 + 1; i++) { 
    			if (num % i == 0) { 
    				temp++;
    				break;
    			}
    		}
    
    		if (temp != 0)
    			return false;
    
    		return true;
    	}
    
    	/** * 得到一个数所有的因数 * * @param num * @return */
    	public static List<Integer> zhengChu(int num) { 
    		List<Integer> integers = new ArrayList<>();
    
    		for (int i = 2; i < num / 2; i++) { 
    			if (num % i == 0)
    				integers.add(i);
    		}
    
    		return integers;
    	}
    
    	/** * 正式求解 * * @param num * @param data * @return */
    	public static Set<Integer> getSingleKeyLock(int num, Set<Integer> data) { 
    		if (data == null)
    			data = new HashSet<>();
    
    		if (isZhishu(num)) { 
    			data.add(num);
    		} else { 
    			List<Integer> temp = zhengChu(num);
    			for (Integer integer : temp)
    				getSingleKeyLock(integer, data);
    		}
    
    		return data;
    	}
    
    	public static Set<Integer> getSingleKeyLock(int num) { 
    		return getSingleKeyLock(num, null);
    	}
    
    	/** * 求 1 到 n 所有质数 * * @param n * @return */
    	private static int[] _getPrimeNumber(int n) { 
    		int[] priArr = new int[n];
    
    		// 质数为大于1的自然数, 故i从2开始
    		for (int i = 2; i < n; i++) { 
    			// isPrime作为当前这个数是否为质数的标记位
    			boolean isPrime = true;
    
    			for (int j = 2; j < i; j++) { 
    				if (i % j == 0) { 
    					isPrime = false;
    					break;
    				}
    			}
    
    			if (isPrime)
    				priArr[i] = i;
    		}
    
    		return priArr;
    	}
    
    	/** * 求 1 到 n 所有质数 * * @param n * @return */
    	public static Integer[] getPrimeNumber(int n) { 
    		int[] arr = _getPrimeNumber(n);
    		List<Integer> list = new ArrayList<>();
    
    		for (int i = 0; i < arr.length; i++) { 
    			if (arr[i] != 0)
    				list.add(arr[i]);
    		}
    
    		return list.toArray(new Integer[list.size()]);
    	}
    
    	static int Rmax = 4; // 权限值的最大值
    
    	public static int getR(int Ki, int Lj) { 
    		int Rij = 0, Temp = Lj;
    
    		while (true) { 
    			if (Rij == Rmax)
    				break;
    
    			if ((Temp % Ki) == 0) {  // isInt() 判断是否整数
    				Rij++;
    				Temp = Temp / Ki;
    			} else
    				break;
    		}
    
    		return Rij;
    	}
    
    	@Override
    	public Long create(Map<String, Object> bean) { 
    		Integer[] ep = getExistingPrime();
    		int prime;
    
    		if (ep == null || ep.length == 0) { 
    			prime = 2;
    		} else
    			prime = getNextPrime(ep);
    
    		bean.put("accessKey", prime);
    		return super.create(bean);
    	}
    
    	/** * 获取当前最大的质数 * * @return 当前最大的质数 */
    	public Integer[] getExistingPrime() { 
    		return dao.getExistingPrime();
    	}
    
    	/** * 生成下一个质数 * * @param existingPrime 当前最大的质数 * @return */
    	public static int getNextPrime(Integer[] existingPrime) { 
    		int max = Collections.max(Arrays.asList(existingPrime));
    		Integer[] p = RoleUtil.getPrimeNumber(200);
    
    		for (int i : p) { 
    			if (i > max)
    				return i;
    		}
    
    		return 0;
    	}
    
    
    }

单测：

package com.ajaxjs.user;
    
    import static com.ajaxjs.user.role.RoleUtil.getR;
    import static com.ajaxjs.user.role.RoleUtil.getSingleKeyLock;
    import static org.junit.Assert.assertEquals;
    import static org.junit.Assert.assertNotNull;
    
    import java.util.Arrays;
    import java.util.Set;
    
    import org.junit.Test;
    
    import com.ajaxjs.user.role.RoleService;
    import com.ajaxjs.user.role.RoleUtil;
    
    public class TestRole { 
    	@Test
    	public void testGetGetExistingPrime() { 
    		Integer[] ep = new RoleService().getExistingPrime();
    		Arrays.toString(ep);
    	}
    
    	@Test
    	public void testGetGetPrimeNumber() { 
    		assertEquals("[2, 3, 5, 7]", Arrays.toString(RoleUtil.getPrimeNumber(10)));
    	}
    
    	@Test
    	public void testGetSingleKeyLock() { 
    		Set<Integer> ints = getSingleKeyLock(686070);
    		assertEquals("[2, 3, 5, 7, 11]", ints.toString());
    	}
    
    	@Test
    	public void testGetR() { 
    		int r = getR(5, 686070);
    		assertNotNull(r);
    		System.out.println("::::::" + (15 & 7));
    	}
    }

[-8421]: https://www.jianshu.com/p/ef7a15a905e6
[Link 1]: https://blog.csdn.net/looksunli/article/details/17756713
[Link 2]: https://blog.csdn.net/ajian005/article/details/8490899
[Link 3]: https://wenku.baidu.com/view/b1f4343d376baf1ffc4fad3b.html
[Link 4]: https://blog.csdn.net/hzaccp3/article/details/9361741
[Link 5]: https://blog.csdn.net/hzaccp3/article/details/9361287
[Link 6]: https://www.cnblogs.com/zmstudio/archive/2006/11/07/552959.html
[Link 7]: https://blog.csdn.net/5iasp/article/details/10706421
[RBAC_RBAC0]: https://blog.csdn.net/ks_1994/article/details/47810787
[Link 8]: https://blog.csdn.net/u010004317/article/details/53996757
[Google Dirve]: https://blog.kazaff.me/2016/03/11/Google%20Drive%E7%9A%84%E6%9D%83%E9%99%90%E8%AE%BE%E8%AE%A1/
[SSO_]: https://blog.csdn.net/YongJava/article/details/2994089
[SSO]: https://www.iteye.com/topic/1039052