# Casbin库实现权限控制



支持多种访问控制模型，如`ACL/RBAC/ABAC`等，可以实现灵活的访问权限控制

`casbin`将访问控制模型抽象到一个基于PERM(Policy,Effect,Request,Matchers)元模型的配置文件中

- policy

测试或者是说规则的定义，定义了具体的规则

- request

对访问请求的抽象，与`e.Enforce()`的参数一一对应

- matcher

匹配器，请求与每个`policy`一一匹配，生成多个匹配结果

- effect

对结果进行汇总，决定请求是允许还是拒绝

## ACL
access-control-list 访问控制列表

显示定义了每个主体对每个资源的权限情况，未定义的就没有权限，还可以加入超级管理员，只需要修改匹配器即可

### model文件
model.conf
```
[request_definition]
r = sub,obj,act

[policy_definition]
p = sub,obj,act

[matchers]
m = r.sub == p.sub && r.obj == p.obj && r.act == p.act

[policy_effect]
e = some(where (p.eft == allow))
```

### policy文件
policy.csv
```
p,dajun,data1,read
p,lizi,data2,write
```

## RBAC模型
ACL用户量一大就不得了，总不能每个用户都添加对应的策略文件吧

RBAC(role-based-access-control)通过引入角色来解决问题，给角色设置权限，而用户是属于角色，新增用户只需要赋予权限就可以了

### model文件
model.conf
```
[role_definition]
g = _, _

[matchers]
m = g(r.sub,p.sub) && r.obj == p.obj && r.act == p.act
```

### policy文件
policy.csv
```
p,admin,data,read
p,admin,data,write
p,developer,data,read
g,dajun,admin
g,lizi,developer
```

## 多个RBAC
用户和资源都有角色

```
[role_definition]
g=_,_
g2=_,_

[matchers]
m = g(r.sub,p.sub) && g2(r.obj,p.obj) && r.act == p.act
```

```
p, admin, prod, read
p, admin, prod, write
p, admin, dev, read
p, admin, dev, write
p, developer, dev, read
p, developer, dev, write
p, developer, prod, read
g, dajun, admin
g, lizi, developer
g2, prod.data, prod
g2, dev.data, dev
```

## 多层角色
为角色定义所属角色，实现多层角色关系，例如高级开发者senior也属于开发者，拥有开发者的所有权限，然后再对senior定义自己所特有的权限

只需要修改对应的策略文件，将角色作为一个普通用户去赋予对应的父权限即可，这样就可以继承父角色的权限


## RBAC domain
角色可以是全局的，也可以是特定`domain(领域)`或`tenant（租户）`，即分组

```
模型文件
[request_definition]
r = sub, dom, obj, act

[policy_definition]
p = sub, dom, obj, act

[role_definition]
g = _,_,_

[matchers]
m = g(r.sub, p.sub, r.dom) && r.dom == p.dom && r.obj == p.obj && r.act == p.obj
```

## ABAC
前面的模型对于相对静态的权限管理比较有用，但是对于特殊、动态的需求就不合适了

例如不同时间段对数据实现不同的权限控制，就适合用ABAC模型完成

```
[request_definition]
r = sub,obj,act

[policy_definition]
p = sub,onj,act

[matchers]
m = r.sub.Hour >= 9 && r.sub.Hour < 18 || r.sub.Name == r.obj.Owner

[policy_effect]
e = some(where (p.left == allow))
```

## 模型存储
存储在文件里是十分不方便的，所以casbin实现在代码中动态初始化模型

例如字符串，或者调用方法添加，但是不常用

一般情况下，casbin支持第三方的存储方法，包括`Mysql/MongoDB/Redis/Etcd`等，还可以实现自己的存储

```sql
CREATE DATABASE IF NOT EXISTS casbin;

USE casbin;

CREATE TABLE IF NOT EXISTS casbin_rule (
  p_type VARCHAR(100) NOT NULL,
  v0 VARCHAR(100),
  v1 VARCHAR(100),
  v2 VARCHAR(100),
  v3 VARCHAR(100),
  v4 VARCHAR(100),
  v5 VARCHAR(100)
);

INSERT INTO casbin_rule VALUES
('p', 'dajun', 'data1', 'read', '', '', ''),
('p', 'lizi', 'data2', 'write', '', '', '');
```

```golang
package main

import (
  "fmt"

  "github.com/casbin/casbin/v2"
  gormadapter "github.com/casbin/gorm-adapter/v2"
  _ "github.com/go-sql-driver/mysql"
)

func check(e *casbin.Enforcer, sub, obj, act string) {
  ok, _ := e.Enforce(sub, obj, act)
  if ok {
    fmt.Printf("%s CAN %s %s\n", sub, act, obj)
  } else {
    fmt.Printf("%s CANNOT %s %s\n", sub, act, obj)
  }
}

func main() {
  a, _ := gormadapter.NewAdapter("mysql", "root:12345@tcp(127.0.0.1:3306)/")
  e, _ := casbin.NewEnforcer("./model.conf", a)

  check(e, "dajun", "data1", "read")
  check(e, "lizi", "data2", "write")
  check(e, "dajun", "data1", "write")
  check(e, "dajun", "data2", "read")
}
```

