大家好，我是小林。

今天來分析字節(jié)跳動(dòng)校招后端開發(fā)面經(jīng)，同學(xué)的技術(shù)棧是 Java 后端，問八股文比較多，一共經(jīng)歷了一二三面，每一場(chǎng)面試的強(qiáng)度還是蠻高，每次都是 1 個(gè)小時(shí)+。

我把這幾場(chǎng)面試中比較有代表性的題目抽離出來給大家解析一波，給準(zhǔn)備春招的同學(xué)做一個(gè)參考和學(xué)習(xí)，雖然是校招的面試，但是有些問題，其實(shí)社招也經(jīng)常問的。

知識(shí)一學(xué)就忘原因，就是缺少溫故的過程，通過面試題的方式回顧系列的知識(shí)，也是一種高效的方式。

這次面經(jīng)的考點(diǎn)，我簡單羅列一下：

• 操作系統(tǒng)：進(jìn)程調(diào)度
• 網(wǎng)絡(luò)：HTTP、HTTPS
• Java：線程狀態(tài)、多線程、volatile、synchronized
• Redis：數(shù)據(jù)結(jié)構(gòu)、跳表、性能、場(chǎng)景應(yīng)用、緩存一致性
• MySQL：事務(wù)、隔離級(jí)別、日志、索引、間隙鎖、最左匹配原則
• 算法：每一輪 1 個(gè)算法

Redis

Redis 有哪些數(shù)據(jù)結(jié)構(gòu)？

Redis 提供了豐富的數(shù)據(jù)類型，常見的有五種數(shù)據(jù)類型：String（字符串），Hash（哈希），List（列表），Set（集合）、Zset（有序集合）。

圖片

圖片

隨著 Redis 版本的更新，后面又支持了四種數(shù)據(jù)類型：BitMap（2.2 版新增）、HyperLogLog（2.8 版新增）、GEO（3.2 版新增）、Stream（5.0 版新增）。Redis 五種數(shù)據(jù)類型的應(yīng)用場(chǎng)景：

• String 類型的應(yīng)用場(chǎng)景：緩存對(duì)象、常規(guī)計(jì)數(shù)、分布式鎖、共享 session 信息等。
• List 類型的應(yīng)用場(chǎng)景：消息隊(duì)列（但是有兩個(gè)問題：1. 生產(chǎn)者需要自行實(shí)現(xiàn)全局唯一 ID；2. 不能以消費(fèi)組形式消費(fèi)數(shù)據(jù)）等。
• Hash 類型：緩存對(duì)象、購物車等。
• Set 類型：聚合計(jì)算（并集、交集、差集）場(chǎng)景，比如點(diǎn)贊、共同關(guān)注、抽獎(jiǎng)活動(dòng)等。
• Zset 類型：排序場(chǎng)景，比如排行榜、電話和姓名排序等。

Redis 后續(xù)版本又支持四種數(shù)據(jù)類型，它們的應(yīng)用場(chǎng)景如下：

• BitMap（2.2 版新增）：二值狀態(tài)統(tǒng)計(jì)的場(chǎng)景，比如簽到、判斷用戶登陸狀態(tài)、連續(xù)簽到用戶總數(shù)等；
• HyperLogLog（2.8 版新增）：海量數(shù)據(jù)基數(shù)統(tǒng)計(jì)的場(chǎng)景，比如百萬級(jí)網(wǎng)頁 UV 計(jì)數(shù)等；
• GEO（3.2 版新增）：存儲(chǔ)地理位置信息的場(chǎng)景，比如滴滴叫車；
• Stream（5.0 版新增）：消息隊(duì)列，相比于基于 List 類型實(shí)現(xiàn)的消息隊(duì)列，有這兩個(gè)特有的特性：自動(dòng)生成全局唯一消息ID，支持以消費(fèi)組形式消費(fèi)數(shù)據(jù)。

Zset 使用了什么數(shù)據(jù)結(jié)構(gòu)？

Zset 類型的底層數(shù)據(jù)結(jié)構(gòu)是由壓縮列表或跳表實(shí)現(xiàn)的：

• 如果有序集合的元素個(gè)數(shù)小于 128 個(gè)，并且每個(gè)元素的值小于 64 字節(jié)時(shí)，Redis 會(huì)使用壓縮列表作為 Zset 類型的底層數(shù)據(jù)結(jié)構(gòu)；
• 如果有序集合的元素不滿足上面的條件，Redis 會(huì)使用跳表作為 Zset 類型的底層數(shù)據(jù)結(jié)構(gòu)；

在 Redis 7.0 中，壓縮列表數(shù)據(jù)結(jié)構(gòu)已經(jīng)廢棄了，交由 listpack 數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)了。

SkipList 了解嗎？

鏈表在查找元素的時(shí)候，因?yàn)樾枰鹨徊檎?，所以查詢效率非常低，時(shí)間復(fù)雜度是O(N)，于是就出現(xiàn)了跳表。跳表是在鏈表基礎(chǔ)上改進(jìn)過來的，實(shí)現(xiàn)了一種「多層」的有序鏈表，這樣的好處是能快讀定位數(shù)據(jù)。

那跳表長什么樣呢？我這里舉個(gè)例子，下圖展示了一個(gè)層級(jí)為 3 的跳表。

圖片

圖中頭節(jié)點(diǎn)有 L0~L2 三個(gè)頭指針，分別指向了不同層級(jí)的節(jié)點(diǎn)，然后每個(gè)層級(jí)的節(jié)點(diǎn)都通過指針連接起來：

