避风港
0%

Top | 发表于 更新于 分类于

2020年6月6日，博客搭建基本完成啦

发表于 分类于

2023蓝桥杯广东省赛个人题解

仅供参考，不保证思路和代码的正确性。

试题 A: 日期统计

暴力，忘记判重，白给

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;

int a[101] = { 5,6,8,6,9,1,6,1,2,4,9,1,9,8,2,3,6,4,7,7,5,9,5,0,3,8,7,5,8,1,5,8,6,1,8,3,0,3,7,9,2,7,0,5,8,8,5,7,0,9,9,1,9,4,4,6,8,6,3,3,8,5,1,6,3,4,6,7,0,7,8,2,7,6,8,9,5,6,5,6,1,4,0,1,0,0,9,4,8,0,9,1,2,8,5,0,2,5,3,3 };
long long ans = 0;
int b[20];
int c[20] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
void dfs(int x, int pos) {
	if (pos == 1 && a[x] != 2) return;
	if (pos == 2 && a[x] != 0) return;
	if (pos == 3 && a[x] != 2) return;
	if (pos == 4 && a[x] != 3) return;
	b[pos] = a[x];
	if (pos != 8) {
		for (int i = x + 1; i < 100; i++) {
			dfs(i, pos + 1);
		}
	}
	else {

		int m = b[5] * 10 + b[6];
		int d = b[7] * 10 + b[8];

		if (m < 1 || m > 12) return;
		if (d < 1 || d > c[m]) return;

		cout << b[1] << b[2] << b[3] << b[4] << "-" << b[5] << b[6] << "-" << b[7] << b[8] << endl;


		ans++;

	}
}
int main() {

	for (int i = 0; i < 100; i++) {
		dfs(i, 1);
	}

	cout << ans << endl;

	return 0;
}

试题 B: 01 串的熵

暴力，记得处理四舍五入，11027421

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;

int a = 23333333;

int main() {


	int mid = a / 2;

	for (int i = mid; i >= 0; i--) {
		double x = -1.0 * i / a * log2(1.0 * i / a);
		double y = -1.0 * (a - i) / a * log2(1.0 * (a - i) / a);
		long long ans = (x * i + y * (a - i)) * 100000;

		if (ans % 10 >= 5) ans = ans / 10 + 1;
		else ans = ans / 10;

		if (ans == 116259075798) cout << i << endl;
	}


	return 0;
}

试题 C: 冶炼金属

思维，注意处理边界情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;

int n;

int main() {
	ios::sync_with_stdio(0);

	cin >> n;

	int maxx = -1;
	int minn = 1e9 + 7;

	int a, b;
	cin >> a >> b;


	if (a == b) {
		maxx = 1;
		minn = 1;
	}
	else {
		minn = a / (b + 1) + 1;
		maxx = a / b;
	}

	for (int i = 2; i <= n; i++) {
		cin >> a >> b;
		if (a == b) {
			maxx = 1;
			minn = 1;
		}
		else {
			minn = max(minn, a / (b + 1) + 1);
			maxx = min(maxx, a / b);
		}
	}

	cout << minn << " " << maxx << endl;

	return 0;
}

试题 D: 飞机降落

全排列处理，复杂度为10! * 10，可能不是最优解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
using namespace std;

int n;

int a[12];
int t[12], d[12], l[12];
int main() {
	ios::sync_with_stdio(0);

	int T;
	cin >> T;
	while (T--) {
		cin >> n;
		for (int i = 1; i <= n; i++) a[i] = i;

		for (int i = 1; i <= n; i++) {
			cin >> t[i] >> d[i] >> l[i];
		}

		int flag = 0;

		do {

			int now = 0;

			for (int i = 1; i <= n; i++) {
				if (d[a[i]] + t[a[i]] < now) break;

				if (t[a[i]] > now) {
					now = t[a[i]] + l[a[i]];
				}
				else {
					now = now + l[a[i]];
				}

				if (i == n) flag = 1;
			}
			if (flag) break;

		} while (next_permutation(a + 1, a + 1 + n));


		if (flag) cout << "YES";
		else cout << "NO";

		if (T != 0) cout << endl;
	}

	return 0;
}

试题 E: 接龙数列

简单动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;

int n;

int a[100010];
int dp[100010];
int h[100010];
int last[11];
int maxi[11];