Casbin

面试(他人整理的)

# Mysql的事务





事务由Mysql的引擎来实现，常见的Mysql的InnoDB引擎是支持事务的
比如就是在消费的时候，用户金额要减少，要生成用户的订单，且库存要减少，这样的操作必须全部执行或者全部不执行，否则可能就会使得用户钱减少了，但是没有得到东西的情况发生。

事务需要遵守4个特性
- 原子性
- 一致性
- 隔离性
- 持久性

- 原子性

即一个事务内的所有操作，要么全部完成，要么全部不完成，没有说完成一半的操作这一说，而且事务在执行过程中如果出错，就会回滚到事务开始的状态，就像这个事务从来没有执行过

这个原子性和redis的原子性不一样，只是称呼一样罢了，redis的原子性只是类似串行化，即在一系列给定顺序的操作执行过程中不会插入其他的操作命令

- 一致性

指事务操作前后，数据满足完整性约束，数据库保存一致性状态，例如转账的时候，A总共400花费了200，B总共700得到了200，一致性就是要求，最后的结果是A有200，B有900，而不会出现A扣除了，B却没增加的情况
- 隔离性

数据库运行多个并发事务同时对其数据库进行读写和修改的能力，隔离就是为了防止多个事务并发执行时由于交叉执行而导致数据的不一致，多个事务同时使用相同数据，不会相互干扰，且每个事务都有一个完整的数据空间，对其他并发事务是隔离开的

- 持久性
事务结束后，对数据的修改是永久的，不会因为系统故障就丢失

持久性 - 通过 redo log来保证
原子性 - 通过 undo log来保证
隔离性 - 通过 MVCC(多版本并发控制)或者锁来保证
一致性 - 通过上面三个共同保证

## 并发事务引发的问题
- 脏读
- 不可重复读
- 幻读

1. 脏读

一个事务读到了另外一个事务修改过又未提交的数据，就是脏读

例如A先读取了用户C的用户信息，然后又进行了更新，此时还没有提交事务，而又来了个事务B，也去查询了用户C的用户信息，而这个时候事务B读取到的用户信息就是事务A更新后的数据，即使没有提交事务

如果这个时候事务A出错了，事务进行了回滚，那事务B读取到的就是一个错误的用户信息了

2. 不可重复读
在一个事务内多次读取同一个数据，如果出现了前后两次读取数据不一致，则出现了不可重复读的现象

出现的原因一般是另外一个事务进行删除或修改，且进行了提交

例如A和B两个事务在同时处理，A先读取C的用户信息，然后继续执行代码，然后事务B更新了这个数据，这时A再去读取，会发现两次读取数据不一样了，就会引起代码上的问题

比如我现在读取了一个用户，权限是学生，那我就按照学生的逻辑接着处理，这时候再读取一次来进行判断，发现怎么现在这个权限变成老师了，那后续的操作直接作废了。

3. 幻读

在一个事务内多次查询某个符合查询条件的记录数量，如果出现前后两次查询到的记录数量不一致，则发生了幻读

一般是另外一个事务增加或修改了记录，使得符合查询条件的数量增多了

严重程度排序

脏读  >  不可重复读  >  幻读

## 事务的隔离级别

- Read Uncommitted 未提交读

指一个事务还未提交，它的变更就可以被其他事务读取
- Read Committed 已提交读

指一个事务提交后，变更才可以被其他事务读取
- RepeatTable Read 可重复读

指一个事务执行过程中看到的数据，一直跟这个事务启动时看到的数据是一致的，这个是Mysql InnoDB引擎的默认隔离级别
- Serializable 串行化

对记录加上读写锁，在多个事务对这条记录进行读写操作时，如果发生了读写冲突，则后访问的事务需要等待前一个事务执行完释放锁才能继续

不同数据库对规定的4种隔离级别支持程度不同，而Mysql在可重复读的隔离级别下，可以很大程度避免幻读现象，而使用串行化会很大程度影响性能

但也并不是完全解决了幻读，在某些情况下还是可能出现幻读的

- 针对快照读（普通的select）

通过MVCC方式解决了幻读，因为可重复读隔离级别下，事务执行过程中看到的数据，一直跟这个事务启动时看到的数据一致，即使其他事务中途对其进行修改，在这个事务中是查询不出来的

- 针对当前读(select... for update等语句)

通过next-key lock(记录锁+间隙锁)解决幻读，在执行该语句时，会加上next-key lock，如果有其他事务在锁范围内插入语句，就会被阻塞，无法插入

