python的multimap

『壹』 在C++中，multimap中如果有一個key對應了幾個value,那麼怎樣才能將它對應的value一一輸出

1、定義一個數組，其中value有重復部分。

『貳』 python菜鳥一問，請大大們解答，謝謝

哥們，需要import string：

>>> import string
>>> string.atoi('10') + 4
14

分析：錯誤原因說，name 'string' is not defined，意思是string沒有定義。。。所以import一下就好啦。。

『叄』 c++里 為什麼multimap比 vector插入時用的時間少

vector的底層數據結構是順序表，而multimap是紅黑樹。
順序表本質上是數組，假設某一時刻順序表中有n個元素，向其中插入一個元素x，大於x的元素有m個，那麼需要最少logn的時間找到插入的位置（二分查找），以及m的時間將該位置之後的m個元素全部後移一個單位，因此總共所需的時間復雜度是O(n)。
紅黑樹是一種自平衡二叉查找樹，假設某一時刻樹中有n個結點，則高度為logn，向其中插入一個元素x，需要logn的時間找到插入的位置，以及平均logn的時間用於旋轉調整樹結構（這個時間的推導比較復雜，需要考慮各種旋轉情況），因此總共所需的時間復雜度是O(logn)。

『肆』 「干貨」redis面試題

Redis 的全稱是：Remote Dictionary.Server，本質上是一個 Key-Value 類型的內存資料庫，很像

memcached，整個資料庫統統載入在內存當中進行操作，定期通過非同步操作把資料庫數據 flush 到硬碟

上進行保存。

因為是純內存操作，Redis 的性能非常出色，每秒可以處理超過 10 萬次讀寫操作，是已知性能最快的

Key-Value DB。

Redis 的出色之處不僅僅是性能，Redis 最大的魅力是支持保存多種數據結構，此外單個 value 的最大限

制是 1GB，不像 memcached 只能保存 1MB 的數據，因此 Redis 可以用來實現很多有用的功能。

比方說用他的 List 來做 FIFO 雙向鏈表，實現一個輕量級的高性 能消息隊列服務，用他的 Set 可以做高

性能的 tag 系統等等。

另外 Redis 也可以對存入的 Key-Value 設置 expire 時間，因此也可以被當作一 個功能加強版的

memcached 來用。 Redis 的主要缺點是資料庫容量受到物理內存的限制，不能用作海量數據的高性能

讀寫，因此 Redis 適合的場景主要局限在較小數據量的高性能操作和運算上。

1.memcached 所有的值均是簡單的字元串，redis 作為其替代者，支持更為豐富的數據類型

2.redis 的速度比 memcached 快很多 redis 的速度比 memcached 快很多

3.redis 可以持久化其數據 redis 可以持久化其數據

String、List、Set、Sorted Set、hashes

內存。

1.noeviction:返回錯誤當內存限制達到，並且客戶端嘗試執行會讓更多內存被使用的命令。

2.allkeys-lru: 嘗試回收最少使用的鍵（LRU），使得新添加的數據有空間存放。

3.volatile-lru: 嘗試回收最少使用的鍵（LRU），但僅限於在過期集合的鍵,使得新添加的數據有空間存

放。

4.allkeys-random: 回收隨機的鍵使得新添加的數據有空間存放。

5.volatile-random: 回收隨機的鍵使得新添加的數據有空間存放，但僅限於在過期集合的鍵。

6.volatile-ttl: 回收在過期集合的鍵，並且優先回收存活時間（TTL）較短的鍵,使得新添加的數據有空間

存放。

因為目前 Linux 版本已經相當穩定，而且用戶量很大，無需開發 windows 版本，反而會帶來兼容性等問

題。

512M

Redis 為了達到最快的讀寫速度將數據都讀到內存中，並通過非同步的方式將數據寫入磁碟。

所以 redis 具有快速和數據持久化的特徵，如果不將數據放在內存中，磁碟 I/O 速度為嚴重影響 redis 的

性能。

在內存越來越便宜的今天，redis 將會越來越受歡迎， 如果設置了最大使用的內存，則數據已有記錄數達

到內存限值後不能繼續插入新值。

1.codis 2.目前用的最多的集群方案，基本和 twemproxy 一致的效果，但它支持在節點數量改變情況下，舊節點

數據可恢復到新 hash 節點。

redis cluster3.0 自帶的集群，特點在於他的分布式演算法不是一致性 hash，而是 hash 槽的概念，以及自