int main() {
	ios::sync_with_stdio(0);

	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		int k = a[i];
		while (k) {
			if (k < 10) h[i] = k;
			k /= 10;
		}

	}

	for (int i = 0; i <= 9; i++) {
		last[i] = 0;
		maxi[i] = 0;
	}

	for (int i = 1; i <= n; i++) {
		dp[i] = maxi[h[i]] + 1;
		maxi[a[i] % 10] = max(maxi[a[i] % 10], dp[i]);
		last[a[i] % 10] = i;
	}

	int ans = n;
	for (int i = 0; i <= 9; i++) {
		ans = min(ans, n - maxi[i]);
	}

	cout << ans;

	return 0;
}

试题 F: 岛屿个数

首先bfs每个点，判断是否能通过0到达岛外，可以斜着走，无法到达就说明是子岛屿，记得剪枝。第二次bfs判断连通块个数，即为答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include<bits/stdc++.h>
using namespace std;

int n, m;
int a[60][60];
int flag;
int xi[8] = { 1, 0, -1, 0, 1, -1, 1, -1};
int yi[8] = { 0, 1, 0, -1, -1, 1, 1, -1};
int ans;
int ch[60][60];

int check(int x, int y) {
	if (x < 1 || x > n || y < 1 || y > m) return 0;
	return 1;
}

void init_bfs(int x, int y) {

	queue<pair<int, int>>q;
	q.push(make_pair(x, y));
	int c[60][60];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			c[i][j] = 0;
		}
	}
	c[x][y] = 1;

	while (!q.empty()) {
		auto p = q.front();
		q.pop();
		for (int i = 0; i < 8; i++) {
			int xn = p.first + xi[i];
			int yn = p.second + yi[i];
			if (check(xn, yn)) {
				if (c[xn][yn])continue;
				c[xn][yn] = 1;

				if (a[xn][yn] == 2) {

					flag = 2;
					break;
				}
				else if (a[xn][yn] == 1) {
					continue;
				}
				q.push(make_pair(xn, yn));
			}
			else {

				flag = 1;
				break;
			}
		}
		if (flag != 0) break;
	}

}

void bfs(int x, int y) {

	queue<pair<int, int>>q;
	q.push(make_pair(x, y));
	ch[x][y] = 1;

	while (!q.empty()) {
		auto p = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xn = p.first + xi[i];
			int yn = p.second + yi[i];
			if (check(xn, yn)) {
				if (ch[xn][yn])continue;
				ch[xn][yn] = 1;

				if (a[xn][yn] == 0) {
					continue;
				}

				q.push(make_pair(xn, yn));
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);

	int T;
	cin >> T;
	while (T--) {
		cin >> n >> m;
		string s;
		for (int i = 1; i <= n; i++) {
			cin >> s;
			for (int j = 0; j < m; j++) {
				a[i][j + 1] = s[j] - '0';
				ch[i][j + 1] = 0;
			}
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (a[i][j] == 0) continue;
				flag = 0;
				init_bfs(i, j);

				if (flag != 1) a[i][j] = 2;
			}
		}

		ans = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (ch[i][j] == 1 || a[i][j] != 1) continue;
				ans++;
				bfs(i, j);

			}
		}

		cout << ans;
		if (T != 0) cout << endl;
		

	}


	return 0;
}

试题 G: 子串简写

前缀和，但这个位置的题目真的这么简单么，怀疑可能读错题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;

int k;
string s;
char a, b;

int pre[1000010];

int main() {
	ios::sync_with_stdio(0);

	cin >> k;
	cin >> s >> a >> b;
	
	int n = s.length();
	long long ans = 0;

	for (int i = 0; i < n; i++) {
		if (i != 0) pre[i] = pre[i - 1];
		else pre[i] = 0;
		if (s[i] == a) pre[i]++;
		if (s[i] == b && i - k + 1 >= 0) ans += pre[i - k + 1];
	}
	
	cout << ans;

	return 0;
}

试题 H: 整数删除

维护链表和一个set，每次取出set中最小的，判断是否合法，并对链表节点和值进行修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
using namespace std;

int c[1000010];

int n, k;
long long a[500010];

int l[500010], r[500010];

set<pair<int, int>> s;