## Read View

Mysql 事务

# 最短路算法



# Dijkstra
主要是解决图中一点到其余各点的距离
思路：
就是设两个集合，一个s，一个u，先将起点加入s集合，然后更新s集合到u集合的最短距离

然后再每次从u集合找到一个离s集合最近的点，将其加入s集合，再次更新所有的点

```java
public static int[] dijkstar(int[][] graph,int startPoint){
		// 首先需要起始点到其他点的最短距离
		int[] dist = new int[graph.length];
		// 已经求出最短路径的点的集合
		boolean[] s = new boolean[graph.length];
		for(int i = 0;i<graph.length;i++) {
			if (i==startPoint) {
				s[i] = true;
			}else {
				s[i] = false;
			}
			dist[i] = graph[startPoint][i];
		}
		
		// 求到每个点的最短距离
		for(int i = 0;i<graph.length;i++) {
			int max = Integer.MIN_VALUE;
			int index = 0;
			for(int j = 0;j<graph.length;j++) {
				// 如果没在s集合，就找下一个加入s节点的
				if(!s[j]&&dist[j]<max) {
					max = dist[j];
					index = j;
				}
			}
			// 将该点加入s集合
			// index为当前要加入s的点
			s[index] = true;
			
			// 更新起点到其它点的距离
			for(int j = 0;j < graph.length;j++) {
				if(dist[j] > dist[index] + graph[index][j]) {
					dist[j] = dist[index] + graph[index][j];
				}
			}
			
			
		}
		
		return dist;
	}
	
```

# floyd
求每对点之间的最短距离

有图G=(V,E)采用邻接矩阵cost存储，另外设置一个二维数组A用来存放当前顶点之间的最短路径长度，Floyd算法的基本思想是递推产生一个矩阵序列A0，A1，...,Ak,...An,其中Ak[i][j]表示从顶点i到顶点j的路径上经过的顶点编号不大于k的最短路径长度

简单来说，就是不断的修改路径的邻接矩阵，以某个节点为中转，修改到其他节点的最短路径

```java
public static void floyd(int[][] graph) {
		
		for(int i = 0;i < graph.length;i++) {
			for(int j = 0;j<graph.length;j++) {
				// i是中转点
				for(int k = 0;k<graph.length;k++) {
					// 如果b-c + c-d 的距离小于 b-d
					if(graph[j][i] + graph[i][k] < graph[j][k]) {
						//更新b-d的距离
						graph[j][k] = graph[j][i] + graph[i][k];
					}
				}
				
			}
		}
	}
```

最短路算法

# 进程管理



## 进程
我们编写的代码只是一个存储在硬盘里的静态文件，通过编译可执行的二进制文件，当运行这个文件时，会被装载到内存中，接着CPU会执行程序中的每一条指令，那么这个运行中的程序，就被称为`进程`

如果程序中存在读写硬盘文件的代码，那么执行该指令时，由于读写速度很慢，如果CPU要等待读写得到的数据的话，那CPU利用率就是非常低的，所以要想办法在等待时机内去做其他的事，而收到通知后再回来继续，这个通知就是中断

### 进程的状态
最基本的三个是运行-阻塞-就绪，除此之外还有创建和结束状态

一个完整的进程状态变迁是：

