Algorithm

128. 最長連續(xù)序列

func longestConsecutive(nums []int) (result int) {
    numMap := make(map[int]bool, 0)
    for _, v := range nums {
        numMap[v] = true
    }
    result = 0
    for k, _ := range numMap {
        currentNum := k
        currentResult := 1
        if _, ok := numMap[k-1]; !ok {
            for {
                _, ok := numMap[currentNum+1]
                if ok {
                    currentNum += 1
                    currentResult += 1
                } else {
                    break
                }
            }
            if currentResult > result {
                result = currentResult
            }
        }
    }
    return
}

Review

Common Problems in Message Queues [With Solutions]
文章講述了使用MQ可能遇到的問題，以及給出對應的一些解決方案张吉。

1. 解決不可用/壞消息：使用死信隊列來存儲無法處理的壞消息，并且在需要/消費者解決問題的時候再從死信隊列中將消息重新發(fā)送。
2. 怎么避免消息丟失：

• 通過消費者消費成功回復ACK的方式浑侥，來避免消息端消息丟失。
• MQ服務端實現(xiàn)消息可持久化來避免異常情況下服務端消息丟失勤揩。
• MQ服務端實例之間消息復制來避免其中一個服務實例掛死之后的消息丟失乓梨。
• 通過編碼將消息發(fā)送鳖轰、消費作為一個事務，來徹底解決消息丟失問題扶镀。

3. 消息有序性保障：
   • 每個消息里面帶上時間戳蕴侣，消費端識別時間戳來實現(xiàn)有序消費。

• 每個消息里面帶上序列號臭觉。
• 使用自帶offset的MQ中間件（比如kafka）

TIP

并查集從入門到出門

Share

學習mysql 45講

24 | MySQL是怎么保證主備一致的昆雀？

MySQL主備的基本原理

備庫B跟主庫A之間維持了一個長連接。 主庫A內(nèi)部有一個線程蝠筑， 專門用于服務備庫B的這個長連接狞膘。一個事務日志同步的完整過程是這樣的：

1. 在備庫B上通過change master命令， 設置主庫A的IP什乙、 端口挽封、 用戶名、 密碼臣镣， 以及要從哪個位置開始請求binlog辅愿， 這個位置包含文件名和日志偏移量。
2. 在備庫B上執(zhí)行start slave命令忆某， 這時候備庫會啟動兩個線程点待， 就是圖中的io_thread和sql_thread。其中io_thread負責與主庫建立連接弃舒。
3. 主庫A校驗完用戶名癞埠、 密碼后， 開始按照備庫B傳過來的位置， 從本地讀取binlog苗踪， 發(fā)給B颠区。
4. 備庫B拿到binlog后， 寫到本地文件通铲， 稱為中轉(zhuǎn)日志（relaylog）瓦呼。
5. sql_thread讀取中轉(zhuǎn)日志， 解析出日志里的命令测暗， 并執(zhí)行。

binlog的三種格式

同樣是刪除表里面一行數(shù)據(jù)磨澡，不同格式的binlog記錄的內(nèi)容是不一樣的：

1. statement格式下：記錄到binlog里的是語句原文碗啄。因此可能會出現(xiàn)這樣一種情況： 在主庫執(zhí)行這條SQL語句的時候， 用的是索引a稳摄； 而在備庫執(zhí)行這條SQL語句的時候稚字， 卻使用了索引t_modified。 因此厦酬， MySQL認為這樣寫是有風險的胆描。
2. row格式：binlog里面記錄了真實刪除行的主鍵id， 這樣binlog傳到備庫去的時候仗阅， 就肯定會刪除id=4的行昌讲， 不會有主備刪除不同行的問題。比如你用一個delete語句刪掉10萬行數(shù)據(jù)减噪，如果用row格式的binlog短绸，就要把這10萬條記錄都寫到binlog中。 這樣做筹裕， 不僅會占用更大的空間醋闭， 同時寫binlog也要耗費IO資源， 影響執(zhí)行速度朝卒。
3. mixed格式：基于statement和row格式各自的優(yōu)缺點证逻，MySQL就取了個折中方案， 也就是有了mixed格式的binlog抗斤。 mixed格式的意思是囚企， MySQL自己會判斷這條SQL語句是否可能引起主備不一致， 如果有可能豪治， 就用row格式洞拨，否則就用statement格式。

