盡管此刻沒有如愿以償找到合適的ft，但我希望能夠充分認識到自己的不足，積蓄力量。相信在不久的將來會有爆發的機會。

---------------------------------------------------------------------------------------------

知識的廣度（component, 目的）和深度(sde1: 3年以內，sde2: 4年以上，sde3：team lead，org impact可小可大，深度，3+：org lead, 領域見解)

 

設計用戶系統，實現功能包括注冊、登陸、用戶信息查詢，好友關系存儲

Scenario:

注冊，登陸，查詢（需求量大），用戶信息修改

支持100M DAU

注冊，登陸，信息修改QPS

　　100M * 0.1 / 86400 ~100

　　0.1 = 平均每個用戶每天登陸+注冊+信息修改

　　peak = 100 * 3 = 300 -> Mysql

查詢的QPS

　　100M * 100 / 86400 ~100k

　　100 = 平均每個用戶每天查詢用戶信息相關的操作次數（查看好友，發信息，更新消息主頁）

　　peak = 100k * 3 = 300k ->Redis

Service:

　　一個authenticationService負責登陸注冊

　　一個userService負責用戶信息存儲和查詢

　　一個friendshipService負責好友關系存儲

Storage:

MySql/PosgreSql等SQL數據庫性能： 1k QPS

MongoDB/Cassandra等硬盤型Nosql數據庫性能：10k QPS

Redis/Memcached等內存型Nosql數據庫性能：100k~1m QPS

用戶系統特點：讀非常多，寫非常少。讀多寫少，一定用cache進行優化。

Cache: 把之后要查詢的東西先存一下。無需重新計算和存取數據庫。可以理解為hashmap, key-value結構。提供協議，淘汰機制（LRU/LFU cache）