![图片.png](http://malyue.cn/static/img/0474dbda45b1e3eccd2c481bece7d6d4.%C3%A5%C2%9B%C2%BE%C3%A7%C2%89%C2%87.png)

- 一个进程被创建时进入创建状态
- 创建完并完成初始化后，变为就绪状态
- 就绪状态被操作系统的进程调度器选中后，就分配给CPU正式运行该进程，进入运行状态
- 进程完成或者出错以后，会被操作系统作结束状态处理
- 处于运行状态的进程在运行过程中，由于分配给的运行时间片用完，重新回到就绪态
- 当进程请求某个事件，遇到阻塞必须等待的时候，例如IO事件，或者等待资源，就会进入阻塞状态
- 当进程等待的事件完成后，会从阻塞状态恢复就绪状态

且通常情况下，如果阻塞状态的进程过多，会占用很大的物理空间，所以一般会将阻塞的进程的物理内存空间移出到硬盘，等需要的时候再从硬盘移入物理内存，这个状态就是`挂起`，用来描述进程没有占用实际的物理内存空间的情况
- 阻塞挂起

进程在外存并等待某个事件的出现
- 就绪挂起

进程在外存，但只要进入内存即立刻运行

导致进程挂起的原因：
- 进程所使用的内存空间不在物理内存
- 通过sleep让进程间歇性挂起
- 用户用ctrl+z挂起一个程序的进程

### 创建进程
1. 创建进程

操作系统允许一个进程创建另外一个进程，而且允许子进程继承父进程所拥有的资源

过程如下：
- 申请一个空白的PCB，并向PCB里填入控制和管理进程的信息，比如进程唯一标识等
- 为该进程分配运行时需要的资源，比如内存资源
- 将PCB插入到就绪队列，等待被调用

2. 终止进程

- 正常结束、异常结束以及外界干预（信号kill掉）

当子进程被终止，从父进程处继承来的资源会归还给父进程，而当父进程被终止时，子进程会被变为孤儿进程，会被1号进程收养，并且由1号进程对它们完成状态收集工作

终止进程的过程：
- 查找需要终止进程的PCB
- 如果处于执行状态，则停止进程执行，释放CPU资源
- 如果其有子进程，则将子进程交给1号进程管理
- 将该进程资源全部释放
- 从PCB所在队列中删除

3. 阻塞进程

当进程在等待其余事件时，它可以采用阻塞语句将自己阻塞，而一旦被阻塞等待只能由另外一个进程唤醒

过程如下：
- 找到要被阻塞进程标识号对应的PCB
- 如果该进程为运行状态，则保护现场，将状态转为阻塞状态，停止运行
- 将该PCB插入到阻塞队列

4. 唤醒进程

阻塞态无法自己唤醒自己，所以需要等待其他进程的唤醒

过程如下：
- 在该事件的阻塞队列中找到相应进程的PCB
- 将其从阻塞队列中移出，并置状态为就绪状态
- 把该PCB插入到就绪队列中，等待调度程序调度

### 上下文切换
各个进程之间是共享CPU资源的，在不同的时候进程之间需要切换，让不同的进程可以在CPU执行，这个切换的过程就称为上下文切换

每个任务执行前，CPU需要知道任务从哪里加载，从哪里开始运行，所以操作系统需要帮助CPU设置好`CPU寄存器`和`程序计数器`

程序计数器就是用来存储CPU正在执行的指令位置，或者即将执行的下一条指令位置，这些环境就是上下文

> 即在运行前必须依赖的环境


#### 进程上下文切换
进程是由内核管理和调度的，所以进程的切换只能发生在内核态

所以，进程的上下文切换不仅包含了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈，寄存器等内核空间的资源，通常把交换的信息保存在`PCB`中，运行另外一个进程时就会把信息从PCB中取出，加载到CPU中

发生场景
- 时间片轮转，时间片耗尽了就进入就绪状态
- 系统资源不足的时候，要等待资源满足后才可以运行，这个时候进程也会进行挂起
- 当进程通过sleep主动挂起，也会重新调度
- 当高优先级的进程运行，则当前进程被挂起
- 发生硬件中断时，也会挂起，执行内核中的中断服务程序

## 线程

为什么要有线程?那自然是进程有缺点需要满足

比如一个程序，如果有多个操作，例如视频对话，首先需要读取文件，然后再进行解压缩，最后再播放，如果视频比较大，就需要在IO读取部分耗时过久，如果每个进程各执行一个功能，又需要实现进程之间的通信，共享数据，所以会很麻烦，而且维护进程的系统开销比较大

所以为了让实体之间可以并发运行，而且共享相同的地址空间，人们就发明了一个新的实体，`线程`，可以并发运行而且共享相同的内存空间

### 线程定义
线程是进程当中的一条执行流程

每个线程各自有一套独立的寄存器和栈，这样可以确保线程的控制流是独立的，而且共享代码段，数据段，解决了通信和数据共享的问题


### 进程和线程的比较
- 进程是资源分配的单位，线程是CPU调度的单位
- 进程拥有一个完整的资源平台，线程只独享必不可少的资源，如寄存器和栈
- 线程同样具有就绪、阻塞、执行三种基本状态，同样具有状态之间的转换关系
- 线程能减少并发执行的空间和时间开销

- 线程的创建耗时少，它不需要像进程一样再去创建需要的一些信息，比如内存管理、文件管理信息等，它们只需要共享这些资源即可
- 线程终止时间比进程快，因为释放的资源少
- 同一个进程内的线程切换比进程切换快，因为线程具有相同的地址空间，意味着同一个进程的线程都具有同一个页表，而进程切换的时候需要把页表给进行切换，页表切换的开销就会比较大
- 共享了文件和内存，线程之间就不需要通过内核传输数据了

### 进程的上下文切换
操作系统的任务调度实际上调度的是线程，而进程只是给线程提供了虚拟内存和全局变量等资源

而线程独有的资源就是其栈和寄存器，如果是两个不同进程的线程切换，则和进程上下文切换一样，否则的话只需要切换私有数据，寄存器等数据

### 线程的实现
- 用户线程

在用户空间实现的线程，不是由内核管理的线程，是由用户态的线程库来完成线程的管理

- 内核线程

在内核中实现的线程，是由内核管理的线程

- 轻量级进程

在内核中支持用户线程