身支持節點設置從節點。具體看官方文檔介紹。

3.在業務代碼層實現，起幾個毫無關聯的 redis 實例，在代碼層，對 key 進行 hash 計算，然後去對應的

redis 實例操作數據。這種方式對 hash 層代碼要求比較高，考慮部分包括，節點失效後的替代演算法方

案，數據震盪後的自動腳本恢復，實例的監控，等等。

有 A，B，C 三個節點的集群,在沒有復制模型的情況下,如果節點 B 失敗了，那麼整個集群就會以為缺少

5501-11000 這個范圍的槽而不可用。

redis 內存數據集大小上升到一定大小的時候，就會施行數據淘汰策略。

（1）會話緩存（Session Cache）

最常用的一種使用 Redis 的情景是會話緩存（sessioncache），用 Redis 緩存會話比其他存儲（如

Memcached）的優勢在於：Redis 提供持久化。當維護一個不是嚴格要求一致性的緩存時，如果用戶的

購物車信息全部丟失，大部分人都會不高興的，現在，他們還會這樣嗎？

幸運的是，隨著 Redis 這些年的改進，很容易找到怎麼恰當的使用 Redis 來緩存會話的文檔。甚至廣為

人知的商業平台 Magento 也提供 Redis 的插件。

（2）全頁緩存（FPC）

除基本的會話 token 之外，Redis 還提供很簡便的 FPC 平台。回到一致性問題，即使重啟了 Redis 實

例，因為有磁碟的持久化，用戶也不會看到頁面載入速度的下降，這是一個極大改進，類似 PHP 本地

FPC。

再次以 Magento 為例，Magento 提供一個插件來使用 Redis 作為全頁緩存後端。

此外，對 WordPress 的用戶來說，Pantheon 有一個非常好的插件 wp-redis，這個插件能幫助你以最快

速度載入你曾瀏覽過的頁面。

（3）隊列

Reids 在內存存儲引擎領域的一大優點是提供 list 和 set 操作，這使得 Redis 能作為一個很好的消息隊列

平台來使用。Redis 作為隊列使用的操作，就類似於本地程序語言（如 Python）對 list 的 push/pop

操作。

如果你快速的在 Google 中搜索「Redis queues」，你馬上就能找到大量的開源項目，這些項目的目的

就是利用 Redis 創建非常好的後端工具，以滿足各種隊列需求。例如，Celery 有一個後台就是使用

Redis 作為 broker，你可以從這里去查看。

（4）排行榜/計數器 Redis 在內存中對數字進行遞增或遞減的操作實現的非常好。集合（Set）和有序集合（SortedSet）也使

得我們在執行這些操作的時候變的非常簡單，Redis 只是正好提供了這兩種數據結構。

所以，我們要從排序集合中獲取到排名最靠前的 10 個用戶–我們稱之為「user_scores」，我們只需要像

下面一樣執行即可：

當然，這是假定你是根據你用戶的分數做遞增的排序。如果你想返回用戶及用戶的分數，你需要這樣執

行：

ZRANGE user_scores 0 10 WITHSCORES

Agora Games 就是一個很好的例子，用 Ruby 實現的，它的排行榜就是使用 Redis 來存儲數據的，你可

以在這里看到。

立聊天系統！

Redisson、Jedis、lettuce 等等，官方推薦使用 Redisson。

Redisson 是一個高級的分布式協調 Redis 客服端，能幫助用戶在分布式環境中輕松實現一些 Java 的對

象 (Bloom filter, BitSet, Set, SetMultimap, ScoredSortedSet, SortedSet, Map, ConcurrentMap,

List, ListMultimap, Queue, BlockingQueue, Deque, BlockingDeque, Semaphore, Lock,

ReadWriteLock, AtomicLong, CountDownLatch, Publish / Subscribe, HyperLogLog)。

Jedis 是 Redis 的 Java 實現的客戶端，其 API 提供了比較全面的 Redis 命令的支持；

Redisson 實現了分布式和可擴展的 Java 數據結構，和 Jedis 相比，功能較為簡單，不支持字元串操作，

Redis 集群沒有使用一致性 hash,而是引入了哈希槽的概念，Redis 集群有 16384 個哈希槽，每個 key 通

過 CRC16 校驗後對 16384 取模來決定放置哪個槽，集群的每個節點負責一部分 hash 槽。

為了使在部分節點失敗或者大部分節點無法通信的情況下集群仍然可用，所以集群使用了主從復制模型,

每個節點都會有 N-1 個復製品.

