一、問題起因
前幾天在面試的時候，因為我以前有個B2B訂貨平臺（saas系統(tǒng)架構，平臺給每個租戶，提供完全獨立的在線商城服務，而所有的商城實際上還是在同一個系統(tǒng)中）的項目經(jīng)驗，所以面試官問到了這個問題，當某個租戶的流量特別大，怎么保證其他租戶的訪問不受限制？
二、一般系統(tǒng)常見的限流方案
1.限制并發(fā)數(shù)
假設系統(tǒng)瞬時可接受的并發(fā)數(shù)為1000，那么每來一個請求將該數(shù)值減1，請求執(zhí)行完成后將該數(shù)值加1，當該數(shù)值小于等于0時拒絕訪問。該方法實現(xiàn)非常簡單粗暴，java應用中可以通過java.util.corrurnent包下的Semaphore信號量的tryAcquire和release操作來實現(xiàn)。
該方法其實常見于一些長連接的限制上，比如db連接。對于執(zhí)行時間較短，波動較大的請求，并不能很公平的限制流量，因為每個請求執(zhí)行時間不一樣，甚至不同系統(tǒng)負載下的同一個請求執(zhí)行時間也不一樣，如果都只獲取一個并發(fā)數(shù)并不是一個很優(yōu)的方案。（這個也是我當時面試的時候給面試官的方案，給每個租戶一個固定并發(fā)數(shù)來限制，現(xiàn)在想來其實還有些欠妥）
2.漏桶（Leaky Bucket）算法
初始一個定長的漏桶，將請求任務放到漏桶中，以固定的流出速率去執(zhí)行請求，如果桶滿了就丟棄。實現(xiàn)方式，事先準備一個定長隊列，存放請求任務，準備一個任務執(zhí)行線程池固定時間間隔取任務來執(zhí)行即可，隊列滿了就丟棄。
該方法類似于一些消息隊列如rocketmq和kafka的消息消費方式（consumer定速率的從broker上pull消息），這種方法嚴格限制了系統(tǒng)的執(zhí)行速率，起到限流的作用，但對于一些可接受范圍內突發(fā)的大流量請求也會被限制，導致部分請求延遲過大。
3.令牌桶（Token Bucket）算法
初始一個定長的桶，以固定的速率往桶內放令牌，溢出的令牌丟棄，每個請求可以獲得任意個數(shù)令牌，如果取到了足夠令牌就可以繼續(xù)執(zhí)行，如果取不到就拒絕該請求。Google的Guava包中的RateLimiter即是以該算法實現(xiàn)，實現(xiàn)比較簡單，有興趣的小伙伴可以自己去研究源碼。
該方法算是第一種限制并發(fā)數(shù)的改進版，取得令牌數(shù)是可以動態(tài)改變的，釋放令牌的數(shù)量也不會受限于每個請求的執(zhí)行時間，而且可以應對可接受范圍內的突發(fā)流量，應該也是目前最常用的方式。
三、針對多租戶系統(tǒng)的限流方案（僅個人想法）
1.事先分配
事先為每個租戶分配獨立的限制量，當然可以簡單的平均分配，也可以根據(jù)租戶事先定制的值分配。這種方法應該是最容易想到，根據(jù)總的租戶個數(shù)平均分配限制量后，再通過對多租戶的身份識別分別做流量控制，前面提到的三種算法應該都比較容易通過改進來實現(xiàn)。
缺點：不夠靈活，不活躍的租戶的量其實是可以暫時分配或者是部分分配給其他租戶的。
2.私有+公有令牌桶
①基于令牌桶算法的改進，每個租戶都有一個私有的令牌桶，所有租戶有個公有的令牌桶，租戶先從公有令牌桶取令牌，取不到再去私有令牌桶取，每個租戶有各自獨立的放令牌速率，先放到私有桶中，溢出的部分再放到公有桶中，公有桶溢出后就丟棄。這種方式可以保證每個租戶都有一個可以得到保障的最低流量，而且還可以將系統(tǒng)資源得到充分的利用。但是這種方案使用時卻并不那么美好，因為放令牌操作要遍歷每個私有桶，他的時間復雜度是O(n)，相比較原來O(1)的時間復雜度，尤其在海量租戶的情況下，嚴重影響系統(tǒng)效率。
偽代碼：
long timeStamp=getNowTime();
int publicCapacity; // 公有桶的容量
int privateCapacity; //私有桶的容量
Map rateMap ; //每個租戶令牌放入速度
int publicTokens; //公有桶的當前水量
Map privateTokensMap; //私有桶的當前水量
bool grant(int tenantId, int grantTokens){ //取令牌方法
//先執(zhí)行添加令牌的操作
putTokens();
//先從公有桶取，再從私有桶取
int privateTokens = privateTokensMap.get(tenantId);
if(privateTokens+publicTokens >= grantTokens){
int tokensDel = publicTokens - grantTokens;
if(tokensDel >= 0){
//完全從公有桶取
publicTokens = tokensDel
}else{
//共有桶不夠，從私有桶補足
publicTokens = 0;
privateTokensMap.put(tenantId,privateTokens+tokensDel);
}
return true;
}else{
//令牌不夠，拒絕請求
retun false;
}
}
void putTokens(){
long now = getNowTime();
long timeDelta = now - timeStamp;
timeStamp = now;
for(Map.Entry rateEntry : rateMap){//遍歷每個桶，將令牌放入，私有桶溢出的令牌放到公有桶，公有桶溢出的丟棄
int tenantId = rateEntry.getKey();
int rate = rateEntry.getValue();
int privateTokens = privateTokensMap.get(tenantId);
int tokensDelta = timeDelta*rate;
if(privateTokens + tokenDelta > privateCapacity){
rateEntry.setValue(privateCapacity);
publicTokens = min(publicCapacity, publicTokens+(privateTokens + tokenDelta - privateCapacity));
}else{
rateEntry.setValue(privateTokens + tokenDelta);
}
}
}
②在上一種方案的基礎下，公有桶也作為一個獨立的令牌桶使用，公有桶的令牌流入速率與私有桶不同，每個租戶先從公有桶嘗試獲取，獲取不到的情況下，再從私有桶獲取，但是每個桶（包括公有桶）的速率總和還是要小于等于系統(tǒng)可接受的最大流量。這樣的時間復雜度依然是常數(shù)級別的，也可以提高部分閑置資源的使用率。借助現(xiàn)有的限流工具也很容易實現(xiàn)。
偽代碼：
Map<RateLimiter> privateRateLimiterMap; //租戶的私有令牌桶，RateLimiter是普通的令牌桶實現(xiàn)，例如：Guava包里的令牌桶RateLimiter
RateLimiter publicRateLimiter; //公有的令牌桶
void init(Map privateRateMap, int publicRate){ //初始化令牌桶
publicRateLimiter = RateLimiter.create(publicRate);
privateRateLimiterMap = new HashMap<>();
for(Map.Entry rateEntry : privateRateMap){
RateLimiter privateRateLimiter = RateLimiter.create(rateEntry.getValue());
privateRateLimiterMap.put(rateEntry.getKey(), privateRateLimiter);
}
}
bool grant(int tenantId, int grantTokens){ //取令牌方法
if(publicRateLimiter.tryAcquire(grantTokens))
return true;
else
return privateRateLimiterMap.get(tenantId).tryAcquire(grantTokens);
}
歡迎來我的個人博客逛逛: https://blog.52xtg.com
