权限设计算法基础

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

最笨的方法

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

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

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

8421 码

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

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

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

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]的权限

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

TODO

其他资源

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

  • Google Dirve的权限设计

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));
	}
}


很遗憾的说,推酷将在这个月底关闭。人生海海,几度秋凉,感谢那些有你的时光。

原文 

https://blog.csdn.net/zhangxin09/article/details/107530676

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 权限设计算法基础

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址