• Memcached(純內存不支持數據存儲化，斷電后數據沒有）
• Redis（支持數據持久化）

Cache不一定在內存，沒有指定存在怎樣的存儲介質中。訪問遠端數據/計算量大的工作file system可以做cache, cpu也有cache。

Cache server cache, frontend/client/browser有客戶端cache。

 

Memcached

cache.set("key","value")

cache.get("key")

cache.set("foo",1,ttl=60) 這個key只能活60s　　

out of memory key may be evicted by cache

 

class UserService:

　　def getUser(self, user_id):

　　　　key = "user::%s" % user_id

　　　　user = cache.get(key)

　　　　if user:

　　　　　　return user

　　　　user = database.get(user_id)

　　　　cache.set(key, user)

　　　　return user

　　def setUser(self, user):

　　　　key = "user::%s" % user.id

 　　　　cache.delete(key) 

　　　　database.set(key,user)

數據庫和cache不一致問題，出現臟數據dirty data

多線程多進程下的數據不一致： process1: setUser, cachedelete()   process2: getUser cache.get() //none db.get() cache.set() // 更新老數據 process 1: db.set() // 寫入新數據

解決方法：數據庫和緩存加鎖不可以，因為是兩臺機器，兩套系統，要用分布式鎖，會導致存取效率降低，得不償失。

best practice:

　　database.set(key,user)

　　cache.delete(key)

多線程多進程下的數據不一致： process1: setUser, db.set()   process2: setUser db.set() // 更新老數據 process 1.2: cache.delete() 

process1: setUser, db.set()新數據 cache.delete()失敗老數據

原因：讀多寫少，cache heat rate:98%+

cache ttl 7天，基地概率下出現數據不一致，也就最多不一致7天

 

寫多讀少，寫時刪除cache, 讀取時cache miss，無讀的優化效果。寫改db,多db,分攤寫請求

 

cache aside: db <-> web server<-> cache      memcached + mysql

cache through: web server <-> [cache <-> DB]           redis只支持單純的kv存儲結構，無法適應復雜的應用場景

 

Authentication service (session, cookie)

session table（存在cache （+ db））

session_key 　　　　  string      //全局唯一，uuid

user_id　　　　　　   foreign key // 指向user table

expire_at　　　　　　timestamp //什么時候過期

<device_key>

• login以后創建session對象
• 并把session_key返回給瀏覽器，讓瀏覽器存儲起來
• 瀏覽器將該值記錄在瀏覽器的cookie中（哈希表）
• 用戶每次向服務器發送的訪問，都會自動帶上該網站所有的cookie
• 此時服務器拿到cookie中的session_key,在session table中檢測是否存在，是否過期

 

friendship service

單向

friendship table

from_user_id 　　 foreign key 用戶主體

to_user_id　　　　foreign key 被關注的人

select * from friendship where from_user_id = x 查關注對象

select * from friendship where to_user_id = x 查粉絲

 

雙向

smaller_user_id　　   bigger_user_id

1　　　　　　　　　　2

存儲容量小一半，查詢 select * from friendship where smaller_user_id = x or bigger_user_id = x 效率慢

or

from_user_id　　　　to_user_id

1　　　　　　　　　　2

2　　　　　　　　　　1

select * from friendship where from_user_id = x查詢快，時間要求》空間要求

寫入事務操作，同時成功同時失敗

 

Cassandra為例的nosql數據庫

第一層：row_key

第二層：column_key

第三層：value

Cassandra 的key = row_key + column_key, 只對應一個value

結構化信息serialize到value存儲 

row key/hash key/partition key/sharding key: 數據存在哪個機器上的依據，nosql實現分布式多臺機器存儲；常用：user_id

inset(row_key, column_key, value)

column key: 是排序的，row_key等于x， 進行范圍查詢query(row_key, column_start, column_end); 可以是復合值，如timestamp + user_id

 

sql: 以row為單位（取出row作為一條數據），每一列是一種屬性

nosql: column是動態的，無限大，以格子為單位，row_key + column_key + value = 一條數據

 

friendship table在cassandra存儲

row key: 　　　　　　　　　　　　　　　　user_id1 　　　　　　　　　　　　　　　　　　　　      user_id2

column key: 　　  friendship_user_id2　　　　　   　　　　friendship_user_id3　　　　　　　　　friend_user_id1

value:　　is_mutual_friend, is_blocked, timestamp　is_mutual_friend, is_blocked, timestamp　　　　

 

newsfeed在cassandra存儲

row_key:　　　　　　　　　　　　owner_id1

column_key:　　created_at1,tweet_id1　　created_at2,tweet_id2      拿tweet_id從cache里讀數據

value:　　　　　　tweet_data1　　　　　　　　tweet_data2

 

數據庫選擇原則1: 大部分情況，sql, nosql都可以

數據庫選擇原則2: 支持transaction，不能選nosql。在一臺機器上操作。

數據庫選擇原則3: sql-結構化數據，自由創建索引。nosql-分布式，auto-scale自動拓展，replica

數據庫選擇原則4: 一個網站同時用多種數據庫系統。不同的表單放在不同的數據庫

 

user table - sql: 信任度， multi-index

friendship - nosql: 結構簡單，key-value的查詢/存儲需求，nosql效率更高

 

paper:

dynamo db

scaling memcache at fb

couchbase architecture

LFU

 

練習1: nosql存單項好友關系：需要兩張表單，一張存粉絲，一張存關注。

redis:

key = user_id

value = set of friend_user_id（粉絲表就是粉絲ID，關注表就是關注id) 相當于hashset

查a是否關注了b： redis的sismember查詢b是否在value（a關注的人）中

 

Cassandra:

row_key = user_id

column_key = friend_user_id（粉絲表就是粉絲ID，關注表就是關注id) 

value=其他想同時存儲的東西，如關注時間

查a是否關注了b： 在關注表中查詢row_key = A, column_key = B的數據是否存在

 

練習2: nosql 存儲user。如果使用不支持multi-index的nosql存儲user。如何同時支持按照email, username, phone, id來檢索用戶。

redis: key = user_id, value = 用戶信息

Cassandra: row_key = user_id, column_key = 任何信息，value = 其他用戶信息

創建表單用作index，去查到user_id

redis: key = email/phone/username, value = user_id

Cassandra: row_key = email/phone/username, column_key = 任何信息，value = 其他用戶信息

 

練習3: A和B之間的共同好友

1. A的好友
2. B的好友
3. 求交集

讀多寫少，使用緩存存儲用戶的好友列表，而不是兩次數據庫查詢

 

練習4: 好友幾度關系BFS

　　細化需求：

• 查詢你和不超過10個人之間的關系
• 用戶數量集>100M
• 平均好友數1000個
• 期望的db query次數為常數級（<20次query）
• >3度沒有現實意義 3+

 雙向BFS，

a查好友，一度

b查好友，一度

查并集，二度

offline提前算好所有的一度和二度并存儲在nosql，

A 　一度 - 1次db

　　二度 - 1次db   交集3度

B 　一度 - 1次db