int main() {
	ios::sync_with_stdio(0);

	cin >> n >> k;

	int w = n - k;

	l[0] = r[0] = l[n + 1] = r[n + 1] = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		l[i] = i - 1;
		r[i] = i + 1;
		s.insert(make_pair(a[i], i));
	}

	while (1) {
		if (k == 0) break;

		auto it = s.begin();
		auto p = *it;

		int val = p.first, pos = p.second;
		if (c[pos] || a[pos] != val) {
			s.erase(it);
			continue;
		}

		k--;
		c[pos] = 1;
		int pl = l[pos], pr = r[pos];
		if (pl > 0 && pl <= n) {
			a[pl] += a[pos];
			r[pl] = pr;
			s.insert(make_pair(a[pl], pl));
		}
		if (pr > 0 && pr <= n) {
			a[pr] += a[pos];
			l[pr] = pl;
			s.insert(make_pair(a[pr], pr));
		}
	}

	for (int i = 1; i <= n; i++) {
		if (c[i]) continue;
		cout << a[i];
		if (w != 0) cout << " ";
		w--;
	}
	

	return 0;
}

试题 I: 景区导游

最近公共祖先+简单容斥，LCA边想边敲，敲的很烂，思路应该问题不大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<bits/stdc++.h>
using namespace std;

int pow2[21];
int n, k;
vector<pair<int, int>>edge[100010];
long long st[100010][21];
int stt[100010][21];
int fa[100010];
int dep[100010];
int kk[100010];

void init(int x, int f) {

	for (int i = 0; i < edge[x].size(); i++) {
		auto p = edge[x][i];
		int to = p.first;
		int val = p.second;

		if (to == f) continue;
		dep[to] = dep[x] + 1;
		fa[to] = x;
		st[to][0] = val;
		stt[to][0] = x;
		for (int j = 1; j <= 20; j++) {
			int now = x;
			st[to][j] = val;
			for (int k = j - 1; k >= 0; k--) {
				st[to][j] += st[now][k];
				now = stt[now][k];
			}
			stt[to][j] = now;
		}

		init(to, x);

	}

}

long long solve(int x, int y) {

	if (dep[x] > dep[y]) swap(x, y);

	int cha = dep[y] - dep[x];

	int now = y;
	long long ans = 0;
	for (int i = 20; i >= 0; i--) {
		if (pow2[i] <= cha) {
			ans += st[now][i];
			cha -= pow2[i];
			now = stt[now][i];
		}
	}

	int lpos = x, rpos = now;
	while (1) {
		if (lpos == rpos) break;
		if (stt[lpos][0] == stt[rpos][0]) {
			ans += st[lpos][0] + st[rpos][0];
			break;
		}

		for (int i = 20; i >= 0; i--) {
			if (stt[lpos][i] == stt[rpos][i]) continue;
			ans += st[lpos][i] + st[rpos][i];
			lpos = stt[lpos][i];
			rpos = stt[rpos][i];
		}
	}

	return ans;

}

int main() {
	ios::sync_with_stdio(0);

	pow2[0] = 1;
	for (int i = 1; i <= 20; i++) pow2[i] = pow2[i - 1] * 2;

	cin >> n >> k;
	for (int i = 1; i < n; i++) {
		int u, v, t;
		cin >> u >> v >> t;
		edge[u].push_back(make_pair(v, t));
		edge[v].push_back(make_pair(u, t));

	}
	dep[1] = 1;
	init(1, 0);

	for (int i = 1; i <= k; i++) cin >> kk[i];

	long long ans = 0;

	for (int i = 2; i <= k; i++) {
		ans += solve(kk[i - 1], kk[i]);
	}

	for (int i = 1; i <= k; i++) {
		long long ff = ans;
		if (i == 1) {
			ff -= solve(kk[i], kk[i + 1]);
		}
		else if (i == k) {
			ff -= solve(kk[i - 1], kk[i]);
		}
		else {
			ff -= solve(kk[i], kk[i + 1]);
			ff -= solve(kk[i - 1], kk[i]);
			ff += solve(kk[i - 1], kk[i + 1]);
		}
		cout << ff;
		if (i != k) cout << " ";
	}

	return 0;
}

试题 J: 砍树

正解没有想到，枚举砍掉的边，用LCA判断是否在一颗子树上，可以通过30%样例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<bits/stdc++.h>
using namespace std;

int pow2[21];
int n, k;
vector<int>edge[100010];
int stt[100010][21];
int fa[100010];
int dep[100010];
int kl[100010], kr[100010];
int ledge[100010], redge[100010];

void init(int x, int f) {

	for (int i = 0; i < edge[x].size(); i++) {
		int to = edge[x][i];

		if (to == f) continue;
		dep[to] = dep[x] + 1;
		fa[to] = x;
		stt[to][0] = x;
		for (int j = 1; j <= 20; j++) {
			int now = x;
			for (int k = j - 1; k >= 0; k--) {
				now = stt[now][k];
			}
			stt[to][j] = now;
		}

		init(to, x);

	}

}