• L0 層級(jí)共有 5 個(gè)節(jié)點(diǎn)，分別是節(jié)點(diǎn)1、2、3、4、5；
• L1 層級(jí)共有 3 個(gè)節(jié)點(diǎn)，分別是節(jié)點(diǎn) 2、3、5；
• L2 層級(jí)只有 1 個(gè)節(jié)點(diǎn)，也就是節(jié)點(diǎn) 3 。

如果我們要在鏈表中查找節(jié)點(diǎn) 4 這個(gè)元素，只能從頭開始遍歷鏈表，需要查找 4 次，而使用了跳表后，只需要查找 2 次就能定位到節(jié)點(diǎn) 4，因?yàn)榭梢栽陬^節(jié)點(diǎn)直接從 L2 層級(jí)跳到節(jié)點(diǎn) 3，然后再往前遍歷找到節(jié)點(diǎn) 4。

可以看到，這個(gè)查找過程就是在多個(gè)層級(jí)上跳來跳去，最后定位到元素。當(dāng)數(shù)據(jù)量很大時(shí)，跳表的查找復(fù)雜度就是 O(logN)。

跳表的時(shí)間復(fù)雜度是多少？

跳表中查找一個(gè)元素的時(shí)間復(fù)雜度為O(logn)，空間復(fù)雜度是 O(n)。

為什么 MysSQL 不用 SkipList？

B+樹的高度在3層時(shí)存儲(chǔ)的數(shù)據(jù)可能已達(dá)千萬級(jí)別，但對(duì)于跳表而言同樣去維護(hù)千萬的數(shù)據(jù)量那么所造成的跳表層數(shù)過高而導(dǎo)致的磁盤io次數(shù)增多，也就是使用B+樹在存儲(chǔ)同樣的數(shù)據(jù)下磁盤io次數(shù)更少。

Redis 使用場(chǎng)景?

Redis 是一種基于內(nèi)存的數(shù)據(jù)庫，對(duì)數(shù)據(jù)的讀寫操作都是在內(nèi)存中完成，因此讀寫速度非?？?，常用于緩存，消息隊(duì)列、分布式鎖等場(chǎng)景。

圖片

Redis用途

Redis 提供了多種數(shù)據(jù)類型來支持不同的業(yè)務(wù)場(chǎng)景，比如 String(字符串)、Hash(哈希)、 List (列表)、Set(集合)、Zset(有序集合)、Bitmaps（位圖）、HyperLogLog（基數(shù)統(tǒng)計(jì)）、GEO（地理信息）、Stream（流），并且對(duì)數(shù)據(jù)類型的操作都是原子性的，因?yàn)閳?zhí)行命令由單線程負(fù)責(zé)的，不存在并發(fā)競爭的問題。

除此之外，Redis 還支持事務(wù) 、持久化、Lua 腳本、多種集群方案（主從復(fù)制模式、哨兵模式、切片機(jī)群模式）、發(fā)布/訂閱模式，內(nèi)存淘汰機(jī)制、過期刪除機(jī)制等等。

Redis 性能好的原因是什么？

官方使用基準(zhǔn)測(cè)試的結(jié)果是，單線程的 Redis 吞吐量可以達(dá)到 10W/每秒，如下圖所示：

圖片

之所以 Redis 采用單線程（網(wǎng)絡(luò) I/O 和執(zhí)行命令）那么快，有如下幾個(gè)原因：

• Redis 的大部分操作都在內(nèi)存中完成，并且采用了高效的數(shù)據(jù)結(jié)構(gòu)，因此 Redis 瓶頸可能是機(jī)器的內(nèi)存或者網(wǎng)絡(luò)帶寬，而并非 CPU，既然 CPU 不是瓶頸，那么自然就采用單線程的解決方案了；
• Redis 采用單線程模型可以避免了多線程之間的競爭，省去了多線程切換帶來的時(shí)間和性能上的開銷，而且也不會(huì)導(dǎo)致死鎖問題。
• Redis 采用了 I/O 多路復(fù)用機(jī)制處理大量的客戶端 Socket 請(qǐng)求，IO 多路復(fù)用機(jī)制是指一個(gè)線程處理多個(gè) IO 流，就是我們經(jīng)常聽到的 select/epoll 機(jī)制。簡單來說，在 Redis 只運(yùn)行單線程的情況下，該機(jī)制允許內(nèi)核中，同時(shí)存在多個(gè)監(jiān)聽 Socket 和已連接 Socket。內(nèi)核會(huì)一直監(jiān)聽這些 Socket 上的連接請(qǐng)求或數(shù)據(jù)請(qǐng)求。一旦有請(qǐng)求到達(dá)，就會(huì)交給 Redis 線程處理，這就實(shí)現(xiàn)了一個(gè) Redis 線程處理多個(gè) IO 流的效果。

Redis 和 MySQL 如何保證一致性

可以采用「先更新數(shù)據(jù)庫，再刪除緩存」的更新策略+過期時(shí)間來兜底。

我們用「讀 + 寫」請(qǐng)求的并發(fā)的場(chǎng)景來分析。

假如某個(gè)用戶數(shù)據(jù)在緩存中不存在，請(qǐng)求 A 讀取數(shù)據(jù)時(shí)從數(shù)據(jù)庫中查詢到年齡為 20，在未寫入緩存中時(shí)另一個(gè)請(qǐng)求 B 更新數(shù)據(jù)。它更新數(shù)據(jù)庫中的年齡為 21，并且清空緩存。這時(shí)請(qǐng)求 A 把從數(shù)據(jù)庫中讀到的年齡為 20 的數(shù)據(jù)寫入到緩存中。

圖片

最終，該用戶年齡在緩存中是 20（舊值），在數(shù)據(jù)庫中是 21（新值），緩存和數(shù)據(jù)庫數(shù)據(jù)不一致。