循環(huán)復制問題

雙M結(jié)構(gòu)：2個mysql server互為主備负拟。
雙M結(jié)構(gòu)存在一個問題需要解決：業(yè)務邏輯在節(jié)點A上更新了一條語句烦衣， 然后再把生成的binlog 發(fā)給節(jié)點B， 節(jié)點B執(zhí)行完這條更新語句后也會生成binlog。 如果節(jié)點A同時是節(jié)點B的備庫花吟， 相當于又把節(jié)點B新生成的binlog拿過來執(zhí)行了一次秸歧， 然后節(jié)點A和B間， 會不斷地循環(huán)執(zhí)行這個更新語句衅澈， 也就是循環(huán)復制了键菱。

解決方案：

1. 規(guī)定兩個庫的server id必須不同， 如果相同今布， 則它們之間不能設定為主備關系经备；
2. 一個備庫接到binlog并在重放的過程中， 生成與原binlog的server id相同的新的binlog部默；
3. 每個庫在收到從自己的主庫發(fā)過來的日志后侵蒙， 先判斷server id， 如果跟自己的相同傅蹂， 表示這個日志是自己生成的纷闺， 就直接丟棄這個日志

25 | MySQL是怎么保證高可用的？

主備延遲

1. 主庫A執(zhí)行完成一個事務份蝴， 寫入binlog犁功， 我們把這個時刻記為T1;
2. 之后傳給備庫B， 我們把備庫B接收完這個binlog的時刻記為T2;
3. 備庫B執(zhí)行完成這個事務婚夫， 我們把這個時刻記為T3浸卦。

所謂主備延遲， 就是同一個事務请敦， 在備庫執(zhí)行完成的時間和主庫執(zhí)行完成的時間之間的差值镐躲， 也就是T3-T1

主備延遲的來源

1. 有些部署條件下， 備庫所在機器的性能要比主庫所在的機器性能差侍筛。
2. 備庫的壓力大萤皂。 一般的想法是， 主庫既然提供了寫能力匣椰， 那么備庫可以提供一些讀能力裆熙。 或者一些運營后臺需要的分析語句， 不能影響正常業(yè)務禽笑， 所以只能在備庫上跑入录。
3. 大事務。

主備切換策略

可靠性優(yōu)先策略

1. 判斷備庫B現(xiàn)在的seconds_behind_master佳镜， 如果小于某個值（比如5秒） 繼續(xù)下一步僚稿， 否則持續(xù)重試這一步；
2. 把主庫A改成只讀狀態(tài)蟀伸， 即把readonly設置為true蚀同；
3. 判斷備庫B的seconds_behind_master的值缅刽， 直到這個值變成0為止；
4. 把備庫B改成可讀寫狀態(tài)蠢络， 也就是把readonly設置為false衰猛；
5. 把業(yè)務請求切到備庫B

可用性優(yōu)先策略

如果強行把步驟4、 5調(diào)整到最開始執(zhí)行刹孔， 也就是說不等主備數(shù)據(jù)同步啡省， 直接把連接切到備庫B， 并且讓備庫B可以讀寫髓霞， 那么系統(tǒng)幾乎就沒有不可用時間了卦睹。代價， 就是可能出現(xiàn)數(shù)據(jù)不一致的情況方库。

26 | 備庫為什么會延遲好幾個小時分预？

并行復制：原來的sql_thread不再直接更新數(shù)據(jù)了， 只負責讀取中轉(zhuǎn)日志和分發(fā)事務薪捍。 真正更新日志的， 變成了worker線程配喳。 而work線程的個數(shù)酪穿， 就是由參數(shù)slave_parallel_workers決定的。
coordinator在分發(fā)的時候晴裹， 需要滿足以下這兩個基本要求：

1. 不能造成更新覆蓋被济。 這就要求更新同一行的兩個事務， 必須被分發(fā)到同一個worker中涧团。
2. 同一個事務不能被拆開只磷， 必須放到同一個worker中。

MySQL 5.5版本的并行復制策略

按表分發(fā)策略