int solve(int x, int y) {
	if (dep[x] > dep[y]) swap(x, y);

	int cha = dep[y] - dep[x];

	int now = y;
	for (int i = 20; i >= 0; i--) {
		if (pow2[i] <= cha) {
			cha -= pow2[i];
			now = stt[now][i];
		}
	}

	int lpos = x, rpos = now;


	while (1) {
		if (lpos == rpos) break;
		if (stt[lpos][0] == stt[rpos][0]) {
			lpos = stt[lpos][0];
			break;
		}

		for (int i = 20; i >= 0; i--) {
			if (stt[lpos][i] == stt[rpos][i]) continue;
			lpos = stt[lpos][i];
			rpos = stt[rpos][i];
		}
	}

	return lpos;

}

int main() {
	ios::sync_with_stdio(0);

	pow2[0] = 1;
	for (int i = 1; i <= 20; i++) pow2[i] = pow2[i - 1] * 2;

	cin >> n >> k;
	for (int i = 1; i < n; i++) {
		int u, v, t;
		cin >> u >> v;
		edge[u].push_back(v);
		edge[v].push_back(u);
		ledge[i] = u;
		redge[i] = v;

	}
	dep[1] = 1;
	init(1, 0);
	for (int i = 1; i <= k; i++) {
		cin >> kl[i] >> kr[i];
	}

	int ans = -1;

	for (int i = 1; i < n; i++) {
		if (dep[ledge[i]] < dep[redge[i]]) swap(ledge[i], redge[i]);

		int flag = 0;
		for (int j = 1; j <= k; j++) {
			int ansa = solve(kl[j], ledge[i]);
			int ansb = solve(kr[j], ledge[i]);

			if ((ansa == ledge[i] || ansb == ledge[i]) && ansa != ansb) continue;
			flag = 1;
			break;

		}
		if (!flag) ans = i;

	}
	cout << ans;


	return 0;
}

发表于 分类于

死锁问题

获取锁的进程在锁未释放时终止，其他进程无法获取到锁，形成死锁

解决死锁问题？

原子操作设置过期时间

过期时间的两个问题
  • 未执行完key就过期，导致其他进程获取到锁：锁续期
  • 删除到其他线程的锁：设定不冲突的key值

提升redis锁性能

分段锁

比如把相同的商品的id分段

集群引发的问题

主服务器加锁，未同步到从服务器就挂掉，选举的新的主服务器没有加锁

Redis红锁方案
  • 存活的Redis服务器有一半加锁成功，才算成功
  • 实现工具：redission

JVM的STW对Redis影响

拿到锁后，JVM发生STW，锁无法续期，其他进程可以拿到锁

使用zookeeper解决

发表于 更新于 分类于

第一章 并发编程的挑战

减少上下文切换的四种方法 p3

第二章 Java并发机制的底层实现原理

volatile如何保证可见性 p9
synchronized实现原理 p12
锁的升级 p13
处理器实现原子操作的两种方式 p17
java实现原子操作 p18
CAS实现原子操作的三大问题 p19

第三章 Java内存模型

volatile两大特性的含义（可见性与原子性） p39
双重检查锁定（单例模式） p67
类初始化的5个阶段 p74

第四章 Java并发编程基础

线程的状态 p87
队列同步器AQS p121
重入锁 p136
公平锁与非公平锁 p137
读写锁 p140

发表于 分类于
RDB AOF
持久化方式 定时对整个内存做快照 记录每一次执行的命令
数据完整性 不完整，两次备份之间会有数据丢失 相对完整，取决于刷盘策略
文件大小 会有压缩，体积小 记录命令，体积大
宕机恢复速度 很快 慢
数据恢复优先级 低，因为完整性不如AOF 高
系统资源占用 高，大量CPU与内存消耗 低，主要是磁盘IO资源，重写时占用高
使用场景 容忍数分钟数据丢失，追求更快启动速度 对数据安全性要求较高

发表于 更新于 分类于

Seata是什么？

Seata是2019年1月蚂蚁金服和阿里巴巴共同开源的分布式事务解决方案。致力于提供高性能和简单易用的分布式事务服务，为用户打造一站式的分布式解决方案。

Seata架构