從上面的理論上分析，先更新數(shù)據(jù)庫，再刪除緩存也是會(huì)出現(xiàn)數(shù)據(jù)不一致性的問題，但是在實(shí)際中，這個(gè)問題出現(xiàn)的概率并不高。

因?yàn)榫彺娴膶懭胪ǔＲh(yuǎn)遠(yuǎn)快于數(shù)據(jù)庫的寫入，所以在實(shí)際中很難出現(xiàn)請(qǐng)求 B 已經(jīng)更新了數(shù)據(jù)庫并且刪除了緩存，請(qǐng)求 A 才更新完緩存的情況。

而一旦請(qǐng)求 A 早于請(qǐng)求 B 刪除緩存之前更新了緩存，那么接下來的請(qǐng)求就會(huì)因?yàn)榫彺娌幻卸鴱臄?shù)據(jù)庫中重新讀取數(shù)據(jù)，所以不會(huì)出現(xiàn)這種不一致的情況。

所以，「先更新數(shù)據(jù)庫 + 再刪除緩存」的方案，是可以保證數(shù)據(jù)一致性的。

而且為了確保萬無一失，還給緩存數(shù)據(jù)加上了「過期時(shí)間」，就算在這期間存在緩存數(shù)據(jù)不一致，有過期時(shí)間來兜底，這樣也能達(dá)到最終一致。

MySQL

事務(wù)有哪些特性?

事務(wù) 4 個(gè)特性，分別如下：

• 原子性（Atomicity）：一個(gè)事務(wù)中的所有操作，要么全部完成，要么全部不完成，不會(huì)結(jié)束在中間某個(gè)環(huán)節(jié)，而且事務(wù)在執(zhí)行過程中發(fā)生錯(cuò)誤，會(huì)被回滾到事務(wù)開始前的狀態(tài)，就像這個(gè)事務(wù)從來沒有執(zhí)行過一樣，就好比買一件商品，購買成功時(shí)，則給商家付了錢，商品到手；購買失敗時(shí)，則商品在商家手中，消費(fèi)者的錢也沒花出去。
• 一致性（Consistency）：是指事務(wù)操作前和操作后，數(shù)據(jù)滿足完整性約束，數(shù)據(jù)庫保持一致性狀態(tài)。比如，用戶 A 和用戶 B 在銀行分別有 800 元和 600 元，總共 1400 元，用戶 A 給用戶 B 轉(zhuǎn)賬 200 元，分為兩個(gè)步驟，從 A 的賬戶扣除 200 元和對(duì) B 的賬戶增加 200 元。一致性就是要求上述步驟操作后，最后的結(jié)果是用戶 A 還有 600 元，用戶 B 有 800 元，總共 1400 元，而不會(huì)出現(xiàn)用戶 A 扣除了 200 元，但用戶 B 未增加的情況（該情況，用戶 A 和 B 均為 600 元，總共 1200 元）。
• 隔離性（Isolation）：數(shù)據(jù)庫允許多個(gè)并發(fā)事務(wù)同時(shí)對(duì)其數(shù)據(jù)進(jìn)行讀寫和修改的能力，隔離性可以防止多個(gè)事務(wù)并發(fā)執(zhí)行時(shí)由于交叉執(zhí)行而導(dǎo)致數(shù)據(jù)的不一致，因?yàn)槎鄠€(gè)事務(wù)同時(shí)使用相同的數(shù)據(jù)時(shí)，不會(huì)相互干擾，每個(gè)事務(wù)都有一個(gè)完整的數(shù)據(jù)空間，對(duì)其他并發(fā)事務(wù)是隔離的。也就是說，消費(fèi)者購買商品這個(gè)事務(wù)，是不影響其他消費(fèi)者購買的。
• 持久性（Durability）：事務(wù)處理結(jié)束后，對(duì)數(shù)據(jù)的修改就是永久的，即便系統(tǒng)故障也不會(huì)丟失。

隔離性有哪些隔離級(jí)別?

四個(gè)隔離級(jí)別如下：

• 讀未提交（*read uncommitted*），指一個(gè)事務(wù)還沒提交時(shí)，它做的變更就能被其他事務(wù)看到；
• 讀提交（*read committed*），指一個(gè)事務(wù)提交之后，它做的變更才能被其他事務(wù)看到；
• 可重復(fù)讀（*repeatable read*），指一個(gè)事務(wù)執(zhí)行過程中看到的數(shù)據(jù)，一直跟這個(gè)事務(wù)啟動(dòng)時(shí)看到的數(shù)據(jù)是一致的，MySQL InnoDB 引擎的默認(rèn)隔離級(jí)別；
• 串行化（*serializable* ）；會(huì)對(duì)記錄加上讀寫鎖，在多個(gè)事務(wù)對(duì)這條記錄進(jìn)行讀寫操作時(shí)，如果發(fā)生了讀寫沖突的時(shí)候，后訪問的事務(wù)必須等前一個(gè)事務(wù)執(zhí)行完成，才能繼續(xù)執(zhí)行；

按隔離水平高低排序如下：

圖片

針對(duì)不同的隔離級(jí)別，并發(fā)事務(wù)時(shí)可能發(fā)生的現(xiàn)象也會(huì)不同。

圖片

也就是說：

• 在「讀未提交」隔離級(jí)別下，可能發(fā)生臟讀、不可重復(fù)讀和幻讀現(xiàn)象；
• 在「讀提交」隔離級(jí)別下，可能發(fā)生不可重復(fù)讀和幻讀現(xiàn)象，但是不可能發(fā)生臟讀現(xiàn)象；
• 在「可重復(fù)讀」隔離級(jí)別下，可能發(fā)生幻讀現(xiàn)象，但是不可能臟讀和不可重復(fù)讀現(xiàn)象；
• 在「串行化」隔離級(jí)別下，臟讀、不可重復(fù)讀和幻讀現(xiàn)象都不可能會(huì)發(fā)生。