按表分發(fā)事務的基本思路是泌绣， 如果兩個事務更新不同的表钮追， 它們就可以并行。 因為數(shù)據(jù)是存儲在表里的阿迈， 所以按表分發(fā)元媚， 可以保證兩個worker不會更新同一行。當然苗沧， 如果有跨表的事務刊棕， 還是要把兩張表放在一起考慮的。具體實現(xiàn)就是：

1. 每個worker線程對應一個hash表待逞， 用于保存當前正在這個worker的“執(zhí)行隊列”里的事務所涉及的表甥角。 hash表的key是“庫名.表名”， value是一個數(shù)字识樱， 表示隊列中有多少個事務修改這個表嗤无。
2. 在有事務分配給worker時震束， 事務里面涉及的表會被加到對應的hash表中。 worker執(zhí)行完成后翁巍， 這個表會被從hash表中去掉驴一。

每個事務在分發(fā)的時候， 跟worker的沖突關系包括以下三種情況：

1. 如果跟所有worker都不沖突灶壶， coordinator線程就會把這個事務分配給最空閑的woker;
2. 如果跟多于一個worker沖突肝断， coordinator線程就進入等待狀態(tài)， 直到和這個事務存在沖突關系的worker只剩下1個驰凛；
3. 如果只跟一個worker沖突胸懈， coordinator線程就會把這個事務分配給這個存在沖突關系的worker

按行分發(fā)策略

要解決熱點表的并行復制問題， 就需要一個按行并行復制的方案恰响。 按行復制的核心思路是： 如果兩個事務沒有更新相同的行趣钱， 它們在備庫上可以并行執(zhí)行。 顯然胚宦， 這個模式要求binlog格式必須是row首有。
基于行的策略， 事務hash表中還需要考慮唯一鍵枢劝， 即key應該是“庫名+表名+索引a的名字+a的值”井联。

MySQL 5.6版本的并行復制策略

官方MySQL5.6版本， 支持了并行復制您旁， 只是支持的粒度是按庫并行烙常。用于決定分發(fā)策略的hash表里， key就是數(shù)據(jù)庫名鹤盒。這個策略的并行效果蚕脏， 取決于壓力模型。 如果在主庫上有多個DB侦锯， 并且各個DB的壓力均衡驼鞭， 使用這個策略的效果會很好。

MariaDB的并行復制策略

在實現(xiàn)上尺碰， MariaDB是這么做的：

1. 在一組里面一起提交的事務终议， 有一個相同的commit_id， 下一組就是commit_id+1葱蝗；
2. commit_id直接寫到binlog里面穴张；
3. 傳到備庫應用的時候， 相同commit_id的事務分發(fā)到多個worker執(zhí)行两曼；
4. 這一組全部執(zhí)行完成后皂甘， coordinator再去取下一批。

MySQL 5.7的并行復制策略

MySQL 5.7并行復制策略的思想是：

1. 同時處于prepare狀態(tài)的事務悼凑， 在備庫執(zhí)行時是可以并行的偿枕；
2. 處于prepare狀態(tài)的事務璧瞬， 與處于commit狀態(tài)的事務之間， 在備庫執(zhí)行時也是可以并行的渐夸。

MySQL 5.7.22的并行復制策略

在2018年4月份發(fā)布的MySQL 5.7.22版本里嗤锉， MySQL增加了一個新的并行復制策略， 基于WRITESET的并行復制墓塌。所以有了3中策略模式：

1. COMMIT_ORDER瘟忱， 表示的就是前面介紹的， 根據(jù)同時進入prepare和commit來判斷是否可以并行的策略苫幢。
2. WRITESET访诱， 表示的是對于事務涉及更新的每一行， 計算出這一行的hash值韩肝， 組成集合writeset触菜。 如果兩個事務沒有操作相同的行， 也就是說它們的writeset沒有交集哀峻， 就可以并行涡相。這個hash值是通過“庫名+表名+索引名+值”
3. WRITESET_SESSION， 是在WRITESET的基礎上多了一個約束剩蟀， 即在主庫上同一個線程先后執(zhí)行的兩個事務漾峡， 在備庫執(zhí)行的時候， 要保證相同的先后順序喻旷。

27 | 主庫出問題了， 從庫怎么辦牢屋？

基于位點的主備切換

取同步位點的方法是這樣的：