Seata事务管理中有三个重要角色
  • TC - 事务协调者：维护全局和分支事务的状态，协调全局事务提交或回滚
  • TM - 事务管理器：定义全局事务的范围、开始全局事务、提交或回滚全局事务
  • RM - 资源管理器：管理分支事务处理的资源，与TC交谈以注册分支事务和报告分支事务的状态，并驱动分支事务提交或回滚
Seata提供了四种不同的分布式事务解决方案
  • XA模式：强一致分阶段事务模式，牺牲了一定的可用性，无业务侵入
  • TCC模式：最终一致的分阶段事务模式，有业务侵入
  • AT模式：最终一致的分阶段事务模式，无业务侵入，也是Seata的默认模式
  • SAGA模式：长事务模式，有业务侵入

XA模式

原理

XA规范是X/Open组织定义的分布式事务处理(DTP)标准，XA规范描述了全局的TM与局部RM之间的接口，几乎所有主流的数据库都对XA规范提供了支持

  • RM一阶段工作：
    • 注册分支事务到TC
    • 执行分支事务sql但不提交
    • 报告执行状态到TC
  • TC二阶段工作：
    • TC检测各分支事务执行状态
    • 判断提交或回滚
  • RM二阶段工作：
    • 接收TC指令，提交或回滚事务
实现XA模式

Seata的starter已经完成了XA模式的自动装配

  • 修改配置文件
1
2
seata:
    data-source-proxy-mode: XA
  • 发起全局事务的入口添加@GlobalTransactional注解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
@Override
@GlobalTransactional
public Long create(Order order) {
    // 创建订单
    orderMapper.insert(order);
    try {
        // 扣用户余额
        accountClient.deduct(order.getUserId(), order.getMoney());
        // 扣库存
        storageClient.deduct(order.getCommodityCode(), order.getCount());

    } catch (FeignException e) {
        log.error("下单失败，原因:{}", e.contentUTF8(), e);
        throw new RuntimeException(e.contentUTF8(), e);
    }
    return order.getId();
}

AT模式

原理

AT模式同样是分阶段提交的事务模型，不过弥补了XA模型中资源锁定周期过长的缺陷

  • RM一阶段工作：
    • 注册分支事务到TC
    • 记录undo-log（数据快照）
    • 执行分支事务sql并提交
    • 报告执行状态到TC
  • TC二阶段工作：
    • TC检测各分支事务执行状态
    • 判断提交或回滚，提交删除快照，回滚读取快照
  • RM二阶段回滚工作：
    • 根据undo-log恢复数据
AT模式的写隔离

全局锁：由TC（在数据库中）记录当前正在操作某行数据的事务，该事务持有全局锁，具备执行权

  • 事务1获取了全局锁，准备回滚，等待事务2释放DB锁（读写隔离）
  • 事务2持有DB锁，等待全局锁，重试默认30次，间隔10毫秒，超时释放（避免死锁）
  • 事务1获取DB锁，将数据库当前数据和更新后undo-log数据对比，判断是否一致

TCC模式

与AT模式相似，每阶段都是独立事务，但不加锁。不同的是TCC通过人工编码来实现数据恢复，需要实现三个方法

  • Try：资源的检测和预留，比如可用余额预留为冻结余额，不同的操作冻结的余额相互隔离
  • Confirm：完成资源操作业务；要求Try成功Confirm一定要成功
  • Cancel：预留资源释放，try的反向操作
优点
  • 一阶段完成直接提交事务，释放数据库资源，性能好
  • 相比AT模型，无需生成快照，无需使用全局锁，性能最强
  • 不依赖数据库事务，而是依赖补偿操作，可以用非事务数据库
缺点
  • 有代码侵入，需要人为编写try、Confirm和Cancel接口
  • 软状态，最终一致
  • 需要考虑Confirm和Cancel失败情况，做好幂等处理
空回滚

当某分支事务的try阶段阻塞时，可能导致全局事务超时而触发二阶段的cancel操作，在未执行try操作时先执行了cancel操作，这时cancel不能做回滚，就是空回滚

业务悬挂

对于已经空回滚的业务，如果以后继续执行try，就永远不可能confirm或cancel，这就是业务悬挂。应当组织执行空回滚后try操作，避免悬挂

业务分析

为了实现空回滚，防止业务悬挂，以及幂等性要求。我们必须在数据库记录预留资源信息同时，记录当前事务id和执行状态

声明TCC接口，并实现三个方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
@Service
public class AccountTCCServiceImpl implements AccountTCCService {