Redis 並不能保證數據的強一致性，這意味這在實際中集群在特定的條件下可能會丟失寫操作。

非同步復制

16384 個

Redis 集群目前無法做資料庫選擇，默認在 0 資料庫。

一次請求/響應伺服器能實現處理新的請求即使舊的請求還未被響應，這樣就可以將多個命令發送到服務

器，而不用等待回復，最後在一個步驟中讀取該答復。

這就是管道（pipelining），是一種幾十年來廣泛使用的技術。例如許多 POP3 協議已經實現支持這個功

能，大大加快了從伺服器下載新郵件的過程。

事務是一個單獨的隔離操作：事務中的所有命令都會序列化、按順序地執行，事務在執行的過程中，不會被其他客戶端發送來的命令請求所打斷。

事務是一個原子操作：事務中的命令要麼全部被執行，要麼全部都不執行。

MULTI、EXEC、DISCARD、WATCH

EXPIRE 和 PERSIST 命令

盡可能使用散列表（hashes），散列表（是說散列表裡面存儲的數少）使用的內存非常小，所以你應該盡可能的將你的數據模型抽象到一個散列表裡面。

比如你的 web 系統中有一個用戶對象，不要為這個用戶的名稱，姓氏，郵箱，密碼設置單獨的 key,而是應該把這個用戶的所有信息存儲到一張散列表裡面。

一個客戶端運行了新的命令，添加了新的數據。Redi 檢查內存使用情況，如果大於 maxmemory 的限制, 則根據設定好的策略進行回收。一個新的命令被執行，等等。

所以我們不斷地穿越內存限制的邊界，通過不斷達到邊界然後不斷地回收回到邊界以下。

如果一個命令的結果導致大量內存被使用（例如很大的集合的交集保存到一個新的鍵），不用多久內存限制就會被這個內存使用量超越。

咱們來看上面那張圖，現在某個客戶端要加鎖。如果該客戶端面對的是一個 redis cluster 集 群，他首先會根據 hash 節點選擇一台機器。這里注意，僅僅只是選擇一台機器！這點很關 鍵！緊接著，就會發送一段 lua 腳本到 redis 上，那段 lua 腳本如下所示：

為啥要用 lua 腳本呢？因為一大坨復雜的業務邏輯，可以通過封裝在 lua 腳本中發送給 redis， 保證這段復雜業務邏輯執行的原子性。

那麼，這段 lua 腳本是什麼意思呢？這里 KEYS[1]代表的是你加鎖的那個 key，比如說：RLoc

k lock = redisson.getLock("myLock");這里你自己設置了加鎖的那個鎖 key 就是「myLock」。

ARGV[1]代表的就是鎖 key 的默認生存時間，默認 30 秒。ARGV[2]代表的是加鎖的客戶端的 I D，類似於下面這樣：8743c9c0-0795-4907-87fd-6c719a6b4586:1

給大家解釋一下，第一段 if 判斷語句，就是用「exists myLock」命令判斷一下，如果你要加鎖 的那個鎖 key 不存在的話，你就進行加鎖。如何加鎖呢？很簡單，用下面的命令：hset myLoc k 8743c9c0-0795-4907-87fd-6c719a6b4586:1 1，通過這個命令設置一個 hash 數據結構，這行 命令執行後，會出現一個類似下面的數據結構：

上述就代表「8743c9c0-0795-4907-87fd-6c719a6b4586:1」這個客戶端對「myLock」這個鎖 key 完 成了加鎖。接著會執行「pexpire myLock 30000」命令，設置 myLock 這個鎖 key 的生存時間 是 30 秒。好了，到此為止，ok，加鎖完成了。

那麼在這個時候，如果客戶端 2 來嘗試加鎖，執行了同樣的一段 lua 腳本，會咋樣呢？很簡 單，第一個 if 判斷會執行「exists myLock」，發現 myLock 這個鎖 key 已經存在了。接著第二 個 if 判斷，判斷一下，myLock 鎖 key 的 hash 數據結構中，是否包含客戶端 2 的 ID，但是明 顯不是的，因為那裡包含的是客戶端 1 的 ID。

所以，客戶端 2 會獲取到 pttl myLock 返回的一個數字，這個數字代表了 myLock 這個鎖 key 的剩餘生存時間。比如還剩 15000 毫秒的生存時間。此時客戶端 2 會進入一個 while 循環，不 停的嘗試加鎖。