MySQL 默認(rèn)用的哪個(gè)級(jí)別?

MySQL 默認(rèn)隔離級(jí)別是「可重復(fù)讀」，可以很大程度上避免幻讀現(xiàn)象的發(fā)生（注意是很大程度避免，并不是徹底避免），所以 MySQL 并不會(huì)使用「串行化」隔離級(jí)別來避免幻讀現(xiàn)象的發(fā)生，因?yàn)槭褂谩复谢垢綦x級(jí)別會(huì)影響性能。

間隙鎖的原理

Gap Lock 稱為間隙鎖，只存在于可重復(fù)讀隔離級(jí)別，目的是為了解決可重復(fù)讀隔離級(jí)別下幻讀的現(xiàn)象。

假設(shè)，表中有一個(gè)范圍 id 為（3，5）間隙鎖，那么其他事務(wù)就無法插入 id = 4 這條記錄了，這樣就有效的防止幻讀現(xiàn)象的發(fā)生。

img

間隙鎖雖然存在 X 型間隙鎖和 S 型間隙鎖，但是并沒有什么區(qū)別，間隙鎖之間是兼容的，即兩個(gè)事務(wù)可以同時(shí)持有包含共同間隙范圍的間隙鎖，并不存在互斥關(guān)系，因?yàn)殚g隙鎖的目的是防止插入幻影記錄而提出的。

什么時(shí)候會(huì)加間隙鎖?

當(dāng)我們用唯一索引進(jìn)行等值查詢的時(shí)候，查詢的記錄不存在的時(shí)候，在索引樹找到第一條大于該查詢記錄的記錄后，將該記錄的索引中的 next-key lock 會(huì)退化成「間隙鎖」。

假設(shè)事務(wù) A 執(zhí)行了這條等值查詢語句，查詢的記錄是「不存在」于表中的。

mysql> begin;
Query OK, 0 rows affected (0.00 sec)

mysql> select * from user where id = 2 for update;
Empty set (0.03 sec)

接下來，通過 select * from performance_schema.data_locks\G; 這條語句，查看事務(wù)執(zhí)行 SQL 過程中加了什么鎖。

圖片

從上圖可以看到，共加了兩個(gè)鎖，分別是：

• 表鎖：X 類型的意向鎖；
• 行鎖：X 類型的間隙鎖；

因此，此時(shí)事務(wù) A 在 id = 5 記錄的主鍵索引上加的是間隙鎖，鎖住的范圍是 (1, 5)。

圖片

接下來，如果有其他事務(wù)插入 id 值為 2、3、4 這一些記錄的話，這些插入語句都會(huì)發(fā)生阻塞。

注意，如果其他事務(wù)插入的 id = 1 或者 id = 5 的記錄話，并不會(huì)發(fā)生阻塞，而是報(bào)主鍵沖突的錯(cuò)誤，因?yàn)楸碇幸呀?jīng)存在 id = 1 和 id = 5 的記錄了。

比如，下面這個(gè)例子：

img

因?yàn)槭聞?wù) A 在 id = 5 記錄的主鍵索引上加了范圍為 (1, 5) 的 X 型間隙鎖，所以事務(wù) B 在插入一條 id 為 3 的記錄時(shí)會(huì)被阻塞住，即無法插入 id = 3 的記錄。

MySQL 如何保證原子性?

通過 undo log 來保證原子性的。

undo log 是一種用于撤銷回退的日志。在事務(wù)沒提交之前，MySQL 會(huì)先記錄更新前的數(shù)據(jù)到 undo log 日志文件里面，當(dāng)事務(wù)回滾時(shí)，可以利用 undo log 來進(jìn)行回滾。如下圖：

回滾事務(wù)

undo log 撤銷過程具體是怎么撤銷的?

每當(dāng) InnoDB 引擎對(duì)一條記錄進(jìn)行操作（修改、刪除、新增）時(shí)，要把回滾時(shí)需要的信息都記錄到 undo log 里，比如：

• 在插入一條記錄時(shí)，要把這條記錄的主鍵值記下來，這樣之后回滾時(shí)只需要把這個(gè)主鍵值對(duì)應(yīng)的記錄刪掉就好了；
• 在刪除一條記錄時(shí)，要把這條記錄中的內(nèi)容都記下來，這樣之后回滾時(shí)再把由這些內(nèi)容組成的記錄插入到表中就好了；
• 在更新一條記錄時(shí)，要把被更新的列的舊值記下來，這樣之后回滾時(shí)再把這些列更新為舊值就好了。

在發(fā)生回滾時(shí)，就讀取 undo log 里的數(shù)據(jù)，然后做原先相反操作。比如當(dāng) delete 一條記錄時(shí)，undo log 中會(huì)把記錄中的內(nèi)容都記下來，然后執(zhí)行回滾操作的時(shí)候，就讀取 undo log 里的數(shù)據(jù)，然后進(jìn)行 insert 操作。

怎么決定建立哪些索引?

什么時(shí)候適用索引？

• 字段有唯一性限制的，比如商品編碼；
• 經(jīng)常用于 WHERE 查詢條件的字段，這樣能夠提高整個(gè)表的查詢速度，如果查詢條件不是一個(gè)字段，可以建立聯(lián)合索引。
• 經(jīng)常用于 GROUP BY 和 ORDER BY 的字段，這樣在查詢的時(shí)候就不需要再去做一次排序了，因?yàn)槲覀兌家呀?jīng)知道了建立索引之后在 B+Tree 中的記錄都是排序好的。

什么時(shí)候不需要?jiǎng)?chuàng)建索引？

