一、問題起因
前幾天在面試的時候，因為我以前有個B2B訂貨平臺（saas系統(tǒng)架構(gòu)环鲤，平臺給每個租戶，提供完全獨立的在線商城服務(wù)憎兽，而所有的商城實際上還是在同一個系統(tǒng)中）的項目經(jīng)驗冷离，所以面試官問到了這個問題结闸，當(dāng)某個租戶的流量特別大，怎么保證其他租戶的訪問不受限制酒朵？
二桦锄、一般系統(tǒng)常見的限流方案
1.限制并發(fā)數(shù)
假設(shè)系統(tǒng)瞬時可接受的并發(fā)數(shù)為1000，那么每來一個請求將該數(shù)值減1蔫耽，請求執(zhí)行完成后將該數(shù)值加1结耀，當(dāng)該數(shù)值小于等于0時拒絕訪問。該方法實現(xiàn)非常簡單粗暴匙铡，java應(yīng)用中可以通過java.util.corrurnent包下的Semaphore信號量的tryAcquire和release操作來實現(xiàn)图甜。
該方法其實常見于一些長連接的限制上，比如db連接鳖眼。對于執(zhí)行時間較短黑毅，波動較大的請求，并不能很公平的限制流量钦讳，因為每個請求執(zhí)行時間不一樣矿瘦，甚至不同系統(tǒng)負(fù)載下的同一個請求執(zhí)行時間也不一樣，如果都只獲取一個并發(fā)數(shù)并不是一個很優(yōu)的方案愿卒。（這個也是我當(dāng)時面試的時候給面試官的方案缚去，給每個租戶一個固定并發(fā)數(shù)來限制，現(xiàn)在想來其實還有些欠妥）
2.漏桶（Leaky Bucket）算法
初始一個定長的漏桶琼开，將請求任務(wù)放到漏桶中易结，以固定的流出速率去執(zhí)行請求，如果桶滿了就丟棄柜候。實現(xiàn)方式搞动，事先準(zhǔn)備一個定長隊列，存放請求任務(wù)渣刷，準(zhǔn)備一個任務(wù)執(zhí)行線程池固定時間間隔取任務(wù)來執(zhí)行即可鹦肿，隊列滿了就丟棄。
該方法類似于一些消息隊列如rocketmq和kafka的消息消費方式（consumer定速率的從broker上pull消息）飞主，這種方法嚴(yán)格限制了系統(tǒng)的執(zhí)行速率狮惜，起到限流的作用高诺，但對于一些可接受范圍內(nèi)突發(fā)的大流量請求也會被限制碌识，導(dǎo)致部分請求延遲過大。
3.令牌桶（Token Bucket）算法
初始一個定長的桶虱而，以固定的速率往桶內(nèi)放令牌筏餐，溢出的令牌丟棄，每個請求可以獲得任意個數(shù)令牌牡拇，如果取到了足夠令牌就可以繼續(xù)執(zhí)行魁瞪，如果取不到就拒絕該請求穆律。Google的Guava包中的RateLimiter即是以該算法實現(xiàn)，實現(xiàn)比較簡單导俘，有興趣的小伙伴可以自己去研究源碼峦耘。
該方法算是第一種限制并發(fā)數(shù)的改進(jìn)版，取得令牌數(shù)是可以動態(tài)改變的旅薄，釋放令牌的數(shù)量也不會受限于每個請求的執(zhí)行時間辅髓，而且可以應(yīng)對可接受范圍內(nèi)的突發(fā)流量，應(yīng)該也是目前最常用的方式少梁。
三洛口、針對多租戶系統(tǒng)的限流方案（僅個人想法）
1.事先分配
事先為每個租戶分配獨立的限制量，當(dāng)然可以簡單的平均分配凯沪，也可以根據(jù)租戶事先定制的值分配第焰。這種方法應(yīng)該是最容易想到，根據(jù)總的租戶個數(shù)平均分配限制量后妨马，再通過對多租戶的身份識別分別做流量控制挺举，前面提到的三種算法應(yīng)該都比較容易通過改進(jìn)來實現(xiàn)。
缺點：不夠靈活烘跺，不活躍的租戶的量其實是可以暫時分配或者是部分分配給其他租戶的豹悬。
2.私有+公有令牌桶
①基于令牌桶算法的改進(jìn)，每個租戶都有一個私有的令牌桶液荸，所有租戶有個公有的令牌桶瞻佛，租戶先從公有令牌桶取令牌，取不到再去私有令牌桶取娇钱，每個租戶有各自獨立的放令牌速率伤柄，先放到私有桶中，溢出的部分再放到公有桶中文搂，公有桶溢出后就丟棄适刀。這種方式可以保證每個租戶都有一個可以得到保障的最低流量，而且還可以將系統(tǒng)資源得到充分的利用煤蹭。但是這種方案使用時卻并不那么美好笔喉，因為放令牌操作要遍歷每個私有桶，他的時間復(fù)雜度是O(n)硝皂，相比較原來O(1)的時間復(fù)雜度常挚，尤其在海量租戶的情況下，嚴(yán)重影響系統(tǒng)效率稽物。
偽代碼：
long timeStamp=getNowTime();
int publicCapacity; // 公有桶的容量
int privateCapacity; //私有桶的容量
Map rateMap ; //每個租戶令牌放入速度
int publicTokens; //公有桶的當(dāng)前水量
Map privateTokensMap; //私有桶的當(dāng)前水量
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{
//共有桶不夠，從私有桶補(bǔ)足
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);
}
}
}
②在上一種方案的基礎(chǔ)下盗忱，公有桶也作為一個獨立的令牌桶使用酱床，公有桶的令牌流入速率與私有桶不同，每個租戶先從公有桶嘗試獲取趟佃，獲取不到的情況下斤葱，再從私有桶獲取，但是每個桶（包括公有桶）的速率總和還是要小于等于系統(tǒng)可接受的最大流量揖闸。這樣的時間復(fù)雜度依然是常數(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