    @Autowired
    private AccountMapper accountMapper;
    @Autowired
    private AccountFreezeMapper accountFreezeMapper;

    @Override
    @Transactional
    public void deduct(String userId, int money) {
        //获取事务id
        String xid = RootContext.getXID();

        //业务悬挂判断
        AccountFreeze oldFreeze = accountFreezeMapper.selectById(xid);
        if(oldFreeze != null) {
            return;
        }

        //扣减可用余额
        accountMapper.deduct(userId, money);
        //记录冻结余额与事务状态
        AccountFreeze freeze = new AccountFreeze();
        freeze.setUserId(userId);
        freeze.setFreezeMoney(money);
        freeze.setState(AccountFreeze.State.TRY);
        freeze.setXid(xid);
        accountFreezeMapper.insert(freeze);
    }

    @Override
    public boolean confirm(BusinessActionContext ctx) {
        //获取事务id
        String xid = ctx.getXid();
        //根据id删除冻结记录
        int count = accountFreezeMapper.deleteById(xid);

        return count == 1;
    }

    @Override
    public boolean cancel(BusinessActionContext ctx) {
        //获取事务id,查询freeze对象
        String xid = ctx.getXid();
        String userId = ctx.getActionContext("userId").toString();
        AccountFreeze freeze = accountFreezeMapper.selectById(xid);

        //空回滚判断，判断freeze是否为null
        if(freeze == null) {
            AccountFreeze newFreeze = new AccountFreeze();
            freeze.setUserId(userId);
            freeze.setFreezeMoney(0);
            freeze.setState(AccountFreeze.State.CANCEL);
            freeze.setXid(xid);
            int count = accountFreezeMapper.insert(newFreeze);

            return count == 1;
        }

        //幂等判断
        if(freeze.getState().equals(AccountFreeze.State.CANCEL)) {
            return true;
        }

        //恢复可用余额
        accountMapper.refund(freeze.getUserId(), freeze.getFreezeMoney());

        //将冻结金额清零，状态改为CANCEL
        freeze.setFreezeMoney(0);
        freeze.setState(AccountFreeze.State.CANCEL);

        int count = accountFreezeMapper.updateById(freeze);

        return count == 1;
    }
}

Saga模式

Saga模式时SEATA提供的长事务解决方案。也分为两个阶段

  • 一阶段：直接提交事务，与TCC不同的是不做预留操作
  • 二阶段：失败则通过编写补偿业务来回滚
优点
  • 事务参与者可以基于事件驱动实现异步调用，吞吐高
  • 一阶段直接提交事务，无锁，性能好
  • 不用编写TCC中三个阶段，实现简单
缺点
  • 软状态持续时间不确定，时效性差
  • 无锁，无事务隔离，会有脏写

发表于 更新于 分类于

在分布式系统下，一个业务跨越多个服务或数据源，每个服务都是一个分支事务，要保证所有分支事务最终状态一致，这样的事务就是分布式事务。

CAP定理

分布式系统三个指标：

  • Consistency（一致性）：用户访问分布式系统中的任意节点，得到的数据必须一致
  • Availability（可用性）：用户访问集群中的任意健康节点，必须能得到响应，而不是超时或拒绝
  • Partition tolerance（分区容错性）：出现分区问题，C和A无法同时满足
    • 分区：因为网络故障或其它原因导致分布式系统中的部分节点与其它节点失去连接，形成独立分区
    • 容错：在集群出现分区时，整个系统也要持续对外提供服务

Eric Brewer认为，分布式系统无法同时满足三个指标，这个结论就是CAP定理

BASE理论

BASE理论时对CAP的一种解决思路

  • Basically Available（基本可用）：分布式系统出现故障时，允许损失部分可用性，即保证核心可用
  • Soft State（软状态）：在一定时间内，允许出现中间状态，比如临时的不一致状态
  • Eventually Consistent（最终一致性）：虽然无法保证强一致，但是在软状态结束后，最终达到数据一直

AP模式

各子事务分别执行和提交，允许出现结果不一致，然后采用弥补措施恢复数据即可，实现最终一致

CP模式

各个子事务执行后互相等待，同时提交，同时回滚，达成强一致，但事务等待过程中，处于弱可用状态

事务协调者

各个子系统之间必须能感知到彼此的事务状态，才能保证状态一致，因此需要一个事务协调者来协调每一个事务的参与者（子系统事务）

发表于 更新于 分类于