客戶端 1 加鎖的鎖 key 默認生存時間才 30 秒，如果超過了 30 秒，客戶端 1 還想一直持有這把 鎖，怎麼辦呢？

簡單！只要客戶端 1 一旦加鎖成功，就會啟動一個 watch dog 看門狗，他是一個後台線程，會 每隔 10 秒檢查一下，如果客戶端 1 還持有鎖 key，那麼就會不斷的延長鎖 key 的生存時間。

31.可重入加鎖機制

那如果客戶端 1 都已經持有了這把鎖了，結果可重入的加鎖會怎麼樣呢？比如下面這種代碼：

這時我們來分析一下上面那段 lua 腳本。第一個 if 判斷肯定不成立，「exists myLock」會顯示鎖 key 已經存在了。第二個 if 判斷會成立，因為 myLock 的 hash 數據結構中包含的那個 ID，就 是客戶端 1 的那個 ID，也就是「8743c9c0-0795-4907-87fd-6c719a6b4586:1」 此時就會執行可重入加鎖的邏輯，他會用：

incrby myLock 8743c9c0-0795-4907-87fd-6c71a6b4586:1 1 ，通過這個命令，對客戶端 1 的加鎖次數，累加 1。此時 myLock 數據結構變為下面這樣：

大家看到了吧，那個 myLock 的 hash 數據結構中的那個客戶端 ID，就對應著加鎖的次數

如果執行 lock.unlock()，就可以釋放分布式鎖，此時的業務邏輯也是非常簡單的。其實說白 了，就是每次都對 myLock 數據結構中的那個加鎖次數減 1。如果發現加鎖次數是 0 了，說明 這個客戶端已經不再持有鎖了，此時就會用：「del myLock」命令，從 redis 里刪除這個 key。 然後呢，另外的客戶端 2 就可以嘗試完成加鎖了。這就是所謂的分布式鎖的開源 Redisson 框 架的實現機制。

一般我們在生產系統中，可以用 Redisson 框架提供的這個類庫來基於 redis 進行分布式鎖的加 鎖與釋放鎖。

其實上面那種方案最大的問題，就是如果你對某個 redis master 實例，寫入了 myLock 這種鎖 key 的 value，此時會非同步復制給對應的 master slave 實例。但是這個過程中一旦發生 redis m aster 宕機，主備切換，redis slave 變為了 redis master。

接著就會導致，客戶端 2 來嘗試加鎖的時候，在新的 redis master 上完成了加鎖，而客戶端 1 也以為自己成功加了鎖。此時就會導致多個客戶端對一個分布式鎖完成了加鎖。這時系統在業 務語義上一定會出現問題，導致各種臟數據的產生。

所以這個就是 redis cluster，或者是 redis master-slave 架構的主從非同步復制導致的 redis 分布 式鎖的最大缺陷：在 redis master 實例宕機的時候，可能導致多個客戶端同時完成加鎖。

先拿 setnx 來爭搶鎖，搶到之後，再用 expire 給鎖加一個過期時間防止鎖忘記了釋放。

如果在 setnx 之後執行 expire 之前進程意外 crash 或者要重啟維護了，那會怎麼樣？

set 指令有非常復雜的參數，這個應該是可以同時把 setnx 和 expire 合成一條指令來用的！

緩存穿透

一般的緩存系統，都是按照 key 去緩存查詢，如果不存在對應的 value，就應該去後端系統查找（比如DB）。一些惡意的請求會故意查詢不存在的 key,請求量很大，就會對後端系統造成很大的壓力。這就叫做緩存穿透。

如何避免？

1：對查詢結果為空的情況也進行緩存，緩存時間設置短一點，或者該 key 對應的數據 insert 了之後清理緩存。

2：對一定不存在的 key 進行過濾。可以把所有的可能存在的 key 放到一個大的 Bitmap 中，查詢時通過該 bitmap 過濾。

緩存雪崩

當緩存伺服器重啟或者大量緩存集中在某一個時間段失效，這樣在失效的時候，會給後端系統帶來很大壓力。導致系統崩潰。

如何避免？

1：在緩存失效後，通過加鎖或者隊列來控制讀資料庫寫緩存的線程數量。比如對某個 key 只允許一個線程查詢數據和寫緩存，其他線程等待。

2：做二級緩存，A1 為原始緩存，A2 為拷貝緩存，A1 失效時，可以訪問 A2，A1 緩存失效時間設置為短期，A2 設置為長期

3：不同的 key，設置不同的過期時間，讓緩存失效的時間點盡量均勻