1. 等待新主庫A’把中轉(zhuǎn)日志（relaylog） 全部同步完成且预；
2. 在A’上執(zhí)行show master status命令， 得到當前A’上最新的File 和 Position烙无；
3. 取原主庫A故障的時刻T锋谐；
4. 用mysqlbinlog工具解析A’的File， 得到T時刻的位點截酷。

GTID

GTID的全稱是Global Transaction Identifier涮拗， 也就是全局事務ID， 是一個事務在提交的時候生成的迂苛， 是這個事務的唯一標識三热。mysql通過維護GTID來自動選擇主從同步的位點。

28 | 讀寫分離有哪些坑三幻？

一主多從的架構(gòu)下就漾，業(yè)務層很容易遇到主備延遲導致的讀寫分離問題，簡單點描述就是客戶端執(zhí)行完一個更新事務后馬上發(fā)起查詢念搬， 如果查詢選擇的是從庫的話抑堡， 就有可能讀到剛剛的事務更新之前的狀態(tài)摆出。本篇文章介紹的是解決主從延遲的幾種解決方案

強制走主庫方案

強制走主庫方案其實就是， 將查詢請求做分類：

1. 對于必須要拿到最新結(jié)果的請求首妖， 強制將其發(fā)到主庫上
2. 對于可以讀到舊數(shù)據(jù)的請求偎漫， 才將其發(fā)到從庫上

Sleep 方案

主庫更新后， 讀從庫之前先sleep一下有缆，很不精準就不展開說了象踊。。

配合semi-sync

semi-sync是半同步復制妒貌， 也就是semi-sync replication通危。semi-sync做了這樣的設計：

1. 事務提交的時候， 主庫把binlog發(fā)給從庫灌曙；
2. 從庫收到binlog以后菊碟， 發(fā)回給主庫一個ack， 表示收到了在刺；
3. 主庫收到這個ack以后逆害， 才能給客戶端返回“事務完成”的確認。

semi-sync有一個缺陷就是semi-sync+位點判斷的方案蚣驼， 只對一主一備的場景是成立的魄幕。 在一主多從場景中， 主庫只要等到一個從庫的ack颖杏， 就開始給客戶端返回確認纯陨。 這時， 在從庫上執(zhí)行查詢請求留储， 就有兩種情況：

1. 如果查詢是落在這個響應了ack的從庫上翼抠， 是能夠確保讀到最新數(shù)據(jù)；
2. 但如果是查詢落到其他從庫上获讳， 它們可能還沒有收到最新的日志阴颖， 就會產(chǎn)生過期讀的問題；

等主庫位點方案

select master_pos_wait(file, pos[, timeout]);這條命令的邏輯如下：

1. 它是在從庫執(zhí)行的丐膝；
2. 參數(shù)file和pos指的是主庫上的文件名和位置量愧；
3. timeout可選， 設置為正整數(shù)N表示這個函數(shù)最多等待N秒帅矗。

等主庫位點方案的邏輯如下：

1. trx1事務更新完成后偎肃， 馬上執(zhí)行show master status得到當前主庫執(zhí)行到的File和Position；
2. 選定一個從庫執(zhí)行查詢語句浑此；
3. 在從庫上執(zhí)行select master_pos_wait(File, Position, 1)软棺；
4. 如果返回值是>=0的正整數(shù)， 則在這個從庫執(zhí)行查詢語句尤勋；
5. 否則喘落， 到主庫執(zhí)行查詢語句茵宪。

GTID方案

select wait_for_executed_gtid_set(gtid_set, 1);這條命令的邏輯是：

1. 等待， 直到這個庫執(zhí)行的事務中包含傳入的gtid_set瘦棋， 返回0稀火；
2. 超時返回1。

等GTID方案的執(zhí)行流程就變成了：

1. trx1事務更新完成后赌朋， 從返回包直接獲取這個事務的GTID凰狞， 記為gtid1；
2. 選定一個從庫執(zhí)行查詢語句沛慢；
3. 在從庫上執(zhí)行 select wait_for_executed_gtid_set(gtid1, 1)赡若；
4. 如果返回值是0， 則在這個從庫執(zhí)行查詢語句团甲；
5. 否則逾冬， 到主庫執(zhí)行查詢語句