前言
在互聯網應用中，流量洪峰是常有的事情。在應對流量洪峰時，通用的處理模式一般有排隊、限流，這樣可以非常直接有效的保護系統，防止系統被打爆。另外，通過限流技術手段，可以讓整個系統的運行更加平穩。今天要與大家分享一下限流算法和C#版本的組件。
一、令牌桶算法：
令牌桶算法的基本過程如下：
- 假如用戶配置的平均發送速率為r，則每隔1/r秒速率將一個令牌被加入到桶中；
- 假設桶最多可以存發b個令牌。當桶中的令牌達到上限后，丟棄令牌。
- 當一個有請求到達時，首先去令牌桶獲取令牌，能夠取到，則處理這個請求
- 如果桶中沒有令牌，那么請求排隊或者丟棄
工作過程包括3個階段：產生令牌、消耗令牌和判斷數據包是否通過。其中涉及到2個參數：令牌產生的速率和令牌桶的大小，這個過程的具體工作如下。
- 產生令牌：周期性的以固定速率向令牌桶中增加令牌，桶中的令牌不斷增多。如果桶中令牌數已到達上限，則丟棄多余令牌。
- 消費 令牌：業務程序根據具體業務情況消耗桶中的令牌。消費一次，令牌桶令牌減少一個。
- 判斷是否通過：判斷是否已有令牌桶是否存在有效令牌，當桶中的令牌數量可以滿足需求時，則繼續業務處理，否則將掛起業務，等待令牌。
下面是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
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
|
class TokenBucketLimitingService: ILimitingService { private LimitedQueue<object> limitedQueue = null; private CancellationTokenSource cancelToken; private Task task = null; private int maxTPS; private int limitSize; private object lckObj = new object(); public TokenBucketLimitingService(int maxTPS, int limitSize) { this.limitSize = limitSize; this.maxTPS = maxTPS; if (this.limitSize <= 0) this.limitSize = 100; if(this.maxTPS <=0) this.maxTPS = 1; limitedQueue = new LimitedQueue<object>(limitSize); for (int i = 0; i < limitSize; i++) { limitedQueue.Enqueue(new object()); } cancelToken = new CancellationTokenSource(); task = Task.Factory.StartNew(new Action(TokenProcess), cancelToken.Token); } /// <summary> /// 定時消息令牌 /// </summary> private void TokenProcess() { int sleep = 1000 / maxTPS; if (sleep == 0) sleep = 1; DateTime start = DateTime.Now; while (cancelToken.Token.IsCancellationRequested ==false) { try { lock (lckObj) { limitedQueue.Enqueue(new object()); } } catch { } finally { if (DateTime.Now - start < TimeSpan.FromMilliseconds(sleep)) { int newSleep = sleep - (int)(DateTime.Now - start).TotalMilliseconds; if (newSleep > 1) Thread.Sleep(newSleep - 1); //做一下時間上的補償 } start = DateTime.Now; } } } public void Dispose() { cancelToken.Cancel(); } /// <summary> /// 請求令牌 /// </summary> /// <returns>true：獲取成功，false：獲取失敗</returns> public bool Request() { if (limitedQueue.Count <= 0) return false; lock (lckObj) { if (limitedQueue.Count <= 0) return false; object data = limitedQueue.Dequeue(); if (data == null) return false; } return true; } } |
|
1
2
3
4
5
6
7
8
|
public interface ILimitingService:IDisposable { /// <summary> /// 申請流量處理 /// </summary> /// <returns>true：獲取成功，false：獲取失敗</returns> bool Request(); } |
|
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
|
public class LimitingFactory { /// <summary> /// 創建限流服務對象 /// </summary> /// <param name="limitingType">限流模型</param> /// <param name="maxQPS">最大QPS</param> /// <param name="limitSize">最大可用票據數</param> public static ILimitingService Build(LimitingType limitingType = LimitingType.TokenBucket, int maxQPS = 100, int limitSize = 100) { switch (limitingType) { case LimitingType.TokenBucket: default: return new TokenBucketLimitingService(maxQPS, limitSize); case LimitingType.LeakageBucket: return new LeakageBucketLimitingService(maxQPS, limitSize); } } } /// <summary> /// 限流模式 /// </summary> public enum LimitingType { TokenBucket,//令牌桶模式 LeakageBucket//漏桶模式 }public class LimitedQueue<T> : Queue<T> { private int limit = 0; public const string QueueFulled = "TTP-StreamLimiting-1001"; public int Limit { get { return limit; } set { limit = value; } } public LimitedQueue() : this(0) { } public LimitedQueue(int limit) : base(limit) { this.Limit = limit; } public new bool Enqueue(T item) { if (limit > 0 && this.Count >= this.Limit) { return false; } base.Enqueue(item); return true; } } |
調用方法：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
var service = LimitingFactory.Build(LimitingType.TokenBucket, 500, 200);while (true){ var result = service.Request(); //如果返回true，說明可以進行業務處理，否則需要繼續等待 if (result) { //業務處理...... } else Thread.Sleep(1);} |
二、漏桶算法
聲明一個固定容量的桶，每接受到一個請求向桶中添加一個令牌，當令牌桶達到上線后請求丟棄或等待，具體算法如下：
- 創建一個固定容量的漏桶，請求到達時向漏桶添加一個令牌
- 如果請求添加令牌不成功，請求丟棄或等待
- 另一個線程以固定的速率消費桶里的令牌
工作過程也包括3個階段：產生令牌、消耗令牌和判斷數據包是否通過。其中涉及到2個參數：令牌自動消費的速率和令牌桶的大小，個過程的具體工作如下。
- 產生令牌：業務程序根據具體業務情況申請令牌。申請一次，令牌桶令牌加一。如果桶中令牌數已到達上限，則掛起業務后等待令牌。
- 消費令牌：周期性的以固定速率消費令牌桶中令牌，桶中的令牌不斷較少。
- 判斷是否通過：判斷是否已有令牌桶是否存在有效令牌，當桶中的令牌數量可以滿足需求時，則繼續業務處理，否則將掛起業務，等待令牌。
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
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
|
class LeakageBucketLimitingService: ILimitingService { private LimitedQueue<object> limitedQueue = null; private CancellationTokenSource cancelToken; private Task task = null; private int maxTPS; private int limitSize; private object lckObj = new object(); public LeakageBucketLimitingService(int maxTPS, int limitSize) { this.limitSize = limitSize; this.maxTPS = maxTPS; if (this.limitSize <= 0) this.limitSize = 100; if (this.maxTPS <= 0) this.maxTPS = 1; limitedQueue = new LimitedQueue<object>(limitSize); cancelToken = new CancellationTokenSource(); task = Task.Factory.StartNew(new Action(TokenProcess), cancelToken.Token); } private void TokenProcess() { int sleep = 1000 / maxTPS; if (sleep == 0) sleep = 1; DateTime start = DateTime.Now; while (cancelToken.Token.IsCancellationRequested == false) { try { if (limitedQueue.Count > 0) { lock (lckObj) { if (limitedQueue.Count > 0) limitedQueue.Dequeue(); } } } catch { } finally { if (DateTime.Now - start < TimeSpan.FromMilliseconds(sleep)) { int newSleep = sleep - (int)(DateTime.Now - start).TotalMilliseconds; if (newSleep > 1) Thread.Sleep(newSleep - 1); //做一下時間上的補償 } start = DateTime.Now; } } } public void Dispose() { cancelToken.Cancel(); } public bool Request() { if (limitedQueue.Count >= limitSize) return false; lock (lckObj) { if (limitedQueue.Count >= limitSize) return false; return limitedQueue.Enqueue(new object()); } } } |
調用方法：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
var service = LimitingFactory.Build(LimitingType.LeakageBucket, 500, 200);while (true){ var result = service.Request(); //如果返回true，說明可以進行業務處理，否則需要繼續等待 if (result) { //業務處理...... } else Thread.Sleep(1);} |
兩類限流算法雖然非常相似，但是還是有些區別的，供大家參考！
漏桶算法能夠強行限制數據的傳輸速率。在某些情況下，漏桶算法不能夠有效地使用網絡資源。因為漏桶的漏出速率是固定的。
令牌桶算法能夠在限制數據的平均傳輸速率的同時還允許某種程度的突發傳輸.
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，如果有疑問大家可以留言交流，謝謝大家對服務器之家的支持。
原文鏈接：https://www.cnblogs.com/vveiliang/p/9049393.html
