Ⅰ 布隆過濾器詳解
布隆過濾器 （英語：Bloom Filter）是 1970 年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數。主要用於判斷一個元素是否在一個集合中。
通常我們會遇到很多要判斷一個元素是否在某個集合中的業務場景，一般想到的是將集合中所有元素保存起來，然後通過比較確定。鏈表、樹、散列表（又叫哈希表，Hash table）等等數據結構都是這種思路。但是隨著集合中元素的增加，我們需要的存儲空間也會呈現線性增長，最終達到瓶頸。同時檢索速度也越來越慢，上述三種結構的檢索時間復雜度分別為 ， ， 。
這個時候，布隆過濾器（Bloom Filter）就應運而生。
了解布隆過濾器原理之前，先回顧下 Hash 函數原理。
哈希函數的概念是：將任意大小的輸入數據轉換成特定大小的輸出數據的函數，轉換後的數據稱為哈希值或哈希編碼，也叫散列值。下面是一幅示意圖：
所有散列函數都有如下基本特性：
但是用 hash表存儲大數據量時，空間效率還是很低，當只有一個 hash 函數時，還很容易發生哈希碰撞。
BloomFilter 是由一個固定大小的二進制向量或者點陣圖（bitmap）和一系列映射函數組成的。
在初始狀態時，對於長度為 m 的位數組，它的所有位都被置為0，如下圖所示：
當有變數被加入集合時，通過 K 個映射函數將這個變數映射成點陣圖中的 K 個點，把它們置為 1（假定有兩個變數都通過 3 個映射函數）。
查詢某個變數的時候我們只要看看這些點是不是都是 1 就可以大概率知道集合中有沒有它了
為什麼說是可能存在，而不是一定存在呢？那是因為映射函數本身就是散列函數，散列函數是會有碰撞的。
布隆過濾器的誤判是指多個輸入經過哈希之後在相同的bit位置1了，這樣就無法判斷究竟是哪個輸入產生的，因此誤判的根源在於相同的 bit 位被多次映射且置 1。
這種情況也造成了布隆過濾器的刪除問題，因為布隆過濾器的每一個 bit 並不是獨占的，很有可能多個元素共享了某一位。如果我們直接刪除這一位的話，會影響其他的元素。(比如上圖中的第 3 位)
相比於其它的數據結構，布隆過濾器在空間和時間方面都有巨大的優勢。布隆過濾器存儲空間和插入/查詢時間都是常數 ，另外，散列函數相互之間沒有關系，方便由硬體並行實現。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優勢。
布隆過濾器可以表示全集，其它任何數據結構都不能；
但是布隆過濾器的缺點和優點一樣明顯。誤算率是其中之一。隨著存入的元素數量增加，誤算率隨之增加。但是如果元素數量太少，則使用散列表足矣。
另外，一般情況下不能從布隆過濾器中刪除元素。我們很容易想到把位數組變成整數數組，每插入一個元素相應的計數器加 1, 這樣刪除元素時將計數器減掉就可以了。然而要保證安全地刪除元素並非如此簡單。首先我們必須保證刪除的元素的確在布隆過濾器裡面。這一點單憑這個過濾器是無法保證的。另外計數器回繞也會造成問題。
在降低誤算率方面，有不少工作，使得出現了很多布隆過濾器的變種。
在程序的世界中，布隆過濾器是程序員的一把利器，利用它可以快速地解決項目中一些比較棘手的問題。
如網頁 URL 去重、垃圾郵件識別、大集合中重復元素的判斷和緩存穿透等問題。
布隆過濾器的典型應用有：
知道了布隆過濾去的原理和使用場景，我們可以自己實現一個簡單的布隆過濾器
分布式環境中，布隆過濾器肯定還需要考慮是可以共享的資源，這時候我們會想到 Redis，是的，Redis 也實現了布隆過濾器。
當然我們也可以把布隆過濾器通過 bloomFilter.writeTo() 寫入一個文件，放入OSS、S3這類對象存儲中。
Redis 提供的 bitMap 可以實現布隆過濾器，但是需要自己設計映射函數和一些細節，這和我們自定義沒啥區別。
Redis 官方提供的布隆過濾器到了 Redis 4.0 提供了插件功能之後才正式登場。布隆過濾器作為一個插件載入到 Redis Server 中，給 Redis 提供了強大的布隆去重功能。
在已安裝 Redis 的前提下，安裝 RedisBloom，有兩種方式
直接編譯進行安裝
使用Docker進行安裝
使用
布隆過濾器基本指令：
我們只有這幾個參數，肯定不會有誤判，當元素逐漸增多時，就會有一定的誤判了，這里就不做這個實驗了。
上面使用的布隆過濾器只是默認參數的布隆過濾器，它在我們第一次 add 的時候自動創建。
Redis 還提供了自定義參數的布隆過濾器， bf.reserve 過濾器名 error_rate initial_size
但是這個操作需要在 add 之前顯式創建。如果對應的 key 已經存在，bf.reserve 會報錯
我是一名 Javaer，肯定還要用 Java 來實現的，Java 的 Redis 客戶端比較多，有些還沒有提供指令擴展機制，筆者已知的 Redisson 和 lettuce 是可以使用布隆過濾器的，我們這里用 Redisson
為了解決布隆過濾器不能刪除元素的問題，布穀鳥過濾器橫空出世。論文《Cuckoo Filter：Better Than Bloom》作者將布穀鳥過濾器和布隆過濾器進行了深入的對比。相比布穀鳥過濾器而言布隆過濾器有以下不足：查詢性能弱、空間利用效率低、不支持反向操作（刪除）以及不支持計數。
由於使用較少，暫不深入。
https://www.cs.cmu.e/~dga/papers/cuckoo-conext2014.pdf
http://www.justdojava.com/2019/10/22/bloomfilter/
https://www.cnblogs.com/cpselvis/p/6265825.html
https://juejin.im/post/5cc5aa7ce51d456e431adac5
Ⅱ 什麼是緩存穿透
緩存穿透又稱緩存擊穿,是指在高並發場景下緩存中(包括本地緩存和Redis緩存)的某一個Key被高並發的訪問沒有命中,此時回去資料庫中訪問數據,導致資料庫並發的執行大量查詢操作,對DB造成巨大的壓力。
Ⅲ 如何使用bloomfilter構建大型Java緩存系統
在如今的軟體當中，緩存是解決很多問題的一個關鍵概念。你的應用可能會進行CPU密集型運算。你當然不想讓這些運算一邊又一邊的重復執行，相反，你可以只執行一次， 把這個結果放在內存中作為緩存。有時系統的瓶頸在I/O操作上，比如你不想重復的查詢資料庫，你想把結果緩存起來，只在數據發生變化時才去數據查詢來更新緩存。
與上面的情況類似，有些場合下我們需要進行快速的查找來決定如何處理新來的請求。例如，考慮下面這種情況，你需要確認一個URL是否指向一個惡意網站，這種需求可能會有很多。如果我們把所有惡意網站的URL緩存起來，那麼會佔用很大的空間。或者另一種情況，需要確認用戶輸入的字元串是包含了美國的地名。像「華盛頓的博物館」——在這個字元串中，華盛頓是美國的一個地名。我們應該把美國所有的地名保存在內存中然後再查詢嗎？那樣的話緩存會有多大？是否能在不使用資料庫的前提下來高效地完成？
這就是為什麼我們要跨越基本的數據結構map，在更高級的數據結構像布隆過濾器（bloomfilter）中來尋找答案。你可以把布隆過濾器看做Java中的集合（collection），你可以往它裡面添加元素，查詢某個元素是否存在（就像一個HashSet）。如果布隆過濾器說沒有這個元素，這個結果可能是錯誤的。如果我們在設計布隆過濾器時足夠細心，我們可以把這種出錯的概率控制在可接受范圍內。
解釋
布隆過濾器被設計為一個具有N的元素的位數組A（bit array），初始時所有的位都置為0.
添加元素
要添加一個元素，我們需要提供k個哈希函數。每個函數都能返回一個值，這個值必須能夠作為位數組的索引（可以通過對數組長度進行取模得到）。然後，我們把位數組在這個索引處的值設為1。例如，第一個哈希函數作用於元素I上，返回x。類似的，第二個第三個哈希函數返回y與z，那麼：
A[x]=A[y]=A[z] = 1
查找元素
查找的過程與上面的過程類似，元素將會被會被不同的哈希函數處理三次，每個哈希函數都返回一個作為位數組索引值的整數，然後我們檢測位數組在x、y與z處的值是否為1。如果有一處不為1，那麼就說明這個元素沒有被添加到這個布隆過濾器中。如果都為1，就說明這個元素在布隆過濾器裡面。當然，會有一定誤判的概率。
演算法優化
通過上面的解釋我們可以知道，如果想設計出一個好的布隆過濾器，我們必須遵循以下准則：
好的哈希函數能夠盡可能的返回寬范圍的哈希值。
位數組的大小（用m表示）非常重要：如果太小，那麼所有的位很快就都會被賦值為1，這樣就增加了誤判的幾率。
哈希函數的個數（用k表示）對索引值的均勻分配也很重要。
計算m的公式如下：
m = - nlog p / (log2)^2;
這里p為可接受的誤判率。
計算k的公式如下：
k = m/n log(2) ;
這里k=哈希函數個數，m=位數組個數，n=待檢測元素的個數（後面會用到這幾個字母）。
哈希演算法
哈希演算法是影響布隆過濾器性能的地方。我們需要選擇一個效率高但不耗時的哈希函數，在論文《更少的哈希函數，相同的性能指標：構造一個更好的布隆過濾器》中，討論了如何選用2個哈希函數來模擬k個哈希函數。首先，我們需要計算兩個哈希函數h1(x)與h2(x)。然後，我們可以用這兩個哈希函數來模仿產生k個哈希函數的效果：
gi(x) = h1(x) + ih2(x);
這里i的取值范圍是1到k的整數。
Google guava類庫使用這個技巧實現了一個布隆過濾器，哈希演算法的主要邏輯如下：
long hash64 = …; //calculate a 64 bit hash function
//split it in two halves of 32 bit hash values
int hash1 = (int) hash64;
int hash2 = (int) (hash64 >>> 32);
//Generate k different hash functions with a simple loop
for (int i = 1; i <= numHashFunctions; i++) {
int nextHash = hash1 + i * hash2;
}
應用
從數學公式中，我們可以很明顯的知道使用布隆過濾器來解決問題。但是，我們需要很好地理解布隆過濾器所能解決問題的領域。像我們可以使用布隆過濾器來存放美國的所有城市，因為城市的數量是可以大概確定的，所以我們可以確定n（待檢測元素的個數）的值。根據需求來修改p（誤判概率）的值，在這種情況下，我們能夠設計出一個查詢耗時少，內存使用率高的緩存機制。
實現
Google Guava類庫有一個實現，查看這個類的構造函數，在這裡面需要設置待檢測元素的個數與誤判率。
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
//Create Bloomfilter
int expectedInsertions = ….;
double fpp = 0.03; // desired false positive probability
BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("UTF-8")), expectedInsertions,fpp)
Ⅳ 如何保證緩存與資料庫雙寫時的數據一致性
一般來說，就是如果系統不是嚴格要求緩存+資料庫必須一致性的話，緩存可以稍微的跟資料庫偶爾有不一致的情況，最好不要做這個方案，讀請求和寫請求串列化，串到一個內存隊列里去，這樣就可以保證一定不會出現不一致的情況
串列化之後，就會導致系統的吞吐量會大幅度的降低，用比正常情況下多幾倍的機器去支撐線上的一個請求。
Ⅳ 布隆過濾器
[TOC]
通過解決方案：
Java中如將數據存儲在內存中，最簡單的演算法結構是HashMap。通過HashMap判斷key是否存在，來判斷數據是否存在。通過hash演算法查找元素，時間復雜度基本是 O(1) （可能存在hash沖突後轉換成鏈表或紅黑樹的情況，時間復雜度的影響可以忽略）。
使用HashMap速度很快，存儲簡單，絕大部分場景可以使用。但是HashMap 佔用的空間比較大 ：
為什麼出現布隆過濾器：
舉例：
如1000萬個Integer存儲在內存中，佔用空間為：4x32x10000000位，即1220兆。如布隆過濾器通過4位元組存儲（布隆過濾器通過多次hash對數據計算後-->幾次hash根據數據量指定，得到多個數據， 佔用多個位 ），則佔用空間為610M。比原有空間少一半。
個人覺得，此比較在字元等的比較中尤為有效。
一個字元串多個字元，根據編碼方式，一個字元兩個或三個位元組，如10個字元，字元串存儲佔用20個位元組，還有相關字元串相關的類信息的內存佔用。
位存儲，根據數據量的大小，hash的位數，靈活計算。如4個位元組，則是原hashMap佔用空間的五分之一。
（1）定義位元組向量
先定義一個指定長度的位元組數組（位元組數組，數組內每個元素的值）。
如長度為8（一個位元組大小），默認所有元素值均為0，如下：
（2）計算哈希值
將要寫入過濾器的數據，根據一定數量的哈希函數，得到多個哈希值，再依次判斷每個哈希值對應的索引。
如使用3個哈希函數，計算得到3個哈希值，判定哈希值對應的位元組向量為為1，3，7。
（3）更新位元組向量
將計算出的位元組向量的索引， 對應的位元組向量中的元素值更高為1 （無論之前為0或者為1，均更改為1）。如下：
（1）計算哈希值
將要判斷過濾器中是否存在的數據，根據一定數量的哈希函數，得到多個哈希值，再依次判斷每個哈希值對應的索引。
如使用3個哈希函數，計算得到3個哈希值，判定哈希值對應的位元組向量為為1，3，7。
注意：哈希函數的判斷方式和計算索引的方式，需和寫入數據時完全一致。
（2）判斷是否存在
如原位元組數組中，對應1，3，7中存在的元素的值都為1。則判定為此元素 可能存在 ，但凡有一個元素的值不為1，則判定此元素 一定不存在 。
布隆過濾器，主要需實現的目標是， 在指定的數據個數范圍內，滿足誤判率在設定的范圍內 ，誤判率太高的話，無法起到過濾數據的情況，誤判率不能為0。
因此需要計算兩個數據來滿足 存儲數據的個數 和 誤判率 ：
使用布隆過濾器的決定性因素之一，就是此演算法插入數據和查詢數據的速度必須非常快。因此在對數據進行哈希運算的時候， 需選擇計算快的哈希演算法 。
而且， 寫入數據以及查詢數據的哈希演算法，順序和演算法都需完全一致 。
待完善。。。。。
可以通過google的 guava ，在內存中輕松實現布隆過濾器。
無需手動計算滿足位元組數組的長度和哈希個數，只需要輸入 擬輸入數據的個數 和 期望誤判率 即可。
不輸入期望誤判率的情況下，誤判率為0.03，即100個非范圍內的數據進行校驗時，約三個數據會判定為存在。
多次執行，結果一致，根據結果判定：
內存的存儲存在局限性，可以使用redis中的bitMap來實現位元組數組的存儲。
使用redis實現布隆過濾器。需要根據公式，手動計算位元組數組的長度和哈希的個數。
實現過程，待完善。。。。。。
Ⅵ 緩存穿透有哪些解決辦法
最基本的就是首先做好參數校驗，一些不合法的參數請求直接拋出異常信息返回給客戶端。比如查詢的資料庫 id 不能小於 0、傳入的郵箱格式不對的時候直接返回錯誤消息給客戶端等等。
1）緩存無效 key : 如果緩存和資料庫都查不到某個 key 的數據就寫一個到 redis 中去並設置過期時間，具體命令如下：SET key value EX 10086。這種方式可以解決請求的 key 變化不頻繁的情況，如何黑客惡意攻擊，每次構建的不同的請求key，會導致 redis 中緩存大量無效的 key 。很明顯，這種方案並不能從根本上解決此問題。如果非要用這種方式來解決穿透問題的話，盡量將無效的 key 的過期時間設置短一點比如 1 分鍾。另外，一般情況下我們是這樣設計 key 的： 表名:列名:主鍵名:主鍵值。
2）布隆過濾器：布隆過濾器是一個非常神奇的數據結構，通過它我們可以非常方便地判斷一個給定數據是否存在與海量數據中。我們需要的就是判斷 key 是否合法，有沒有感覺布隆過濾器就是我們想要找的那個「人」。具體是這樣做的：把所有可能存在的請求的值都存放在布隆過濾器中，當用戶請求過來，我會先判斷用戶發來的請求的值是否存在於布隆過濾器中。不存在的話，直接返回請求參數錯誤信息給客戶端，存在的話才會走下面的流程。總結一下就是下面這張圖(這張圖片不是我畫的，為了省事直接在網上找的)：
Ⅶ Java通過id訪問方法,不讓id重復訪問怎麼實現
就是一個id只能訪問一次嗎？
1，在調用方法前要有控制
2，判定id是否訪問過
比較簡單的，比如訪問過的id存起來，調用前查一下看看是不是已經有了，有了不允許訪問
然後說點逼格高的，
1，用資料庫保存已經訪問的id，但是資料庫會慢一點
2，用緩存保存先過濾一下，不過會越來越大。id不長還是能存很多很多很多的，如果緩存失效再向庫里查，萬無一失
3，布隆過濾器特別適合你這個，每次id訪問過來就加到過濾器裡面，後面直接先用布隆過濾器過濾下，性能特別高，誤判再往後面緩存資料庫走就行
Ⅷ 緩存穿透的意義
最基本的就是首先做好參數校驗，一些不合法的參數請求直接拋出異常信息返回給客戶端。比如查詢的資料庫 id 不能小於 0、傳入的郵箱格式不對的時候直接返回錯誤消息給客戶端等等。
1）緩存無效 key : 如果緩存和資料庫都查不到某個 key 的數據就寫一個到 redis 中去並設置過期時間，具體命令如下：SET key value EX 10086。這種方式可以解決請求的 key 變化不頻繁的情況，如何黑客惡意攻擊，每次構建的不同的請求key，會導致 redis 中緩存大量無效的 key 。很明顯，這種方案並不能從根本上解決此問題。如果非要用這種方式來解決穿透問題的話，盡量將無效的 key 的過期時間設置短一點比如 1 分鍾。另外，一般情況下我們是這樣設計 key 的： 表名:列名:主鍵名:主鍵值。
2）布隆過濾器：布隆過濾器是一個非常神奇的數據結構，通過它我們可以非常方便地判斷一個給定數據是否存在與海量數據中。我們需要的就是判斷 key 是否合法，有沒有感覺布隆過濾器就是我們想要找的那個「人」。具體是這樣做的：把所有可能存在的請求的值都存放在布隆過濾器中，當用戶請求過來，我會先判斷用戶發來的請求的值是否存在於布隆過濾器中。不存在的話，直接返回請求參數錯誤信息給客戶端，存在的話才會走下面的流程。
Ⅸ 如何搭建億級並發的系統架構
想設計億萬級高並發架構，你要先知道高並發是什麼？
面對流量高峰，不同的企業是如何通過技術手段解決高並發難題的呢?
0、引言
軟體系統有三個追求：高性能、高並發、高可用，俗稱三高。三者既有區別也有聯系，門門道道很多，全面討論需要三天三夜，本篇討論高並發。
高並發（High Concurrency）。並發是操作系統領域的一個概念，指的是一段時間內多任務流交替執行的現象，後來這個概念被泛化，高並發用來指大流量、高請求的業務情景，比如春運搶票，電商雙十一，秒殺大促等場景。
很多程序員每天忙著搬磚，平時接觸不到高並發，哪天受不了跑去面試，還常常會被面試官犀利的高並發問題直接KO，其實吧，高並發系統也不高深，我保證任何一個智商在線的看過這篇文章後，都能戰勝恐懼，重拾生活的信心。
本文先介紹高並發系統的度量指標，然後講述高並發系統的設計思路，再梳理高並發的關鍵技術，最後結合作者的經驗做一些延伸探討。
1、高並發的度量指標
既然是高並發系統，那並發一定要高，不然就名不副實。並發的指標一般有QPS、TPS、IOPS，這幾個指標都是可歸為系統吞吐率，QPS越高系統能hold住的請求數越多，但光關注這幾個指標不夠，我們還需要關注RT，即響應時間，也就是從發出request到收到response的時延，這個指標跟吞吐往往是此消彼長的，我們追求的是一定時延下的高吞吐。
比如有100萬次請求，99萬次請求都在10毫秒內響應，其他次數10秒才響應，平均時延不高，但時延高的用戶受不了，所以，就有了TP90/TP99指標，這個指標不是求平均，而是把時延從小到大排序，取排名90%/99%的時延，這個指標越大，對慢請求越敏感。
除此之外，有時候，我們也會關注可用性指標，這可歸到穩定性。
一般而言，用戶感知友好的高並發系統，時延應該控制在250毫秒以內。
什麼樣的系統才能稱為高並發？這個不好回答，因為它取決於系統或者業務的類型。不過我可以告訴你一些眾所周知的指標，這樣能幫助你下次在跟人扯淡的時候稍微靠點兒譜，不至於貽笑大方。
通常，資料庫單機每秒也就能抗住幾千這個量級，而做邏輯處理的服務單台每秒抗幾萬、甚至幾十萬都有可能，而消息隊列等中間件單機每秒處理個幾萬沒問題，所以我們經常聽到每秒處理數百萬、數千萬的消息中間件集群，而像阿某的API網關，每日百億請求也有可能。
2、高並發的設計思路
高並發的設計思路有兩個方向：
垂直方向擴展，也叫豎向擴展
水平方向擴展，也叫橫向擴展
硬體方向，很好理解，花錢升級機器，更多核更高主頻更大存儲空間更多帶寬
軟體方向，包括用各快的數據結構，改進架構，應用多線程、協程，以及上性能優化各種手段，但這玩意兒天花板低，就像提升個人產出一樣，996、007、最多24 X 7。
DNS負載均衡，客戶端通過URL發起網路服務請求的時候，會去DNS伺服器做域名解釋，DNS會按一定的策略（比如就近策略）把URL轉換成IP地址，同一個URL會被解釋成不同的IP地址，這便是DNS負載均衡，它是一種粗粒度的負載均衡，它只用URL前半部分，因為DNS負載均衡一般採用就近原則，所以通常能降低時延，但DNS有cache，所以也會更新不及時的問題。
硬體負載均衡，通過布置特殊的負載均衡設備到機房做負載均衡，比如F5，這種設備貴，性能高，可以支撐每秒百萬並發，還能做一些安全防護，比如防火牆。
軟體負載均衡，根據工作在ISO 7層網路模型的層次，可分為四層負載均衡（比如章文嵩博士的LVS）和七層負載均衡（NGINX），軟體負載均衡配置靈活，擴展性強，阿某雲的SLB作為服務對外售賣，Nginx可以對URL的後半部做解釋承擔API網關的職責。
一致性問題：(a)更新db成功+更新cache失敗 -> 不一致 (b)更新db失敗+更新cache成功 -> 不一致 ©更新db成功+淘汰緩存失敗 -> 不一致
緩存穿透：查詢一定不存在的數據，會穿透緩存直接壓到資料庫，從而導致緩存失去作用，如果有人利用這個漏洞，大量查詢一定不存在的數據，會對資料庫造成壓力，甚至打掛資料庫。解決方案：布隆過濾器 或者 簡單的方案，查詢不存在的key，也把空結果寫入緩存（設置較短的過期淘汰時間），從而降低命失
緩存雪崩：如果大量緩存在一個時刻同時失效，則請求會轉到DB，則對DB形成壓迫，導致雪崩。簡單的解決方案是為緩存失效時間添加隨機值，降低同一時間點失效淘汰緩存數，避免集體失效事件發生
計數器演算法（固定窗口）：計數器演算法是使用計數器在周期內累加訪問次數，當達到設定的限流值時，觸發限流策略，下一個周期開始時，進行清零，重新計數，實現簡單。計數器演算法方式限流對於周期比較長的限流，存在很大的弊端，有嚴重的臨界問題。
滑動窗口演算法：將時間周期分為N個小周期，分別記錄每個小周期內訪問次數，並且根據時間滑動刪除過期的小周期，當滑動窗口的格子劃分的越多，那麼滑動窗口的滾動就越平滑，限流的統計就會越精確。此演算法可以很好的解決固定窗口演算法的臨界問題。
漏桶演算法：訪問請求到達時直接放入漏桶，如當前容量已達到上限（限流值），則進行丟棄（觸發限流策略）。漏桶以固定的速率進行釋放訪問請求（即請求通過），直到漏桶為空。分布式環境下實施難度高。
令牌桶演算法：程序以r（r=時間周期/限流值）的速度向令牌桶中增加令牌，直到令牌桶滿，請求到達時向令牌桶請求令牌，如獲取到令牌則通過請求，否則觸發限流策略。分布式環境下實施難度高。
垂直方向：提升單機能力
提升單機處理能力又可分為硬體和軟體兩個方面：
水平方向：分布式集群
為了解決分布式系統的復雜性問題，一般會用到架構分層和服務拆分，通過分層做隔離，通過微服務解耦。
這個理論上沒有上限，只要做好層次和服務劃分，加機器擴容就能滿足需求，但實際上並非如此，一方面分布式會增加系統復雜性，另一方面集群規模上去之後，也會引入一堆AIOps、服務發現、服務治理的新問題。
因為垂直向的限制，所以，我們通常更關注水平擴展，高並發系統的實施也主要圍繞水平方向展開。
3、高並發的關鍵技術
玩具式的網路服務程序，用戶可以直連伺服器，甚至不需要資料庫，直接寫磁碟文件。但春運購票系統顯然不能這么做，它肯定扛不住這個壓力，那一般的高並發系統是怎麼做呢？比如某寶這樣的正經系統是怎麼處理高並發的呢？
其實大的思路都差不多，層次劃分 + 功能劃分。可以把層次劃分理解為水平方向的劃分，而功能劃分理解為垂直方向的劃分。
首先，用戶不能直連伺服器，要做分布式就要解決「分」的問題，有多個服務實例就需要做負載均衡，有不同服務類型就需要服務發現。
集群化：負載均衡
負載均衡就是把負載（request）均衡分配到不同的服務實例，利用集群的能力去對抗高並發，負載均衡是服務集群化的實施要素，它分3種：
所以，完整的負載均衡鏈路是 client <-> DNS負載均衡 -> F5 -> LVS/SLB -> NGINX
不管選擇哪種LB策略，或者組合LB策略，邏輯上，我們都可以視為負載均衡層，通過添加負載均衡層，我們將負載均勻分散到了後面的服務集群，具備基礎的高並發能力，但這只是萬里長征第一步。
資料庫層面：分庫分表+讀寫分離
前面通過負載均衡解決了無狀態服務的水平擴展問題，但我們的系統不全是無狀態的，後面通常還有有狀態的資料庫，所以解決了前面的問題，存儲有可能成為系統的瓶頸，我們需要對有狀態存儲做分片路由。
資料庫的單機QPS一般不高，也就幾千，顯然滿足不了高並發的要求。
所以，我們需要做分庫分表 + 讀寫分離。
就是把一個庫分成多個庫，部署在多個資料庫服務上，主庫承載寫請求，從庫承載讀請求。從庫可以掛載多個，因為很多場景寫的請求遠少於讀的請求，這樣就把對單個庫的壓力降下來了。
如果寫的請求上升就繼續分庫分表，如果讀的請求上升就掛更多的從庫，但資料庫天生不是很適合高並發，而且資料庫對機器配置的要求一般很高，導致單位服務成本高，所以，這樣加機器抗壓力成本太高，還得另外想招。
讀多寫少：緩存
緩存的理論依據是局部性原理。
一般系統的寫入請求遠少於讀請求，針對寫少讀多的場景，很適合引入緩存集群。
在寫資料庫的時候同時寫一份數據到緩存集群里，然後用緩存集群來承載大部分的讀請求，因為緩存集群很容易做到高性能，所以，這樣的話，通過緩存集群，就可以用更少的機器資源承載更高的並發。
緩存的命中率一般能做到很高，而且速度很快，處理能力也強（單機很容易做到幾萬並發），是理想的解決方案。
CDN本質上就是緩存，被用戶大量訪問的靜態資源緩存在CDN中是目前的通用做法。
緩存也有很多需要謹慎處理的問題：
但緩存是針對讀，如果寫的壓力很大，怎麼辦？
高寫入：消息中間件
同理，通過跟主庫加機器，耗費的機器資源是很大的，這個就是資料庫系統的特點所決定的。
相同的資源下，資料庫系統太重太復雜，所以並發承載能力就在幾千/s的量級，所以此時你需要引入別的一些技術。
比如說消息中間件技術，也就是MQ集群，它是非常好的做寫請求非同步化處理，實現削峰填谷的效果。
消息隊列能做解耦，在只需要最終一致性的場景下，很適合用來配合做流控。
假如說，每秒是1萬次寫請求，其中比如5千次請求是必須請求過來立馬寫入資料庫中的，但是另外5千次寫請求是可以允許非同步化等待個幾十秒，甚至幾分鍾後才落入資料庫內的。
那麼此時完全可以引入消息中間件集群，把允許非同步化的每秒5千次請求寫入MQ，然後基於MQ做一個削峰填谷。比如就以平穩的1000/s的速度消費出來然後落入資料庫中即可，此時就會大幅度降低資料庫的寫入壓力。
業界有很多著名的消息中間件，比如ZeroMQ，rabbitMQ，kafka等。
消息隊列本身也跟緩存系統一樣，可以用很少的資源支撐很高的並發請求，用它來支撐部分允許非同步化的高並發寫入是很合適的，比使用資料庫直接支撐那部分高並發請求要減少很多的機器使用量。
避免擠兌：流控
再強大的系統，也怕流量短事件內集中爆發，就像銀行怕擠兌一樣，所以，高並發另一個必不可少的模塊就是流控。
流控的關鍵是流控演算法，有4種常見的流控演算法。
4、高並發的實踐經驗
接入-邏輯-存儲是經典的互聯網後端分層，但隨著業務規模的提高，邏輯層的復雜度也上升了，所以，針對邏輯層的架構設計也出現很多新的技術和思路，常見的做法包括系統拆分，微服務。
除此之外，也有很多業界的優秀實踐，包括某信伺服器通過協程（無侵入，已開源libco）改造，極大的提高了系統的並發度和穩定性，另外，緩存預熱，預計算，批量讀寫（減少IO），池技術等也廣泛應用在實踐中，有效的提升了系統並發能力。
為了提升並發能力，邏輯後端對請求的處理，一般會用到生產者-消費者多線程模型，即I/O線程負責網路IO，協議編解碼，網路位元組流被解碼後產生的協議對象，會被包裝成task投入到task queue，然後worker線程會從該隊列取出task執行，有些系統會用多進程而非多線程，通過共享存儲，維護2個方向的shm queue，一個input q，一個output q，為了提高並發度，有時候會引入協程，協程是用戶線程態的多執行流，它的切換成本更低，通常有更好的調度效率。
另外，構建漏斗型業務或者系統，從客戶端請求到接入層，到邏輯層，到DB層，層層遞減，過濾掉請求，Fail Fast（盡早發現盡早過濾），嘴大屁眼小，哈哈。
漏斗型系統不僅僅是一個技術模型，它也可以是一個產品思維，配合產品的用戶分流，邏輯分離，可以構建全方位的立體模型。
5、小結
莫讓浮雲遮望眼，除去繁華識真顏。我們不能掌握了大方案，吹完了牛皮，而忽視了編程最本質的東西，掌握最基本最核心的編程能力，比如數據架構和演算法，設計，慣用法，培養技術的審美，也是很重要的，既要致高遠，又要盡精微。