• WHERE 條件，GROUP BY，ORDER BY 里用不到的字段，索引的價(jià)值是快速定位，如果起不到定位的字段通常是不需要?jiǎng)?chuàng)建索引的，因?yàn)樗饕菚?huì)占用物理空間的。
• 字段中存在大量重復(fù)數(shù)據(jù)，不需要?jiǎng)?chuàng)建索引，比如性別字段，只有男女，如果數(shù)據(jù)庫表中，男女的記錄分布均勻，那么無論搜索哪個(gè)值都可能得到一半的數(shù)據(jù)。在這些情況下，還不如不要索引，因?yàn)?MySQL 還有一個(gè)查詢優(yōu)化器，查詢優(yōu)化器發(fā)現(xiàn)某個(gè)值出現(xiàn)在表的數(shù)據(jù)行中的百分比很高的時(shí)候，它一般會(huì)忽略索引，進(jìn)行全表掃描。
• 表數(shù)據(jù)太少的時(shí)候，不需要?jiǎng)?chuàng)建索引；
• 經(jīng)常更新的字段不用創(chuàng)建索引，比如不要對(duì)電商項(xiàng)目的用戶余額建立索引，因?yàn)樗饕侄晤l繁修改，由

最左匹配是什么，舉個(gè)例子？

使用聯(lián)合索引時(shí)，存在最左匹配原則，也就是按照最左優(yōu)先的方式進(jìn)行索引的匹配。在使用聯(lián)合索引進(jìn)行查詢的時(shí)候，如果不遵循「最左匹配原則」，聯(lián)合索引會(huì)失效，這樣就無法利用到索引快速查詢的特性了。

比如，如果創(chuàng)建了一個(gè) (a, b, c) 聯(lián)合索引，如果查詢條件是以下這幾種，就可以匹配上聯(lián)合索引：

• where a=1；
• where a=1 and b=2 and c=3；
• where a=1 and b=2；

需要注意的是，因?yàn)橛胁樵儍?yōu)化器，所以 a 字段在 where 子句的順序并不重要。

但是，如果查詢條件是以下這幾種，因?yàn)椴环献钭笃ヅ湓瓌t，所以就無法匹配上聯(lián)合索引，聯(lián)合索引就會(huì)失效:

• where b=2；
• where c=3；
• where b=2 and c=3；

上面這些查詢條件之所以會(huì)失效，是因?yàn)?a, b, c) 聯(lián)合索引，是先按 a 排序，在 a 相同的情況再按 b 排序，在 b 相同的情況再按 c 排序。所以，b 和 c 是全局無序，局部相對(duì)有序的，這樣在沒有遵循最左匹配原則的情況下，是無法利用到索引的。

我這里舉聯(lián)合索引（a，b）的例子，該聯(lián)合索引的 B+ Tree 如下（圖中葉子節(jié)點(diǎn)之間我畫了單向鏈表，但是實(shí)際上是雙向鏈表，原圖我找不到了，修改不了，偷個(gè)懶我不重畫了，大家腦補(bǔ)成雙向鏈表就行）。

可以看到，a 是全局有序的（1, 2, 2, 3, 4, 5, 6, 7 ,8），而 b 是全局是無序的（12，7，8，2，3，8，10，5，2）。因此，直接執(zhí)行where b = 2這種查詢條件沒有辦法利用聯(lián)合索引的，利用索引的前提是索引里的 key 是有序的。

只有在 a 相同的情況才，b 才是有序的，比如 a 等于 2 的時(shí)候，b 的值為（7，8），這時(shí)就是有序的，這個(gè)有序狀態(tài)是局部的，因此，執(zhí)行where a = 2 and b = 7是 a 和 b 字段能用到聯(lián)合索引的，也就是聯(lián)合索引生效了。

Java

Java 里面線程有哪些狀態(tài)?

源自《Java并發(fā)編程藝術(shù)》

java.lang.Thread.State枚舉類中定義了六種線程的狀態(tài)，可以調(diào)用線程Thread中的getState()方法獲取當(dāng)前線程的狀態(tài)。

wait 狀態(tài)下的線程如何進(jìn)行恢復(fù)到 running 狀態(tài)?

• 等待的線程被其他線程對(duì)象喚醒，notify()和notifyAll()。
• 如果線程沒有獲取到鎖則會(huì)直接進(jìn)入 Waiting 狀態(tài)，其實(shí)這種本質(zhì)上它就是執(zhí)行了 LockSupport.park() 方法進(jìn)入了Waiting 狀態(tài)，那么解鎖的時(shí)候會(huì)執(zhí)行LockSupport.unpark(Thread)，與上面park方法對(duì)應(yīng)，給出許可證，解除等待狀態(tài)。

notify 和 notifyAll 的區(qū)別?

同樣是喚醒等待的線程，同樣最多只有一個(gè)線程能獲得鎖，同樣不能控制哪個(gè)線程獲得鎖。

區(qū)別在于：

• notify：喚醒一個(gè)線程，其他線程依然處于wait的等待喚醒狀態(tài)，如果被喚醒的線程結(jié)束時(shí)沒調(diào)用notify，其他線程就永遠(yuǎn)沒人去喚醒，只能等待超時(shí)，或者被中斷
• notifyAll：所有線程退出wait的狀態(tài)，開始競爭鎖，但只有一個(gè)線程能搶到，這個(gè)線程執(zhí)行完后，其他線程又會(huì)有一個(gè)幸運(yùn)兒脫穎而出得到鎖

notify 選擇哪個(gè)線程?

notify在源碼的注釋中說到notify選擇喚醒的線程是任意的，但是依賴于具體實(shí)現(xiàn)的jvm。

圖片

notify源碼