授权规则可以对调用方的来源做控制，有白名单和黑名单两种方式

  • 白名单：来源在白名单内的调用者允许访问
  • 黑名单：来源在黑名单内的调用者不允许访问

可以解决绕过网关直接访问微服务的问题

授权方法

  • 实现RequestOriginParser接口，自定义处理逻辑
1
2
3
4
5
6
7
8
9
10
11
12
13
@Component
public class HeaderOriginParser implements RequestOriginParser {
    @Override
    public String parseOrigin(HttpServletRequest request) {

        String origin = request.getHeader("origin");

        if(StringUtils.isEmpty(origin)) {
            origin = "blank";
        }
        return origin;
    }
}
  • 在gateway服务中，利用过滤器添加指定请求头
1
2
3
4
5
6
spring:
  cloud:
    gateway:
      default-filters:
        - AddRequestHeader=Truth,Itcast is freaking awesome!
        - AddRequestHeader=origin,gateway
  • 在sentinel中添加约定好的授权规则

自定义异常

实现BlockExceptionHandler接口

BlockException包含多个子类：

异常 说明
FlowException 限流异常
ParamFlowException 热点参数限流的异常
DegradeException 降级异常
AuthorityException 授权规则异常
SystemBlockException 系统规则异常

规则持久化

规则管理模式
  • 原始模式：默认模式，将规则保存在内存，重启服务丢失
  • pull模式：控制台将配置的规则推送给Sentinel客户端，客户端会保存到本地文件或数据库中。之后定时轮询更新
  • push模式：控制台将配置规则推送到远程配置中心，例如Nacos。Sentinel客户端监听Nacos，获取配置变更的推送消息，完成本地更新

发表于 分类于

虽然限流可以尽量避免因高并发而引起的服务故障，但服务还会因为其它原因而故障。而要将这些故障控制在一定范围，避免雪崩，就要靠线程隔离（舱壁模式）和熔断降级的手段。

Feign整合Sentinel

SpringCloud中，微服务调用都是通过Feign来实现的，因此做客户端保护必须整合Feign和Sentinel

  • 修改配置文件，开启Feign的Sentinel功能
  • 给FeignClient编写失败后的降级逻辑
    • 方式一：FallbackClass，无法对远程调用的异常做处理
    • 方式二：FallbackFactory，可以对远程调用的异常做处理
使用FallbackFactory实现降级逻辑
  • 定义类，实现FallbackFactory接口的create方法
1
2
3
4
5
6
7
8
9
10
11
12
13
@Slf4j
public class UserClientFallBackFactory implements FallbackFactory<UserClient> {
    @Override
    public UserClient create(Throwable throwable) {
        return new UserClient() {
            @Override
            public User findById(Long id) {
                log.error("查询用户异常", throwable);
                return new User();
            }
        };
    }
}
  • 将实现的FallbackFactory注册为一个Bean
1
2
3
4
@Bean
public UserClientFallBackFactory userClientFallBackFactory() {
    return new UserClientFallBackFactory();
}
  • 在Client接口中使用FallbackFactory（注解添加）
1
@FeignClient(value = "userservice", fallbackFactory = UserClientFallBackFactory.class)

线程隔离

  • 线程池隔离
    • 支持主动超时和异步调用
    • 但线程额外开销较大
    • 场景：低扇出
  • 信号量隔离（Sentinel默认）
    • 轻量级，无额外开销
    • 不支持主动超时、异步调用
    • 场景：高频调用，高扇出

熔断降级

也是解决雪崩问题的重要手段。由断路器统计服务调用的异常比例、慢请求比例，如果超出阈值则会熔断该服务。即拦截访问该服务的一切请求；而当服务恢复时，断路器会放行访问该服务的请求

断路器三种状态
  • Closed：不会拦截任何请求
  • Open：熔断，拦截进入该服务的请求，有持续时间
  • Half-Open：Open状态时间结束，会放行请求，根据结果切换状态
熔断策略-慢调用

业务响应时长（RT）大于指定时长的请求认定为慢调用请求。在指定时间内，如果请求数量超过设定的最小数量且慢调用比例大于设定的阈值，则触发熔断

熔断策略-异常比例

慢调用比例换成抛出异常比例即可

熔断策略-异常数

指定异常次数

发表于 更新于 分类于

雪崩问题

微服务调用链路中的某个服务故障，引起整个链路中的所有微服务都不可用

