0%

github:https://github.com/zanwen/algorithm

普通二叉搜索树

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
package top.zhenganwen.learn.algorithm.datastructure.tree;

import top.zhenganwen.learn.algorithm.commons.printer.BinaryTreeInfo;
import top.zhenganwen.learn.algorithm.commons.printer.BinaryTrees;

import java.util.*;

import static java.util.Objects.isNull;

/**
* @author zhenganwen
* @date 2019/11/6 17:48
*/
public class BinarySearchTree<E> implements BinaryTreeInfo {

protected Node<E> root;

private int size;

private Comparator<E> comparator;

public BinarySearchTree() {

}

public BinarySearchTree(Comparator<E> comparator) {
this.comparator = comparator;
}

public void add(E element) {
nonNullCheck(element);

if (root == null) {
root = createNode(element, null);
size++;
afterAdd(root);
return;
}

Node<E> parent = root, cur = root;
int compare = 0;
while (cur != null) {
parent = cur;
compare = compare(element, cur.element);
cur = compare > 0 ? cur.right : compare < 0 ? cur.left : cur;
if (cur == parent) {
cur.element = element;
return;
}
}
Node<E> node = createNode(element, parent);
if (compare > 0) {
parent.right = node;
} else {
parent.left = node;
}
size++;
afterAdd(node);
}

protected void afterAdd(Node<E> node) {

}

protected Node<E> createNode(E element, Node<E> parent) {
return new Node<>(element, parent);
}

public void remove(E element) {
remove(node(element));
}

private void remove(Node<E> node) {
if (node == null)
return;

size--;
if (hasTwoChild(node)) {
// the node's degree is 2, use node's predecessor/successor's element
// cover the node, and then delete the predecessor/successor
Node<E> successor = Objects.requireNonNull(successor(node));
node.element = successor.element;
node = successor;
}

// reach here, the degree of the node is possible only 0 or 1
// that is to say, the node only has one child
Node replacement = node.left == null ? node.right : node.left;
if (replacement != null) {
// the node's degree is 1
replacement.parent = node.parent;
if (isRoot(node)) {
root = replacement;
} else if (compare(node.element, node.parent.element) >= 0) {
node.parent.right = replacement;
} else {
node.parent.left = replacement;
}
} else {
// the node is leaf node
if (isRoot(node)) {
root = null;
} else if (compare(node.element, node.parent.element) >= 0) {
node.parent.right = null;
} else {
node.parent.left = null;
}
}
afterRemove(node);
}

protected void afterRemove(Node<E> node) {
// let auto-balance bst overwrite the method to balance the tree
}

private boolean isRoot(Node<E> node) {
return node.parent == null;
}

public boolean contains(E element) {
return node(element) != null;
}

public void clear() {
root = null;
size = 0;
}

public Node node(E element) {
Node<E> node = root;
while (node != null) {
int compare = compare(element, node.element);
if (compare == 0)
return node;
else if (compare > 0) {
node = node.right;
} else {
node = node.left;
}
}
return null;
}

private Node predecessor(Node<E> node) {
if (node.left != null) {
node = node.left;
while (node.right != null) {
node = node.right;
}
return node;
} else {
Node parent = node.parent;
while (parent != null) {
if (node == parent.right) {
return parent;
} else {
node = parent;
parent = node.parent;
}
}
return null;
}
}

private Node successor(Node<E> node) {
if (node.right != null) {
node = node.right;
while (node.left != null) {
node = node.left;
}
return node;
} else {
Node parent = node.parent;
while (parent != null) {
if (node == parent.left) {
return parent;
} else {
node = parent;
parent = node.parent;
}
}
return null;
}
}

private int compare(E insert, E current) {
if (comparator != null) {
return Objects.compare(insert, current, comparator);
}
return ((Comparable<E>) insert).compareTo(current);
}

private void nonNullCheck(E element) {
if (isNull(element)) {
throw new IllegalArgumentException("element must not be null");
}
}

@Override
public Object root() {
return root;
}

@Override
public Object left(Object node) {
return ((Node<E>) node).left;
}

@Override
public Object right(Object node) {
return ((Node<E>) node).right;
}

@Override
public Object string(Object node) {
return ((Node<E>) node).element;
}

protected static class Node<E> {
E element;
Node<E> left;
Node<E> right;
Node<E> parent;

Node(E element, Node<E> parent) {
this(element);
this.parent = parent;
}

Node(E element) {
this.element = element;
}

@Override
public String toString() {
return "Node{" +
"element=" + element +
'}';
}
}

public static void preOrderUnRecur(Node root) {
emptyTreeCheck(root);
Stack<Node> stack = new Stack<>();
StringBuilder stringBuilder = new StringBuilder();
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
stringBuilder.append(node.element).append(" ");
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
System.out.println(stringBuilder.toString());
}

private static void emptyTreeCheck(Node root) {
if (root == null) {
throw new IllegalArgumentException("empty tree");
}
}

public static void inOrderUnRecur(Node root) {
emptyTreeCheck(root);
StringBuilder sb = new StringBuilder();
Stack<Node> stack = new Stack<>();
while (root != null) {
stack.push(root);
root = root.left;
while (root == null) {
if (stack.isEmpty()) {
break;
} else {
Node node = stack.pop();
sb.append(node.element).append(" ");
root = node.right;
}
}
}
System.out.println(sb.toString());
}

private static void postOrderUnRecur(Node root) {
emptyTreeCheck(root);
StringBuilder stringBuilder = new StringBuilder();
Stack<Node> stack = new Stack<>();
stack.push(root);
Node lastAccess = null;
while (!stack.isEmpty()) {
Node node = stack.peek();
// 当来到的节点node是叶子节点或上次访问的节点是其子节点时,需要进行访问
if (isLeaf(node) || oneIsChildOfAnother(lastAccess, node)) {
stack.pop();
stringBuilder.append(node.element).append(" ");
lastAccess = node;
} else {
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
System.out.println(stringBuilder.toString());
}

public static void levelOrder(Node root) {
emptyTreeCheck(root);
StringBuilder stringBuilder = new StringBuilder();
LinkedList<Node> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
stringBuilder.append(node.element).append(" ");
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
System.out.println(stringBuilder.toString());
}

private static boolean oneIsChildOfAnother(Node one, Node another) {
return one != null && (one == another.left || one == another.right);
}

private static boolean isLeaf(Node node) {
return node.left == null && node.right == null;
}

public static int height(Node root) {
if (root == null) {
return 0;
}
return Math.max(height(root.left), height(root.right)) + 1;
}

public static int heightUnRecur(Node root) {
if (root == null) {
return 0;
}
Stack<Node> s1 = new Stack<>(), s2 = new Stack<>();
int height = 0;
s1.push(root);
while (!s1.isEmpty()) {
while (!s1.isEmpty()) {
Node node = s1.pop();
if (node.left != null) {
s2.push(node.left);
}
if (node.right != null) {
s2.push(node.right);
}
}
height++;
Stack tmp = s1;
s1 = s2;
s2 = tmp;
}
return height;
}

public static boolean isCompleteBinaryTreeUnRecur(Node root) {
if (root == null) {
return true;
}
boolean leafMode = false;
LinkedList<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.pollFirst();
if (leafMode) {
if (!isLeaf(node)) {
return false;
}
continue;
}
if (hasTwoChild(node)) {
queue.addLast(node.left);
queue.addLast(node.right);
} else if (node.left == null && node.right != null) {
return false;
} else {
leafMode = true;
if (node.left != null) {
queue.addLast(node.left);
}
}
}
return true;
}

private static boolean hasTwoChild(Node node) {
return node != null && node.left != null && node.right != null;
}

public static void main(String[] args) {
int[] arr = { 7, 4, 9, 2, 5, 8, 11, 3, 12, 1 };
BinarySearchTree<Integer> bst = new BinarySearchTree<>(Integer::compareTo);
for (int i : arr) {
bst.add(i);
}
BinaryTrees.println(bst);

// remove node that degree is 0
// bst.remove(1);
// bst.remove(3);
// bst.remove(12);
// BinaryTrees.println(bst);

// remove node that degree is 1
// bst.remove(11);
// BinaryTrees.println(bst);

// remove node that degree is 2
// bst.remove(4);
// bst.remove(9);
// BinaryTrees.println(bst);

// remove root
bst.remove(7);
BinaryTrees.println(bst);


// Node root = new Node(1);
// root.left = new Node(2);
// root.right = new Node(3);
// root.left.left = new Node(4);
// root.left.right = new Node(5);
// root.right.left = new Node(6);
// root.right.right = new Node(7);
// root.left.left.left = new Node(8);
// root.left.right.left = new Node(9);
// root.left.right.left.left = new Node(10);

// preOrderUnRecur(root);
// inOrderUnRecur(root);
// postOrderUnRecur(root);
// System.out.println(height(root));
// System.out.println(heightUnRecur(root));
// System.out.println(isCompleteBinaryTreeUnRecur(root));
// levelOrder(root);

}

}

AVL——平衡因子为1的自平衡二叉搜索树

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
package top.zhenganwen.learn.algorithm.datastructure.tree;

import top.zhenganwen.learn.algorithm.commons.printer.BinaryTrees;

/**
* @author zhenganwen
* @date 2019/11/25 13:46
*/
public class AVLTree<E> extends BinarySearchTree<E> {

@Override
protected void afterAdd(Node<E> node) {
while ((node = node.parent) != null) {
if (isBalanced(node)) {
updateHeight(node);
} else {
rebalance(node);
break;
}
}
}

/**
* remove the {@code node}, maybe cause the LL or RR situation generating,
* this depends on the height of right child's left height when remove left child's node
* and the height of left child's right height when remove right child's node.
* what's more, this time rebalance maybe cause the ancestor's unbalance.
* @param node
*/
@Override
protected void afterRemove(Node<E> node) {
while ((node = node.parent) != null) {
if (isBalanced(node)) {
updateHeight(node);
} else {
rebalance(node);
}
}
}

/**
* 平衡方案一:左旋右旋分开来做
* @param node
*/
private void rebalance2(Node<E> node) {
AVLNode grand = (AVLNode) node;
AVLNode parent = getTallerChild(grand);
AVLNode child = getTallerChild(parent);
if (parent == grand.left) {
if (child == parent.left) {
// LL rotate right
rotateRight(grand);
} else {
// LR rotate left first and then rotate right
rotateLeft(parent);
rotateRight(grand);
}
} else {
if (child == parent.right) {
// RR rotate left
rotateLeft(grand);
} else {
// RL rotate right first and then rotate left
rotateRight(parent);
rotateLeft(grand);
}
}
}

/**
* 平衡方案二:从四种变换中抽离出通用的逻辑
* @param node
*/
private void rebalance(Node<E> node) {
AVLNode grand = (AVLNode) node;
AVLNode parent = getTallerChild(grand);
AVLNode child = getTallerChild(parent);
if (parent == grand.left) {
if (child == parent.left) {
/*
LL
_______f______
| |
____d____ g
| |
_b_ e
| |
a c

f -> grand, d -> parent, b -> child
*/
rotate(grand,
cast(child.left), child, cast(child.right),
parent,
cast(parent.right), grand, cast(grand.right));
} else {
/*
LR
______f_____
| |
___b___ g
| |
a _d_
| |
c e

f -> grand, b -> parent, d -> child
*/
rotate(grand,
cast(parent.left), parent, cast(child.left),
child,
cast(child.right), grand, cast(grand.right));
}
} else {
if (child == parent.right) {
/*
RR
____b____
| |
a ____d____
| |
c _f_
| |
e g

b -> grand, d -> parent, f -> child
*/
rotate(grand,
cast(grand.left), grand, cast(parent.left),
parent,
cast(child.left), child, cast(child.right));

} else {
/*
RL
______b______
| |
a ___f___
| |
_d_ g
| |
c e

b -> grand, f -> parent, d -> child
*/
rotate(grand,
cast(grand.left), grand, cast(child.left),
child,
cast(child.right), parent, cast(parent.right));
}
}
}

private AVLNode cast(Node node) {
return (AVLNode) node;
}

/**
*
* LL
*
* inorder traversal: a b c d e f g
* |
* _______f______
* | |
* ____d____ g ____d____
* | | ===> | |
* _b_ e _b_ _f_
* | | | | | |
* a c a c e g
*
*
* RR
*
* inorder traversal: a b c d e f g
* |
* ____b____
* | |
* a ____d____ ____d____
* | | ===> | |
* c _f_ _b_ _f_
* | | | | | |
* e g a c e g
*
* LR
*
* inorder traversal: a b c d e f g
* |
* ______f_____
* | |
* ___b___ g ____d____
* | | ===> | |
* a _d_ _b_ _f_
* | | | | | |
* c e a c e g
*
*
* RL
*
* inorder traversal: a b c d e f g
* |
* ______b______
* | |
* a ___f___ ____d____
* | | ===> | |
* _d_ g _b_ _f_
* | | | | | |
* c e a c e g
*
*
* @param r the root node of the child tree
* @param a
* @param b
* @param c
* @param d
* @param e
* @param f
* @param g
*/
private void rotate(
AVLNode r,
AVLNode a,AVLNode b, AVLNode c,
AVLNode d,
AVLNode e, AVLNode f, AVLNode g
) {
// d -> new root of the child tree
d.parent = r.parent;
if (r.parent == null) root = d;
else if (r.isLeftChildOf(r.parent)) r.parent.left = d;
else r.parent.right = d;

// a-b-c
b.left = a;
b.right = c;
if (a != null) a.parent = b;
if (c != null) c.parent = b;
b.updateHeight();

// e-f-g
f.left = e;
f.right = g;
if (e != null) e.parent = f;
if (g != null) g.parent = f;
f.updateHeight();

// b-d-f
d.left = b;
d.right = f;
b.parent = d;
f.parent = d;
d.updateHeight();
}

private void rotateLeft(AVLNode node) {
AVLNode child = (AVLNode) node.right;
// rotate left
node.right = child.left;
child.left = node;
afterRotate(node, child);
}

private void afterRotate(AVLNode node, AVLNode child) {
// link parent
child.parent = node.parent;
if (node.parent == null)
root = child;
else if (node.isLeftChildOf(node.parent))
node.parent.left = child;
else
node.parent.right = child;
node.parent = child;
if (node.right != null)
node.right.parent = node;
// update height
node.updateHeight();
child.updateHeight();
}

private void rotateRight(AVLNode node) {
AVLNode child = (AVLNode) node.left;
// rotate right
node.left = child.right;
child.right = node;
afterRotate(node, child);
}

private AVLNode getTallerChild(AVLNode node) {
int r = node.getRightHeight();
int l = node.getLeftHeight();
return (AVLNode) (r > l ? node.right : node.left);
}

private void updateHeight(Node<E> node) {
((AVLNode) node).updateHeight();
}

protected boolean isBalanced(Node<E> node) {
return ((AVLNode) node).isBalanced();
}

@Override
protected Node<E> createNode(E element, Node<E> parent) {
return new AVLNode(element, parent);
}

protected static class AVLNode extends Node {
int height = 1;

AVLNode(Object element, Node parent) {
super(element, parent);
}

void updateHeight() {
int r = getRightHeight();
int l = getLeftHeight();
height = 1 + Math.max(r, l);
}

int getLeftHeight() {
return left == null ? 0 : ((AVLNode) left).height;
}

int getRightHeight() {
return right == null ? 0 : ((AVLNode) right).height;
}

int balanceFactor() {
int r = getRightHeight();
int l = getLeftHeight();
return Math.abs(r - l);
}

boolean isBalanced() {
return balanceFactor() <= 1;
}

boolean isLeftChildOf(Node node) {
return this == node.left;
}
}

public static void main(String[] args) {
AVLTree tree = new AVLTree();
for (int i = 0; i < 100; i++) {
tree.add(i);
}
BinaryTrees.println(tree);
for (int i = 0; i < 50; i++) {
tree.remove(i);
}
BinaryTrees.println(tree);

}
}

伪代码:

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
先序遍历(先根)
将根节点入栈;
当栈不空的时候:
弹出栈顶节点;
访问该节点;
如果其右子节点不可则入栈其右子节点;
如果其左子节点不空则入栈其左子节点;

中序遍历(先左)
将指针p指向根节点;
当p指向不为null时:
将p指向的节点入栈;
p向左子节点移动;
当p指向null时:
如果栈不空:
弹出栈顶节点并访问;
p指向该节点的右子节点;
如果栈为空
跳出内层循环(由于p指向null,间接地会跳出外层循环,终止遍历)

后续遍历(最后考虑根节点)
将根节点入栈;
指针lastAccess记录上次访问的节点,初始为null
当栈不空时:
瞥一眼栈顶节点;
若该节点是叶子节点或该节点是上次访问节点的父节点(注意上次访问节点为空的情况):
访问该节点;
lastAccess指向该节点;
否则:
将非空的该节点的右子节点入栈;
将非空的该节点的左子节点入栈;

代码实现:

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
class Node<E> {
E element;
Node<E> left;
Node<E> right;

Node(E element) {
this.element = element;
}

@Override
public String toString() {
return "Node{" +
"element=" + element +
'}';
}
}

private static void emptyTreeCheck(Node root) {
if (root == null) {
throw new IllegalArgumentException("empty tree");
}
}

public static void preOrderUnRecur(Node root) {
emptyTreeCheck(root);
Stack<Node> stack = new Stack<>();
StringBuilder stringBuilder = new StringBuilder();
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
stringBuilder.append(node.element).append(" ");
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
System.out.println(stringBuilder.toString());
}

public static void inOrderUnRecur(Node root) {
emptyTreeCheck(root);
StringBuilder sb = new StringBuilder();
Stack<Node> stack = new Stack<>();
while (root != null) {
stack.push(root);
root = root.left;
while (root == null) {
if (stack.isEmpty()) {
break;
} else {
Node node = stack.pop();
sb.append(node.element).append(" ");
root = node.right;
}
}
}
System.out.println(sb.toString());
}

private static boolean oneIsChildOfAnother(Node one, Node another) {
return one != null && (one == another.left || one == another.right);
}

private static boolean isLeaf(Node node) {
return node.left == null && node.right == null;
}

private static void postOrderUnRecur(Node root) {
emptyTreeCheck(root);
StringBuilder stringBuilder = new StringBuilder();
Stack<Node> stack = new Stack<>();
stack.push(root);
Node lastAccess = null;
while (!stack.isEmpty()) {
Node node = stack.peek();
// 当来到的节点node是叶子节点或上次访问的节点是其子节点时,需要进行访问
if (isLeaf(node) || oneIsChildOfAnother(lastAccess, node)) {
stack.pop();
stringBuilder.append(node.element).append(" ");
lastAccess = node;
} else {
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
System.out.println(stringBuilder.toString());
}

public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.left.left = new Node(8);
root.left.right.left = new Node(9);

// preOrderUnRecur(root);
// inOrderUnRecur(root);
postOrderUnRecur(root);
}

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
131
package top.zhenganwen.learn.algorithm.difficult;

import java.util.Stack;

/**
* @author zhenganwen
* @date 2019/11/510:48
*
* 给定一个平衡括号字符串 S,按下述规则计算该字符串的分数:
* () 得 1 分。
* AB 得 A + B 分,其中 A 和 B 是平衡括号字符串。
* (A)得 2 * A 分,其中 A 是平衡括号字符串。
*
* 示例 1:
*
* 输入: "()"
* 输出: 1
* 示例 2:
*
* 输入: "(())"
* 输出: 2
* 示例 3:
*
* 输入: "()()"
* 输出: 2
* 示例 4:
*
* 输入: "( ( ) ( ( ) ) )"
* 输出: 6
*
* 提示: S 是平衡括号字符串,且只含有 ( 和 ) 。 2 <= S.length <= 50
*
* 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/score-of-parentheses
* * 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处
*/
public class _856_SCORE_OF_PARENTHESES {

/**
*
*
* ( ( ) ( ( ) ) )
* 0 1 2 3 4 5 6 7
*
* @param S
* @return
*/
public int scoreOfParentheses(String S) {
// return division(S, 0, S.length());
return solveByStack(S);
}

/**
* let's imagine we are the dot and need move from the left to right of {@code s} step by step,
* as if the {@code s} is "(()(()))", we will be beginning from ".(()(()))" and current score is
* 0; when we move front, we arrive "(.()(()))" and current score is still 0; repeat the step,
* we will arrive "((.)(()))" and current score is 0; now we record the score of every step into
* a stack, the stack will like this [0,0,0]; continue, we arrive "(().(()))", we come across a
* right parentheses, so we pop the current score and double it and then plus it to last score,
* but there is a special situation that the current score is 0 which we should plus 1 to last
* score directly.
* take the "(()(()))" for example, the process like:
* 1. dot -> ".(()(()))" score stack -> [0]
* 2. dot -> "(.()(()))" score stack -> [0, 0]
* 3. dot -> "((.)(()))" score stack -> [0, 0, 0]
* 4. dot -> "(().(()))" score stack -> [0, 0] pop 0
* pop is 0, so plus 1 to last -> [0, 1]
* 5. dot -> "(()(.()))" score stack -> [0, 1, 0]
* 6. dot -> "(()((.)))" score stack -> [0, 1, 0, 0]
* 7. dot -> "(()(().))" score stack -> [0, 1, 0] pop 0
* pop is 0, so plus 1 to last -> [0, 1, 1]
* 8. dot -> "(()(()).)" score stack -> [0, 1] pop 1
* pop isn't 0, so double it and plus it to last -> [0, 3]
* 9. dot -> "(()(()))." score stack -> [0] pop 3
* pop isn't 0, so double it and plus it to last -> [6]
*
* complexity
* time: O(N) iterates N times
* space: O(N) stack will store N/2+1 numbers when the string is like "(((...)))"
* @param s
* @return
*/
public int solveByStack(String s) {
Stack<Integer> stack = new Stack<>();
stack.push(0);
for (char c : s.toCharArray()) {
if (c == '(') {
stack.push(0);
} else {
// c -> ')'
Integer current = stack.pop();
Integer last = stack.pop();
stack.push(last + Math.max(current * 2, 1));
}
}
return stack.pop();
}

/**
* time complexity: O(N^2)
* (((...))) n pair of parentheses, need division n/2 times, and need iterates n/2 times averagely for each division
*
* space complexity: O(N)
* each division need store s.length()/2 characters averagely, and the var e.g start, end, ans, bal can be ignored
* @param s
* @param start
* @param end
* @return
*/
public int division(String s, int start, int end) {
int ans = 0, bal = 0;
for (int i = start; i < end; i++) {
bal += s.charAt(i) == '(' ? 1 : -1;
if (bal == 0) {
if (i == start + 1) {
ans++;
} else {
ans += 2 * (division(s, start + 1, i));
}
start = i + 1;
}
}
return ans;
}

public static void main(String[] args) {
System.out.println(new _856_SCORE_OF_PARENTHESES().scoreOfParentheses("(()(()))"));
System.out.println(new _856_SCORE_OF_PARENTHESES().scoreOfParentheses("()"));
System.out.println(new _856_SCORE_OF_PARENTHESES().scoreOfParentheses("()()"));
System.out.println(new _856_SCORE_OF_PARENTHESES().scoreOfParentheses("(())()"));
}
}

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
package top.zhenganwen.learn.algorithm.datastructure.list;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Objects;

/**
* @author zhenganwen
* @date 2019/11/411:44
*/
public class CycleDoublyLinkedList<E> extends AbstractList<E> {

private Node<E> head;

public CycleDoublyLinkedList() {
head = new Node<>(null, null, null);
}

@Override
public E remove(int index) {
return index == 0 ? removeFirst() : index == size - 1 ? removeLast() : removeMiddleNode(index);
}

private E removeLast() {
emptyCheck();
Node<E> first = head.next, tail = first.prev;
E value = tail.val;
first.prev = tail.prev;
tail.prev.next = first;
size--;
return value;
}

private E removeFirst() {
emptyCheck();
Node<E> first = head.next, tail = first.prev;
E value = first.val;
head.next = first.next;
head.next.prev = tail;
tail.next = head.next;
size--;
return value;
}

private void emptyCheck() {
if (isEmpty()) {
throw new IllegalStateException("empty list");
}
}

private E removeMiddleNode(int index) {
Node<E> target = node(index);
E value = target.val;
target.prev.next = target.next;
target.next.prev = target.prev;
size--;
return value;
}

private Node<E> node(int index) {
rangeCheck(index);
boolean leftIndex = index < (size >> 1);
int reduction = leftIndex ? index : size - 1 - index;
Node<E> p = leftIndex ? head.next : head.next.prev;
if (leftIndex) {
while (reduction-- > 0) {
p = p.next;
}
} else {
while (reduction-- > 0) {
p = p.prev;
}
}
return p;
}

@Override
public E set(int index, E e) {
Node<E> node = node(index);
E value = node.val;
node.val = e;
return value;
}

@Override
public E get(int index) {
return node(index).val;
}

@Override
public int indexOf(E e) {
Node<E> node = head.next;
for (int i = 0; i < size; i++) {
if (Objects.equals(node.val, e)) {
return i;
}
node = node.next;
}
return -1;
}

@Override
public int size() {
return size;
}

private static class Node<E> {
E val;
Node<E> next;
Node<E> prev;

public Node(E val) {
this.val = val;
}

public Node() {

}

public Node(Node<E> prev, E val, Node<E> next) {
this.prev = prev;
this.val = val;
this.next = next;
}
}

private Logger logger = LoggerFactory.getLogger(getClass());

@Override
public void add(E e) {
if (size == 0) {
Node<E> first = new Node<>(e);
head.next = first.next = first.prev = first;
} else {
Node<E> first = head.next, tail = first.prev;
Node<E> node = new Node<>(tail, e, first);
tail.next = first.prev = node;
}
size++;
}

@Override
public void insert(int index, E e) {
if (index == 0) {
Node<E> first = head.next, tail = first.prev;
Node<E> node = new Node<>(tail, e, first);
first.prev = tail.next = node;
size++;
} else if (index == size) {
add(e);
return;
}
Node<E> next = node(index);
Node<E> node = new Node<>(next.prev, e, next);
node.prev.next = node.next.prev = node;
size++;
}

@Override
public String toString() {
StringBuilder builder = new StringBuilder("[");
Node<E> node = head.next;
for (int i = 0; i < size; i++) {
if (i != 0) {
builder.append(", ");
}
builder.append(node.prev.val).append("_").append(node.val).append("_").append(node.next.val);
node = node.next;
}
builder.append("]");
return builder.toString();
}

public static void main(String[] args) {
CycleDoublyLinkedList linkedList = new CycleDoublyLinkedList();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
linkedList.add(4);
linkedList.add(5);
// 1,2,3,4,5
System.out.println(linkedList);

linkedList.insert(2, 7);
linkedList.insert(6, 6);
// 1 2 7 3 4 5 6
System.out.println(linkedList);

linkedList.remove(0);
linkedList.remove(5);
linkedList.remove(1);
// 2 3 4 5
System.out.println(linkedList);

linkedList.set(2, 1);
// 2 3 1 5
System.out.println(linkedList);

// 5
System.out.println(linkedList.get(3));
}

}

根据Martin Fowler对微服务架构的阐述中的诉求可以有一个非常轻量级的集中式管理来协调这些服务。分布式配置中心Spring Cloud Config应运而生了。

阅读全文 »

概述

Zuul包含了对请求的路由过滤两个最主要的功能。

其中路由功能负责将外部请求转发到具体的微服务实例上,是实现外部访问统一入口的基础,而过滤器功能则负责对请求的处理过程进行干预,是实现请求校验,服务聚合等功能的基础.

Zuul和Eureka进行整合,将Zuul自身注册为Eureka服务治理下的应用,同时从Eureka中获得其他微服务的消息,也即以后的访问微服务都是通过Zuul跳转后获得.

注意:Zuul服务最终还是会注册进Eureka

提供代理+路由+过滤三大功能

官网资料

打个形象的比喻:拿写字楼的物业、入驻写字楼的企业、写字楼的门卫来做比,企业就是提供服务的一个个微服务,物业就是 Eureka Server,企业微服务要入住先要在物业那儿注册,而门卫就是 Zuul,客户要找企业寻求服务就要先通过门卫转发诉求而不能直接去企业办公室。门卫(前台)就是楼层所有企业服务的代理,客户诉求通过后前台带客户去相应的企业办公室,这就是路由。门卫不会让闲杂人等进入楼层,这就是过滤


实战

zuul基本配置

  1. 新建 clouddemo-zuul-gateway工程

  2. 添加依赖 eurekazuulzuul也是作为一个微服务注册到 eureka

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    <dependency>
    <groupId>org.springframework.cloud</groupId>
    <artifactId>spring-cloud-starter-zuul</artifactId>
    </dependency>
    <dependency>
    <groupId>org.springframework.cloud</groupId>
    <artifactId>spring-cloud-starter-eureka</artifactId>
    </dependency>
    <dependency>
    <groupId>org.springframework.cloud</groupId>
    <artifactId>spring-cloud-starter-config</artifactId>
    </dependency>
  3. 添加配置

    1. 服务名 spring.application.name
    2. 通过 eureka客户端连接 eureka server
    3. 注册的服务实例ID instance-id
    4. zuul代理服务以及映射路由
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    server:
    port: 9527

    spring:
    application:
    name: clouddemo-zuul-gateway

    eureka:
    instance:
    instance-id: clouddemo-zuul-gateway-9527
    prefer-ip-address: true
    client:
    serviceUrl:
    defaultZone: http://eureka1.com:7001/eureka/,http://eureka1.com:7002/eureka/,http://eureka1.com:7003/eureka/

    zuul:
    routes:
    #mydept是自己取的,通过serviceId和path分别指定真实服务名和其映射服务名
    mydept.serviceId: clouddemo-dept #代理哪个服务,同一该服务下所有服务实例的入口
    mydept.path: /mydept/** #路由映射,隐藏真实服务名,对外暴露虚拟服务名
    #如果是订单服务,则可进行如下定义
    #myorder.serviceId: xxx
    #myorder.path:/myorder/**
  4. 在启动类上添加 @EnableZuulProxy

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    package top.zhenganwen.clouddemo.zuul;

    import org.springframework.boot.SpringApplication;
    import org.springframework.boot.autoconfigure.SpringBootApplication;
    import org.springframework.cloud.netflix.zuul.EnableZuulProxy;

    @SpringBootApplication
    @EnableZuulProxy
    public class ZuulApplication {

    public static void main(String[] args) {
    SpringApplication.run(ZuulApplication.class, args);
    }
    }
  5. 测试

    1. 启动3个 eureka server

    2. 启动 clouddemo-provider

    3. 访问 localhost:8001/dept/get/1

      这种访问方式就是之前没使用 zuul时,服务调用方通过 eureka server获取服务实例进而调用

    4. 启动 clouddemo-zuul-gateway

      访问 localhost:9527/mydept/dept/get/1,其中 mydept是对 clouddemo-dept的映射,这种访问方式就是把该服务下的所有服务实例又包了一层。服务调用方要调用 clouddemo-dept服务不再是直接查出服务实例(800180028003),而是调用网关 localhost:9527/clouddemo-deptlocalhost:9527/dept(后者将真实服务名做了一个映射,这就好比滴滴打车为了司机的隐私使用了虚拟拨号隐藏司机真实手机号)

zuul也是作为一个微服务注册到 eureka

zuul路由映射规则

上述中通过 zuul代理 clouddemo-dept服务从而统一该服务下所有入口(8001、8002、8003)之后,可以通过 zuul服务URL+虚拟服务名+服务REST API(如 localhost:9527/mydept/dept/get/1)。但是 localhost:9527/clouddemo-dept/dept/get/1也能访问,这违背了一个服务唯一入口的原则。如此我们需要关闭 localhost:9527/clouddemo-dept这个暴露真实服务名的入口(通过 ignore-services):

1
2
3
4
5
zuul:
routes:
mydept.serviceId: clouddemo-dept
mydept.path: /mydept/**
ignored-services: clouddemo-dept

重启之后,localhost:9527/clouddemo-dept/dept/get/1就调不通了。

如果你想将所有带有真实服务名的入口(如 localhost:9527/clouddemo-orderlocalhost:9527/clouddemo-cart)都关闭,可以将 ignore-services设为 “*”

1
2
3
4
5
zuul:
routes:
mydept.serviceId: clouddemo-dept
mydept.path: /mydept/**
ignored-services: "*"

你甚至还可以通过prefixzuul服务URL虚拟服务名之间加一个公共前缀:

1
2
3
4
5
6
zuul:
routes:
mydept.serviceId: clouddemo-dept
mydept.path: /mydept/**
ignored-services: clouddemo-dept
prefix: /anwen

这样一来你就只能通过 localhost:9527/anwen/mydept/dept/get/1来访问了

概述

Feigh是什么

Feign是一个声明式的Web服务客户端,使得编写Web服务客户端变得非常容易,只需要创建一个接口,然后再上面添加注解即可
参考官网

使用Feign能让编写WebService客户端更加简单,它的使用方法是定义一个接口,然后再上面添加注解,用时

  • 也支持JAX-RS标准的注解.Feign
  • 也支持可拔插式的编码器和解码器,
  • Spring CLoud对Feign进行了封装,使其支持了Spring MVC标准注解和HttpMessageConverters.
  • Feign可以与Eureka和RIbbon组合使用以支持负载均衡.

Feign能干什么

Feign旨在使编写Java HTTP客户端变得更容易.

前面在使用Ribbon+RestTemplate时,利用RestTemplate对http请求的封装处理,形成了一套模板化的调用方法,但在实际开发中,由于对依赖服务的调用可能不止一处,往往一个接口会被多处调用,所以通常都会针对每个微服务自行封装一些客户端类来包装这些依赖服务的调用.所以,Feign在此基础上做了进一步的封装,由他来帮助我们定义和实现依赖服务接口的定义.在Feign的实现下,我们只需要创建一个接口并使用注解的方式来配置它(以前是Dao接口上面标注Mapper注解,现在是一个微服务接口上面标注一个Feign注解即可),即可完成对服务提供方的接口绑定,简化了使用Spring Cloud Ribbon 时,手动封装服务调用客户端的开发量.

这也是为了满足社区广大开发者面向接口编程的习惯。


实操

先回顾一下 clouddemo-consumer工程中 Controller如何调用服务:

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
package top.zhenganwen.clouddemoconsumer.controller;

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.web.bind.annotation.*;
import org.springframework.web.client.RestTemplate;
import top.zhenganwen.clouddemo.entity.Dept;

import java.util.List;

@RestController
@RequestMapping("dept")
public class DeptConsumerController {

private static final String URL_PREFIX= "http://CLOUDDEMO-DEPT";

@Autowired
private RestTemplate restTemplate;

@PostMapping("add")
public Boolean add(Dept dept) {
return restTemplate.postForObject(URL_PREFIX + "/dept/add", dept, Boolean.class);
}
@GetMapping("list")
public List<Dept> list() {
return restTemplate.getForObject(URL_PREFIX + "/dept/list", List.class);
}

@GetMapping("get/{id}")
public Dept get(@PathVariable Long id) {
return restTemplate.getForObject(URL_PREFIX + "/dept/get/" + id, Dept.class);
}
}

这里虽然 RestTemplat帮我们高度封装了 http操作,但是这并不符合原来 Controller+Service的编程习惯,我们还可以在此基础之上封装 http://CLOUDDEMO-DEPT/dept/addhttp细节,只关注接口和方法。于是Feign粉墨登场了

Feign就是对 Ribbon+RestTemplate的再封装,Feign集成了 Ribbon(通过依赖传递可以看出:引入 starter-feign会包含 starter-ribbon的依赖),自然也能够和 Rureka客户端无缝整合

工程搭建

新建工程 clouddemo-dept-feign(与 clouddemo-consumer对比来看):

  1. 引入依赖:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
<!--feign-->
<dependency>
<groupId>org.springframework.cloud</groupId>
<artifactId>spring-cloud-starter-feign</artifactId>
</dependency>
<!--eureka-->
<dependency>
<groupId>org.springframework.cloud</groupId>
<artifactId>spring-cloud-starter-config</artifactId>
</dependency>
<dependency>
<groupId>org.springframework.cloud</groupId>
<artifactId>spring-cloud-starter-eureka</artifactId>
</dependency>
<!--entity:Dept-->
<dependency>
<groupId>top.zhenganwen</groupId>
<artifactId>clouddemo-common</artifactId>
<version>1.0-SNAPSHOT</version>
</dependency>
  1. 配置 eureka集群信息:
1
2
3
4
5
eureka:
client:
serviceUrl:
defaultZone: http://eureka1.com:7001/eureka/,http://eureka2.com:7002/eureka/,http://eureka3.com:7003/eureka/
register-with-eureka: false
  1. 不在编写 RestTemplat+Ribbon(@LoadBalanced)了,而是编写接口+注解(该类要能被 @ComponentScan扫描到):
1
2
3
4
5
6
7
8
9
10
11
12
@FeignClient(value = "CLOUDDEMO-DEPT")
public interface DeptService {

@PostMapping("/dept/add")
Boolean add(Dept dept);

@GetMapping("/dept/list")
List<Dept> list();

@GetMapping("/dept/get/{id}")
Dept get(@PathVariable("id") Long id);
}

其中 value="CLOUDDEMO-DEPT"是给Ribbon针对服务做负载均获取服务实例给 RestTemplate调用的(前面说过了:Feign集成了 Ribbon并高度封装了 RestTemplate

易错点

  1. 这里@PathVariable必须加上 value值,即使形参名 Long id和路径中的 {id}同名,也不可省略,否则之后会报错:PathVariable annotation was empty on param 0
  2. 该类要能被 @ComponentScan扫描到,否则 @EnableFeignClients不会起作用
  1. 在启动类上启用EurekaFeign组件:
1
2
3
4
5
6
7
8
9
@SpringBootApplication
@EnableEurekaClient
@EnableFeignClients
public class ClouddemoFeginApplication {

public static void main(String[] args) {
SpringApplication.run(ClouddemoFeginApplication.class, args);
}
}

值得提醒的是 Feign不一定要和 Eureka一起使用,只不过本例使用了 Eureka

@EnableFeignClients只会使能被 @ComponentScan扫秒到的添加了 @FeignClient的接口起作用

  1. Feign客户端(DeptService)当做 bean注入使用:
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
package top.zhenganwen.clouddemo.controller;

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.web.bind.annotation.*;
import top.zhenganwen.clouddemo.entity.Dept;
import top.zhenganwen.clouddemo.service.DeptService;

import java.util.List;

@RestController
@RequestMapping("dept")
public class DeptController {

@Autowired
private DeptService deptService;

@PostMapping("add")
public Boolean add(Dept dept) {
return deptService.add(dept);
}
@GetMapping("list")
public List<Dept> list() {
return deptService.list();
}

@GetMapping("get/{id}")
public Dept get(@PathVariable Long id) {
return deptService.get(id);
}
}
  1. 依次启动 Eureka Server集群(3个)、clouddemo-providerclouddemo-provider2,最后启动 clouddemo-dept-feign,测试调用和负载均衡发现:localhost/dept/get/1可以正常调用负载均衡被启用并且是默认的轮询策略。

  2. 更改负载均衡策略(只需将相应的策略注册为 bean即可):

1
2
3
4
5
6
7
8
@Configuration
public class ConfigBeans {

@Bean
public IRule getRule() {
return new RandomRule();
}
}

​ 重启后再次测试发现策略已变为随机访问

对比前的 DeptConsumerController可以发现,封装了 RestTemplate之后是完完全全面向接口编程了。并且 Feign还集成了 Ribbon,有关 Ribbon的配置如 @EnableRibbon(value="CLOUDDEMO-DEPT",configuration=MyRule.class)对特定服务启用负载均衡,使用 MyRule定义的策略等都被隐藏了。

将接口迁移到common工程

上述虽然实现了 Feign的使用,隐藏了 RestTemplateRibbon的实现细节,但是如果将 DeptService写在 clouddemo-dept-feign中,如果其他消费者也要调 CLOUDDEMO-DEPT服务岂不是又要写一次。因此将 FeignClient写到 common工程以供复用才对。

  1. 引入 feign依赖:
1
2
3
4
5
<!--feign-->
<dependency>
<groupId>org.springframework.cloud</groupId>
<artifactId>spring-cloud-starter-feign</artifactId>
</dependency>
  1. DeptService复制到common工程的 top.zhenganwen.clouddemo.service中,将 common工程重新打包安装到本地仓库
  2. 删除 clouddemo-dept-feign中的top.zhenganwen.clouddemo.service文件夹
  3. 修改dept-feign工程启动类注解:
    1. 添加 @ComponentScan("top.zhenganwen.clouddemo"),因为将 DeptService迁移到 common工程后,dept-feing工程的启动类上的注解 @SpringBootApplication是扫描不到的,因此要重新定义 @ComponentScan的扫描范围是 commondept-feign工程代码的根路径,即 top.zhenganwen.clouddemo
    2. 添加 @EnableFeignClients(basePackages = {"top.zhenganwen.clouddemo.service"}),指定 FeignClient所在包
1
2
3
4
5
6
7
8
9
10
@SpringBootApplication
@EnableEurekaClient
@ComponentScan("top.zhenganwen.clouddemo")
@EnableFeignClients(basePackages = {"top.zhenganwen.clouddemo.service"})
public class ClouddemoFeginApplication {

public static void main(String[] args) {
SpringApplication.run(ClouddemoFeginApplication.class, args);
}
}
  1. 再次测试

Feign和Ribbon的区别是什么

Feign只不过是集成了 Ribbon实现了负载均衡。但与 Ribbon相比,Feign只需要定义服务绑定接口且以声明式(接口方法添加 @RequestMapping@GetMapping等,方法形参要与服务提供方接口中的保持一致)的方法,优雅而简单地实现了服务的调用:

1
2
3
4
5
6
7
8
9
10
11
12
@FeignClient(value = "CLOUDDEMO-DEPT")
public interface DeptService {

@PostMapping("/dept/add")
Boolean add(Dept dept);

@GetMapping("/dept/list")
List<Dept> list();

@GetMapping("/dept/get/{id}")
Dept get(@PathVariable("id") Long id);
}

概述

是什么

Spring Cloud Ribbon是基于Netflix Ribbon实现的一套客户端 负载均衡工具

简单的说,Ribbon是Netflix发布的开源项目,主要功能是提供客户端的软件负载均衡算法,将NetFlix的中间层服务连接在一起.Ribbon客户端组件提供一系列完善的配置项如连接超时,重试等.简单的说,就是在配置文件中列出Load Balancer(简称LB)后面所有的机器,Ribbon会自动的帮助你基于某种规则(如简单轮询,随机连接等)去连接这些机器.我们也很容易使用Ribbon实现自定义的负载均衡算法.

能干嘛

LB,即负载均衡(Load Balance),在微服务或分布式集群中经常用的一种应用.负载均衡简单的说就是将用户的请求平摊的分配到多个服务上,从而达到系统的HA(高可用).创建的负载均衡有软件Nginx,LVS,硬件F5等,相应的在中间件如:dubbo和SpringCLoud中均给我们提供了负载均衡(其中SpringCloud的负载均衡算法可以自定义).

集中式LB

在服务的消费方和提供方之间使用独立的LB设施(可以是硬件,如F5,也可以是软件,如Nginx),由该设施负责把访问请求通过某种策略转发至服务的提供方

进程内LB

将LB逻辑集成到消费方,消费方从服务注册中心获知有哪些地址可用,然后自己再从这些地址中选择出一个合适的服务器.

Ribbon就属于进程内LB,它只是一个类库,集成于消费方进程,消费方通过它来获取到服务提供方的地址.

官方资料

Ribbon


Ribbon初步配置

以 之前的 clouddemo-consumer工程为例,理解 Ribbon是一套客户端的负载均衡工具

  1. 添加Ribbon组件依赖(ribbon依赖eureka客户端,eureka又依赖config)
1
2
3
4
5
6
7
8
9
10
11
12
<dependency>
<groupId>org.springframework.cloud</groupId>
<artifactId>spring-cloud-starter-ribbon</artifactId>
</dependency>
<dependency>
<groupId>org.springframework.cloud</groupId>
<artifactId>spring-cloud-starter-config</artifactId>
</dependency>
<dependency>
<groupId>org.springframework.cloud</groupId>
<artifactId>spring-cloud-starter-eureka</artifactId>
</dependency>
  1. 添加 eureka.client配置,找服务先找 eureka
1
2
3
4
5
6
7
server.port: 80

eureka:
client:
serviceUrl:
defaultZone: http://eureka1.com:7001/eureka/,http://eureka2.com:7002/eureka/,http://eureka3.com:7003/eureka/
register-with-eureka: false #不是服务提供方,不需要注册
  1. RestTemplate远程访问工具的获取添加 @LoadBalanced
1
2
3
4
5
6
7
8
9
@Configuration
public class BeanConfiguration {

@Bean
@LoadBalanced
public RestTemplate getRestTemplate() {
return new RestTemplate();
}
}

Ribbon是一套客户端的负载均衡工具浮出水面了:这里客户端clouddemo-consumer工程,负载均衡通过 @LoadBalanced

  1. ribbon集成在 eureka客户端,因此还需添加 @EnableEurekaClient
1
2
3
4
5
6
7
8
9
10
11
12
13
14
package top.zhenganwen.clouddemoconsumer;

import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;
import org.springframework.cloud.netflix.eureka.EnableEurekaClient;

@SpringBootApplication
@EnableEurekaClient
public class ClouddemoConsumerApplication {

public static void main(String[] args) {
SpringApplication.run(ClouddemoConsumerApplication.class, args);
}
}
  1. 将原先通过 localhost:8001直接访问服务端改为通过服务名到 eureka找服务端:
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
package top.zhenganwen.clouddemoconsumer.controller;

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.web.bind.annotation.*;
import org.springframework.web.client.RestTemplate;
import top.zhenganwen.clouddemo.entity.Dept;

import java.util.List;

@RestController
@RequestMapping("dept")
public class DeptConsumerController {

// private static final String URL_PREFIX= "http://localhost:8001";
private static final String URL_PREFIX= "http://CLOUDDEMO-DEPT";

@Autowired
private RestTemplate restTemplate;

@PostMapping("add")
public Boolean add(Dept dept) {
return restTemplate.postForObject(URL_PREFIX + "/dept/add", dept, Boolean.class);
}
@GetMapping("list")
public List<Dept> list() {
return restTemplate.getForObject(URL_PREFIX + "/dept/list", List.class);
}

@GetMapping("get/{id}")
public Dept get(@PathVariable Long id) {
return restTemplate.getForObject(URL_PREFIX + "/dept/get/" + id, Dept.class);
}
}
  1. 启动三个 eureka,然后启动 clouddemo-provider,最后启动 clouddemo-consumer

  2. 测试 clouddemo-consumer

    1. localhost/dept/list:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    [
    {
    deptno: 1,
    dname: "人事部",
    db_source: "test"
    },
    {
    deptno: 2,
    dname: "技术部",
    db_source: "test"
    },
    {
    deptno: 3,
    dname: "公关部",
    db_source: "test"
    },
    {
    deptno: 4,
    dname: "销售部",
    db_source: "test"
    }
    ]

    查看控制台日志:

    1
    2
    3
    4
    5
    6
    2018-07-30 20:09:58.415  INFO 9064 --- [p-nio-80-exec-2] c.netflix.loadbalancer.BaseLoadBalancer  : Client: CLOUDDEMO-DEPT instantiated a LoadBalancer: DynamicServerListLoadBalancer:{NFLoadBalancer:name=CLOUDDEMO-DEPT,current list of Servers=[],Load balancer stats=Zone stats: {},Server stats: []}ServerList:null
    2018-07-30 20:09:58.422 INFO 9064 --- [p-nio-80-exec-2] c.n.l.DynamicServerListLoadBalancer : Using serverListUpdater PollingServerListUpdater
    2018-07-30 20:09:58.441 INFO 9064 --- [p-nio-80-exec-2] c.netflix.config.ChainedDynamicProperty : Flipping property: CLOUDDEMO-DEPT.ribbon.ActiveConnectionsLimit to use NEXT property: niws.loadbalancer.availabilityFilteringRule.activeConnectionsLimit = 2147483647
    2018-07-30 20:09:58.442 INFO 9064 --- [p-nio-80-exec-2] c.n.l.DynamicServerListLoadBalancer : DynamicServerListLoadBalancer for client CLOUDDEMO-DEPT initialized: DynamicServerListLoadBalancer:{NFLoadBalancer:name=CLOUDDEMO-DEPT,current list of Servers=[192.168.25.1:8001],Load balancer stats=Zone stats: {defaultzone=[Zone:defaultzone; Instance count:1; Active connections count: 0; Circuit breaker tripped count: 0; Active connections per server: 0.0;]
    },Server stats: [[Server:192.168.25.1:8001; Zone:defaultZone; Total Requests:0; Successive connection failure:0; Total blackout seconds:0; Last connection made:Thu Jan 01 08:00:00 CST 1970; First connection made: Thu Jan 01 08:00:00 CST 1970; Active Connections:0; total failure count in last (1000) msecs:0; average resp time:0.0; 90 percentile resp time:0.0; 95 percentile resp time:0.0; min resp time:0.0; max resp time:0.0; stddev resp time:0.0]
    ]}ServerList:org.springframework.cloud.netflix.ribbon.eureka.DomainExtractingServerList@6ff11bec

    从中可以捕获到负载均衡和服务路由痕迹

Ribbon和Eureka整合后Consumer可以直接调用服务而不用再关心地址和端口号


Ribbon负载均衡

架构图

Ribbon在工作时分成两步:

  • 第一步选择Eureka Server,它优选选择在同一个区域内负载较少的server.
  • 第二步再根据用户指定策略,从server取到的服务注册列表中选择一个地址.

其中Ribbon提供了多种策略:比如轮询,随机,根据响应时间加权.其中轮询是用户不指定策略时的默认执行策略。

我们将在已有架构基础之上再加两个服务:clouddemo-provider2clouddemo-provider3,通过 Ribbon使得 clouddemo-consumerCLOUDDEMO-DEPT服务的访问在 providerprovider2provider3三个服务实例之间做一个均衡:

实操

  1. 为新增的两个微服务创建各自独立的数据库 dept_db2dept_db3,体会每个微服务可以有自己独立的数据存储,也是为了后面负载均衡效果演示。

    1. dept_db2:
    1
    2
    3
    4
    5
    6
    7
    8
    DROP TABLE IF EXISTS `dept`;
    CREATE TABLE `dept` (
    `deptno` bigint(20) NOT NULL AUTO_INCREMENT,
    `dname` varchar(255) DEFAULT NULL,
    `db_source` varchar(255) DEFAULT NULL,
    PRIMARY KEY (`deptno`)
    ) ENGINE=InnoDB AUTO_INCREMENT=5 DEFAULT CHARSET=utf8;
    INSERT INTO `dept` VALUES ('1', '人事部', 'dept_db2');

    2.dept_db3

    1
    2
    3
    4
    5
    6
    7
    8
    DROP TABLE IF EXISTS `dept`;
    CREATE TABLE `dept` (
    `deptno` bigint(20) NOT NULL AUTO_INCREMENT,
    `dname` varchar(255) DEFAULT NULL,
    `db_source` varchar(255) DEFAULT NULL,
    PRIMARY KEY (`deptno`)
    ) ENGINE=InnoDB AUTO_INCREMENT=5 DEFAULT CHARSET=utf8;
    INSERT INTO `dept` VALUES ('1', '人事部', 'dept_db3');
  2. clouddemo-provider为模板创建clouddemo-provider2clouddemo-provider3两个子模块,以clouddemo-provider2为例:

    1. 复制 pom中的依赖
    2. 复制代码和配置文件
    3. 修改 application.yml
      1. 修改其中的端口号为 8002
      2. spring.application.name还是为 clouddemo-dept不要改变
      3. 修改数据源url为 jdbc:mysql://localhost:3306/dept_db2
      4. 修改该服务实例在 eureka上注册的id:instance-id: clouddemo-dept-8002

    clouddemo-provider3参照此步骤创建

  3. 依次启动 eureka集群、3个provider服务实例测试:

    1. 访问 eureka1.com:7001发现服务注册成功:

    1. 启动 clouddemo-consumer,访问 localhost/dept/get/1并刷新多次次,根据db_source属性值发现数据分别是轮询testdept_db2dept_db3数据库查出的数据:

      1. 第一次
      1
      { deptno: 1, dname: "人事部", db_source: "dept_db3" }
      1. 第二次
      1
      { deptno: 1, dname: "人事部", db_source: "dept_db2" }
      1. 第三次
      1
      { deptno: 1, dname: "人事部", db_source: "test" }
      1. 第四次
      1
      { deptno: 1, dname: "人事部", db_source: "dept_db3" }

现在可以发现 @LoadBalanced的作用了吧,这里的负载均衡策略我们没有提供,因此Ribbon使用了默认的轮询策略。

总结:Ribbon其实就是一个软负载均衡的客户端组件,
他可以和其他所需请求的客户端结合使用,和eureka结合只是其中一个实例


Ribbon核心组件IRule

IRule:根据特定算法中从服务列表中选取一个要访问的服务

官方提供

Ribbon为我们实现好的算法如下:

  • RoudRobinRule,轮询
  • RandomRule,随机
  • AvailabilityFilteringRule,会先过滤掉由于多次访问故障而处于断路器跳闸状态的服务,还有并发的连接数超过阈值的服务,然后对剩余的服务列表按照轮询策略进行访问
  • WeightResponseTimeRule根据平均响应时间算所有服务的权重,响应时间越快服务权重越大被选中 的概率越高.刚启动时如果统计信息不足,则使用RoudRobinRule策略,等统计信息足够,会切换到WeightedResponseTimeRule
  • RetryRule,先按照RoundRobinRule的策略获取服务,如果获取服务失败则在指定时间内会进行重试,获取可用的服务
    • 例如,当 providerprovider2provider3正常运行时,采用轮询策略。此时如果 provider2宕机了, provider2还是会被轮询到(客户端会抛异常),但是在指定时间内发现多次重试均失败之后,会将 provider2从轮询列表中剔除。
  • BestAvailableRule,会过滤掉由于多次访问故障而处于断路器跳闸状态的服务,然后选择一个并发量最小的服务
  • ZoneAvoidanceRule,默认规则,复合判断server所在区域的性能和server的可用性选择服务器

Spring Cloud Ribbon默认为我们装载了轮询策略,如果我们没有显示的声明,则采取轮询策略,如果需要更换成以上策略中的任意一个,则只需声明对应的 bean纳入Spring 管理即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package top.zhenganwen.clouddemoconsumer.cfg;

import org.springframework.cloud.client.loadbalancer.LoadBalanced;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.web.client.RestTemplate;

@Configuration
public class BeanConfiguration {

@Bean
@LoadBalanced
public RestTemplate getRestTemplate() {
return new RestTemplate();
}

@Bean
public IRule getRule(){
return RandomRule(); //调整策略为随机访问
}
}

自定义实现

特定的微服务特定的策略

上述切换成官方提供的策略只需配置对应的 bean,但是如果我只想对 CLOUDDEMO-DEPT这一个微服务指定特定的策略,而其他微服务采用默认策略该如何呢?

  1. 创建一个提供策略的配置类:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package top.zhenganwen.rule;

import com.netflix.loadbalancer.IRule;
import com.netflix.loadbalancer.RandomRule;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

@Configuration
public class MyRule {

@Bean
public IRule getRule() {
return new RandomRule();
}
}
  1. 在启动类上添加 @RibbonClient
    1. value指定特定的服务
    2. configuration指定一个配置类,该类提供了对该特定服务使用的策略(此例中:对 CLOUDDEMO-DEPT服务使用随机访问策略)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package top.zhenganwen.clouddemoconsumer;

import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;
import org.springframework.cloud.netflix.eureka.EnableEurekaClient;
import org.springframework.cloud.netflix.ribbon.RibbonClient;
import top.zhenganwen.rule.MyRule;

@SpringBootApplication
@EnableEurekaClient
@RibbonClient(value = "CLOUDDEMO-DEPT",configuration = MyRule.class)
public class ClouddemoConsumerApplication {

public static void main(String[] args) {
SpringApplication.run(ClouddemoConsumerApplication.class, args);
}
}

注意:官方警告,configuration指定的配置类(此例中是 MyRule)不能在 @ComponentScan所在包及其子包下。由于启动类的 @SpringBootApplication包含了该注解,因此上述的 MyRule没有在启动类所在包及其子包下。

最后别忘了访问 localhost/dept/get/1测试,观察 db_source属性值的变动规律

自定义Rule

需求:依旧使用轮询策略,但是要求每个服务器被调用5此后再轮询。即原来是一人一次过,改为一人5次过。

首先参考一下 RandomRule的源码:

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
public class RandomRule extends AbstractLoadBalancerRule {
Random rand = new Random();

public RandomRule() {
}

@SuppressWarnings({"RCN_REDUNDANT_NULLCHECK_OF_NULL_VALUE"})
public Server choose(ILoadBalancer lb, Object key) {
//判断是否开启负载均衡
if (lb == null) {
return null;
} else {
//选择访问哪个服务器
Server server = null;

while(server == null) {
if (Thread.interrupted()) {
return null;
}
//获取该服务下服务实例列表
List<Server> upList = lb.getReachableServers();
//获取该服务的服务实例数量
List<Server> allList = lb.getAllServers();
int serverCount = allList.size();
if (serverCount == 0) {
return null;
}

//随机出一个服务实例
int index = this.rand.nextInt(serverCount);
server = (Server)upList.get(index);

if (server == null) {
Thread.yield();
} else {
if (server.isAlive()) {
return server;
}

server = null;
Thread.yield();
}
}

return server;
}
}

public Server choose(Object key) {
return this.choose(this.getLoadBalancer(), key);
}

public void initWithNiwsConfig(IClientConfig clientConfig) {
}
}

可以看出 choose(ILoadBalancer lb, Object key)是定义策略的核心,随机算法选出服务实例只有两句:

1
2
int index = this.rand.nextInt(serverCount);
server = (Server)upList.get(index);

因此我们只需参考 RandomRule,修改其中算法部分即可写出定义的 每五次轮询策略:

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
package top.zhenganwen.rule;

import com.netflix.client.config.IClientConfig;
import com.netflix.loadbalancer.AbstractLoadBalancerRule;
import com.netflix.loadbalancer.ILoadBalancer;
import com.netflix.loadbalancer.Server;

import java.util.List;

public class MyPollRule extends AbstractLoadBalancerRule {

private int total; //记录同一个实例被连续访问的词数
private int currentIndex; //记录当前被轮询的实例的索引

public MyPollRule() {
total = 0;
currentIndex = 0;
}

@SuppressWarnings({"RCN_REDUNDANT_NULLCHECK_OF_NULL_VALUE"})
public Server choose(ILoadBalancer lb, Object key) {
//判断是否开启负载均衡
if (lb == null) {
return null;
} else {
//选择访问哪个服务器
Server server = null;

while(server == null) {
if (Thread.interrupted()) {
return null;
}
//获取该服务下服务实例列表
List<Server> upList = lb.getReachableServers();
//获取该服务的服务实例数量
List<Server> allList = lb.getAllServers();
int serverCount = allList.size();
if (serverCount == 0) {
return null;
}

//随机出一个服务实例
// int index = this.rand.nextInt(serverCount);
// server = (Server)upList.get(index);

//如果连续访问没有超过5次,则返回当前正在轮询的服务实例,并将连续访问次数递增
if (total < 5) {
server = upList.get(currentIndex);
total++;
}else {
//如果连续访问达到5次,则索引递增,访问次数归零
currentIndex++;
total = 0;
//如果当前轮询服务实例是列表中的最后一个,则将索引归零
if (currentIndex >= serverCount) {
currentIndex = 0;
}
//这里server还是为null,因此进入while循环取下一个服务实例重新对访问次数计数
}

if (server == null) {
Thread.yield();
} else {
if (server.isAlive()) {
return server;
}

server = null;
Thread.yield();
}
}

return server;
}
}

@Override
public Server choose(Object key) {
return this.choose(this.getLoadBalancer(), key);
}

@Override
public void initWithNiwsConfig(IClientConfig clientConfig) {
}
}

最后我们需要注册该 bean以启用它:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
package top.zhenganwen.rule;

import com.netflix.loadbalancer.IRule;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

@Configuration
public class MyRule {

@Bean
public IRule getRule() {
return new MyPollRule();
}
}

测试 localhost/dept/get/1,连续访问查看策略是否生效(观察 db_source属性值的变化)