JVM有很多實(shí)現(xiàn)，比較流行的就是hotspot，hotspot對(duì)notofy()的實(shí)現(xiàn)并不是我們以為的隨機(jī)喚醒,，而是“先進(jìn)先出”的順序喚醒。

如何停止一個(gè)線程的運(yùn)行?

主要有這些方法：

• 異常法停止：線程調(diào)用interrupt()方法后，在線程的run方法中判斷當(dāng)前對(duì)象的interrupted()狀態(tài)，如果是中斷狀態(tài)則拋出異常，達(dá)到中斷線程的效果。
• 在沉睡中停止：先將線程sleep，然后調(diào)用interrupt標(biāo)記中斷狀態(tài)，interrupt會(huì)將阻塞狀態(tài)的線程中斷。會(huì)拋出中斷異常，達(dá)到停止線程的效果
• stop()暴力停止：線程調(diào)用stop()方法會(huì)被暴力停止，方法已棄用，該方法會(huì)有不好的后果：強(qiáng)制讓線程停止有可能使一些請(qǐng)理性的工作得不到完成。
• 使用return停止線程：調(diào)用interrupt標(biāo)記為中斷狀態(tài)后，在run方法中判斷當(dāng)前線程狀態(tài)，如果為中斷狀態(tài)則return，能達(dá)到停止線程的效果。

調(diào)用 interrupt 是如何讓線程拋出異常的?

每個(gè)線程都一個(gè)與之關(guān)聯(lián)的布爾屬性來表示其中斷狀態(tài)，中斷狀態(tài)的初始值為false，當(dāng)一個(gè)線程被其它線程調(diào)用Thread.interrupt()方法中斷時(shí)，會(huì)根據(jù)實(shí)際情況做出響應(yīng)。

• 如果該線程正在執(zhí)行低級(jí)別的可中斷方法（如Thread.sleep()、Thread.join()或Object.wait()），則會(huì)解除阻塞并拋出InterruptedException異常。
• 否則Thread.interrupt()僅設(shè)置線程的中斷狀態(tài)，在該被中斷的線程中稍后可通過輪詢中斷狀態(tài)來決定是否要停止當(dāng)前正在執(zhí)行的任務(wù)。

如果是靠變量來停止線程，缺點(diǎn)是什么?

缺點(diǎn)是中斷可能不夠及時(shí)，循環(huán)判斷時(shí)會(huì)到下一個(gè)循環(huán)才能判斷出來。

class InterruptFlag {
  // 自定義的中斷標(biāo)識(shí)符
  private static volatile boolean isInterrupt = false;

  public static void main(String[] args) throws InterruptedException {
    // 創(chuàng)建可中斷的線程實(shí)例
    Thread thread = new Thread(() -> {
      while (!isInterrupt) { // 如果 isInterrupt=true 則停止線程
        System.out.println("thread 執(zhí)行步驟1：線程即將進(jìn)入休眠狀態(tài)");
        try {
          // 休眠 1s
          Thread.sleep(1000);
        } catch (InterruptedException e) {
          e.printStackTrace();
        }
        System.out.println("thread 執(zhí)行步驟2：線程執(zhí)行了任務(wù)");
      }
    });
    
    thread.start(); // 啟動(dòng)線程
    // 休眠 100ms，等待 thread 線程運(yùn)行起來
    Thread.sleep(100);
    System.out.println("主線程：試圖終止線程 thread");
    // 修改中斷標(biāo)識(shí)符，中斷線程
    isInterrupt = true;
  }
}

當(dāng)終止線程后，執(zhí)行步驟2依然會(huì)被執(zhí)行，這就是缺點(diǎn)。

volatile 保證原子性嗎？

volatile關(guān)鍵字并沒有保證我們的變量的原子性，volatile是Java虛擬機(jī)提供的一種輕量級(jí)的同步機(jī)制，主要有這三個(gè)特性：

• 保證可見性
• 不保證原子性
• 禁止指令重排

那我們要如何保證原子性?

可以通過synchronized來保證原子性。

synchronized 支持重入嗎？如何實(shí)現(xiàn)的?

synchronized是基于原子性的內(nèi)部鎖機(jī)制，是可重入的，因此在一個(gè)線程調(diào)用synchronized方法的同時(shí)在其方法體內(nèi)部調(diào)用該對(duì)象另一個(gè)synchronized方法，也就是說一個(gè)線程得到一個(gè)對(duì)象鎖后再次請(qǐng)求該對(duì)象鎖，是允許的，這就是synchronized的可重入性。

synchronized底層是利用計(jì)算機(jī)系統(tǒng)mutex Lock實(shí)現(xiàn)的。每一個(gè)可重入鎖都會(huì)關(guān)聯(lián)一個(gè)線程ID和一個(gè)鎖狀態(tài)status。

當(dāng)一個(gè)線程請(qǐng)求方法時(shí)，會(huì)去檢查鎖狀態(tài)。

1. 如果鎖狀態(tài)是0，代表該鎖沒有被占用，使用CAS操作獲取鎖，將線程ID替換成自己的線程ID。
2. 如果鎖狀態(tài)不是0，代表有線程在訪問該方法。此時(shí)，如果線程ID是自己的線程ID，如果是可重入鎖，會(huì)將status自增1，然后獲取到該鎖，進(jìn)而執(zhí)行相應(yīng)的方法；如果是非重入鎖，就會(huì)進(jìn)入阻塞隊(duì)列等待。

在釋放鎖時(shí)，

1. 如果是可重入鎖的，每一次退出方法，就會(huì)將status減1，直至status的值為0，最后釋放該鎖。
2. 如果非可重入鎖的，線程退出方法，直接就會(huì)釋放該鎖。

網(wǎng)絡(luò)

HTTP 與 HTTPS 協(xié)議的區(qū)別？