解决雪崩问题的常见方式有四种（前三种避免故障传递，流量控制预防故障发生）：

  • 超时处理：设定超时时间，请求超过一定时间没有响应就返回错误信息，不会无休止等待
  • 舱壁模式：限定每个业务能使用的线程数，避免耗尽整个tomcat资源，因此也叫线程隔离
  • 熔断降级：由断路器统计业务执行的异常比例，如果超出阈值则会熔断该业务，拦截访问该业务的一切请求
  • 流量控制：限制业务访问的QPS（每秒钟请求数量），避免服务因流量的突增而故障

服务保护技术对比(Sentinel与Hystrix)

Sentinel Hystrix
隔离策略 信号量隔离 线程池隔离/信号量隔离
熔断降级策略 基于慢调用比例或异常比例 基于失败比率
实时指标实现 滑动窗口 滑动窗口（基于RxJava）
规则配置 支持多种数据源 支持多种数据源
扩展性 多个扩展点 插件的形式
基于注解的支持 支持 支持
限流 基于QPS，支持基于调用关系的限流 有限的支持
流量整形 支持慢启动、匀速排队模式 不支持
系统自适应保护 支持 不支持
控制台 开箱即用，可配置规则、查看秒级监控、机器发现等 不完善
常见框架适配 Servlet、Spring Cloud、Dubbo、gRPC等 Servlet、Spring Cloud Netflix

安装Sentinel控制台

  • 运行jar包
  • 访问页面，默认账号密码为sentinel
  • 通过配置修改
配置项 默认值 说明
server.port 8080 服务端口
sentinel.dashboard.auth.username sentinel 默认用户名
sentinel.dashboard.auth.password sentinel 默认密码
  • 启动时修改
1
java -jar sentinel-dashboard-1.8.1.jar -Dserver.port=8090

微服务整合Sentinel

  • 引入sentinel依赖
1
2
3
4
<dependency>
    <groupId>com.alibaba.cloud</groupId>
    <artifactId>spring-cloud-starter-alibaba-sentinel</artifactId>
</dependency>
  • 配置控制台地址
1
2
3
4
5
spring:
  cloud:
    sentinel:
      transport:
        dashboard: localhost:8080
  • 访问微服务任意端点，触发sentinel监控

Sentinel限流规则

簇点链路

项目内的调用链路，链路中被监控的每个接口就是一个资源。默认情况下Sentinel会监控SpringMVC每一个端点

在Sentinel控制台设置流控规则
  • 设置QPS，并使用Apache JMeter测试
  • 高级配置：流控模式、流控效果

  • 流控模式：直接、关联、链路

    • 直接：默认模式，统计当前资源请求，触发阈值对当前资源限流
    • 关联：统计与当前资源相关的另一个资源，触发阈值对当前资源限流(A触发阈值对B限流)，如触发修改订单阈值，对查询订单限流
    • 链路：只统计从指定链路访问到本地的资源的请求，触发阈值时，对指定链路限流

  • 流控效果，请求达到流控阈值时应该采取的措施，包括三种：快速失败、warm up、排队等待

    • 快速失败：达到阈值后，新的请求立即被拒绝抛出FlowException异常
    • warm up：预热模式，对超出阈值的请求同样拒绝，但这种模式的阈值会动态变化，从小增大到最大阈值
    • 排队等待：让所有请求按照先后次序排队执行，间隔不小于指定时常
添加限流方法

  • Sentinel默认只标记Controller中的方法为资源，如果要标记其它方法，需要利用@SentinelResource注解

  • Sentinel默认会将Controller方法做context整合，导致链路模式的流控失效，需要修改application.yml

1
2
3
4
spring:
  cloud:
    sentinel:
      web-context-unify: false #关闭context整合
流控效果-warm up

应对服务冷启动的一种方案，请求阈值初始值为threshold/coldFactor，持续指定时长后，逐渐提高到threshold，coldFactor（冷启动因子）默认值为3

流控效果-排队等待

让所有请求进入一个队列中，然后按着阈值允许的时间间隔依次执行。后来的请求必须等待前面执行完成，如果请求预期时间超出最大时长，则会被拒绝

  • 例如，QPS=5，也就是每200ms处理一个请求。timeout=2000，意味着等待超过2000ms就会抛出异常
热点参数限流

分别统计与设定参数值相同的请求，判断是否超过QPS阈值

  • 例如参数索引为0，单机阈值为5，统计窗口时长为1，含义为：对当前资源0号参数（第一个参数）的请求做统计，每1秒的请求数量不超过5
  • 高级选项可以对部分参数做例外配置