HTTP 與 HTTPS 網(wǎng)絡(luò)層

• HTTP 是超文本傳輸協(xié)議，信息是明文傳輸，存在安全風(fēng)險(xiǎn)的問題。HTTPS 則解決 HTTP 不安全的缺陷，在 TCP 和 HTTP 網(wǎng)絡(luò)層之間加入了 SSL/TLS 安全協(xié)議，使得報(bào)文能夠加密傳輸。
• HTTP 連接建立相對(duì)簡單， TCP 三次握手之后便可進(jìn)行 HTTP 的報(bào)文傳輸。而 HTTPS 在 TCP 三次握手之后，還需進(jìn)行 SSL/TLS 的握手過程，才可進(jìn)入加密報(bào)文傳輸。
• 兩者的默認(rèn)端口不一樣，HTTP 默認(rèn)端口號(hào)是 80，HTTPS 默認(rèn)端口號(hào)是 443。
• HTTPS 協(xié)議需要向 CA（證書權(quán)威機(jī)構(gòu)）申請(qǐng)數(shù)字證書，來保證服務(wù)器的身份是可信的。

操作系統(tǒng)

有哪些進(jìn)程調(diào)度算法 ?

01 先來先服務(wù)調(diào)度算法

最簡單的一個(gè)調(diào)度算法，就是非搶占式的先來先服務(wù)（*First Come First Serve, FCFS*）算法了。

FCFS 調(diào)度算法

顧名思義，先來后到，每次從就緒隊(duì)列選擇最先進(jìn)入隊(duì)列的進(jìn)程，然后一直運(yùn)行，直到進(jìn)程退出或被阻塞，才會(huì)繼續(xù)從隊(duì)列中選擇第一個(gè)進(jìn)程接著運(yùn)行。

這似乎很公平，但是當(dāng)一個(gè)長作業(yè)先運(yùn)行了，那么后面的短作業(yè)等待的時(shí)間就會(huì)很長，不利于短作業(yè)。

FCFS 對(duì)長作業(yè)有利，適用于 CPU 繁忙型作業(yè)的系統(tǒng)，而不適用于 I/O 繁忙型作業(yè)的系統(tǒng)。

02 最短作業(yè)優(yōu)先調(diào)度算法

最短作業(yè)優(yōu)先（*Shortest Job First, SJF*）調(diào)度算法同樣也是顧名思義，它會(huì)優(yōu)先選擇運(yùn)行時(shí)間最短的進(jìn)程來運(yùn)行，這有助于提高系統(tǒng)的吞吐量。

SJF 調(diào)度算法

這顯然對(duì)長作業(yè)不利，很容易造成一種極端現(xiàn)象。

比如，一個(gè)長作業(yè)在就緒隊(duì)列等待運(yùn)行，而這個(gè)就緒隊(duì)列有非常多的短作業(yè)，那么就會(huì)使得長作業(yè)不斷的往后推，周轉(zhuǎn)時(shí)間變長，致使長作業(yè)長期不會(huì)被運(yùn)行。

03 高響應(yīng)比優(yōu)先調(diào)度算法

前面的「先來先服務(wù)調(diào)度算法」和「最短作業(yè)優(yōu)先調(diào)度算法」都沒有很好的權(quán)衡短作業(yè)和長作業(yè)。

那么，高響應(yīng)比優(yōu)先 （*Highest Response Ratio Next, HRRN*）調(diào)度算法主要是權(quán)衡了短作業(yè)和長作業(yè)。

每次進(jìn)行進(jìn)程調(diào)度時(shí)，先計(jì)算「響應(yīng)比優(yōu)先級(jí)」，然后把「響應(yīng)比優(yōu)先級(jí)」最高的進(jìn)程投入運(yùn)行，「響應(yīng)比優(yōu)先級(jí)」的計(jì)算公式：

圖片

從上面的公式，可以發(fā)現(xiàn)：

• 如果兩個(gè)進(jìn)程的「等待時(shí)間」相同時(shí)，「要求的服務(wù)時(shí)間」越短，「響應(yīng)比」就越高，這樣短作業(yè)的進(jìn)程容易被選中運(yùn)行；
• 如果兩個(gè)進(jìn)程「要求的服務(wù)時(shí)間」相同時(shí)，「等待時(shí)間」越長，「響應(yīng)比」就越高，這就兼顧到了長作業(yè)進(jìn)程，因?yàn)檫M(jìn)程的響應(yīng)比可以隨時(shí)間等待的增加而提高，當(dāng)其等待時(shí)間足夠長時(shí)，其響應(yīng)比便可以升到很高，從而獲得運(yùn)行的機(jī)會(huì)；

04 時(shí)間片輪轉(zhuǎn)調(diào)度算法

最古老、最簡單、最公平且使用最廣的算法就是時(shí)間片輪轉(zhuǎn)（*Round Robin, RR*）調(diào)度算法。

RR 調(diào)度算法

每個(gè)進(jìn)程被分配一個(gè)時(shí)間段，稱為時(shí)間片（*Quantum*），即允許該進(jìn)程在該時(shí)間段中運(yùn)行。

• 如果時(shí)間片用完，進(jìn)程還在運(yùn)行，那么將會(huì)把此進(jìn)程從 CPU 釋放出來，并把 CPU 分配給另外一個(gè)進(jìn)程；
• 如果該進(jìn)程在時(shí)間片結(jié)束前阻塞或結(jié)束，則 CPU 立即進(jìn)行切換；

另外，時(shí)間片的長度就是一個(gè)很關(guān)鍵的點(diǎn)：

• 如果時(shí)間片設(shè)得太短會(huì)導(dǎo)致過多的進(jìn)程上下文切換，降低了 CPU 效率；
• 如果設(shè)得太長又可能引起對(duì)短作業(yè)進(jìn)程的響應(yīng)時(shí)間變長。將

一般來說，時(shí)間片設(shè)為 20ms~50ms 通常是一個(gè)比較合理的折中值。

05 最高優(yōu)先級(jí)調(diào)度算法

前面的「時(shí)間片輪轉(zhuǎn)算法」做了個(gè)假設(shè)，即讓所有的進(jìn)程同等重要，也不偏袒誰，大家的運(yùn)行時(shí)間都一樣。

但是，對(duì)于多用戶計(jì)算機(jī)系統(tǒng)就有不同的看法了，它們希望調(diào)度是有優(yōu)先級(jí)的，即希望調(diào)度程序能從就緒隊(duì)列中選擇最高優(yōu)先級(jí)的進(jìn)程進(jìn)行運(yùn)行，這稱為最高優(yōu)先級(jí)（*Highest Priority First，HPF*）調(diào)度算法。

進(jìn)程的優(yōu)先級(jí)可以分為，靜態(tài)優(yōu)先級(jí)和動(dòng)態(tài)優(yōu)先級(jí)：

• 靜態(tài)優(yōu)先級(jí)：創(chuàng)建進(jìn)程時(shí)候，就已經(jīng)確定了優(yōu)先級(jí)了，然后整個(gè)運(yùn)行時(shí)間優(yōu)先級(jí)都不會(huì)變化；
• 動(dòng)態(tài)優(yōu)先級(jí)：根據(jù)進(jìn)程的動(dòng)態(tài)變化調(diào)整優(yōu)先級(jí)，比如如果進(jìn)程運(yùn)行時(shí)間增加，則降低其優(yōu)先級(jí)，如果進(jìn)程等待時(shí)間（就緒隊(duì)列的等待時(shí)間）增加，則升高其優(yōu)先級(jí)，也就是隨著時(shí)間的推移增加等待進(jìn)程的優(yōu)先級(jí)。

該算法也有兩種處理優(yōu)先級(jí)高的方法，非搶占式和搶占式：

• 非搶占式：當(dāng)就緒隊(duì)列中出現(xiàn)優(yōu)先級(jí)高的進(jìn)程，運(yùn)行完當(dāng)前進(jìn)程，再選擇優(yōu)先級(jí)高的進(jìn)程。
• 搶占式：當(dāng)就緒隊(duì)列中出現(xiàn)優(yōu)先級(jí)高的進(jìn)程，當(dāng)前進(jìn)程掛起，調(diào)度優(yōu)先級(jí)高的進(jìn)程運(yùn)行。

但是依然有缺點(diǎn)，可能會(huì)導(dǎo)致低優(yōu)先級(jí)的進(jìn)程永遠(yuǎn)不會(huì)運(yùn)行。

06 多級(jí)反饋隊(duì)列調(diào)度算法

多級(jí)反饋隊(duì)列（*Multilevel Feedback Queue*）調(diào)度算法是「時(shí)間片輪轉(zhuǎn)算法」和「最高優(yōu)先級(jí)算法」的綜合和發(fā)展。

顧名思義：

• 「多級(jí)」表示有多個(gè)隊(duì)列，每個(gè)隊(duì)列優(yōu)先級(jí)從高到低，同時(shí)優(yōu)先級(jí)越高時(shí)間片越短。
• 「反饋」表示如果有新的進(jìn)程加入優(yōu)先級(jí)高的隊(duì)列時(shí)，立刻停止當(dāng)前正在運(yùn)行的進(jìn)程，轉(zhuǎn)而去運(yùn)行優(yōu)先級(jí)高的隊(duì)列；

多級(jí)反饋隊(duì)列

來看看，它是如何工作的：

• 設(shè)置了多個(gè)隊(duì)列，賦予每個(gè)隊(duì)列不同的優(yōu)先級(jí)，每個(gè)隊(duì)列優(yōu)先級(jí)從高到低，同時(shí)優(yōu)先級(jí)越高時(shí)間片越短；
• 新的進(jìn)程會(huì)被放入到第一級(jí)隊(duì)列的末尾，按先來先服務(wù)的原則排隊(duì)等待被調(diào)度，如果在第一級(jí)隊(duì)列規(guī)定的時(shí)間片沒運(yùn)行完成，則將其轉(zhuǎn)入到第二級(jí)隊(duì)列的末尾，以此類推，直至完成；
• 當(dāng)較高優(yōu)先級(jí)的隊(duì)列為空，才調(diào)度較低優(yōu)先級(jí)的隊(duì)列中的進(jìn)程運(yùn)行。如果進(jìn)程運(yùn)行時(shí)，有新進(jìn)程進(jìn)入較高優(yōu)先級(jí)的隊(duì)列，則停止當(dāng)前運(yùn)行的進(jìn)程并將其移入到原隊(duì)列末尾，接著讓較高優(yōu)先級(jí)的進(jìn)程運(yùn)行；

可以發(fā)現(xiàn)，對(duì)于短作業(yè)可能可以在第一級(jí)隊(duì)列很快被處理完。對(duì)于長作業(yè)，如果在第一級(jí)隊(duì)列處理不完，可以移入下次隊(duì)列等待被執(zhí)行，雖然等待的時(shí)間變長了，但是運(yùn)行時(shí)間也變更長了，所以該算法很好的兼顧了長短作業(yè)，同時(shí)有較好的響應(yīng)時(shí)間。

算法

• 給定鏈表 1 -> 2 -> ... -> n-1 -> n，使用 O(1) 空間復(fù)雜度使其變?yōu)?1 -> n -> 2 -> n-1 -> ...
• 只記得有關(guān)滑動(dòng)窗口，應(yīng)該是力扣 TOP 100 的