outline

Design User System用户系统
- Mencached 优化数据库查询软件
- Authentication 用户验证
- SQL VS NoSQL 如何选取数据库
- Friendship 存储好友关系（不用graph DB用什么）
How to Scale?
- Sharding
- Consistent Hashing(第5节)
- Replica(第5节)

4S分析法

Scenario场景
- 注册、登录、查询、用户修改信息
  
  哪个需求量最大？查询最大，因为用户登录时给他展示的各种信息邓邓就是通过查询出来的结果
- 支持100M DAU(每日登录用户数)
- 注册，登录，信息修改QPS约：
  - 100M*0.1/86400 ~ 100
  - 0.1=平均每个用户每天登陆+注册+信息修改
  - Peak = 100*3 = 300
- 查询的QPS约为：
  - 100M*100/86400 ~ 100k
  - 100 = 平均每个用户每天查询与用户信息相关的操作次数（查看好友、发信息，更新消息主页等）
  - Peak = 100k*3 = 300K
Service服务
- 一个AuthService 负责登录注册
- 一个UserService 负责用户信息与存储
- 一个FriendshipService存储好友关系
Storage:QPS与常用数据存储系统
- MySQL/PostgreSQL等数据库性能
  - 约1kQPS
- MongoDB/Cassandra等硬盘性NoSQL数据库
  - 约10QPS
- Redis/memcached等内存型NoSQL数据库性能
  - 100k~1mQPS
Scale

根据上面的QPS分析，注册、登录、信息修改300QPS，用mysql应该就够了

用户查询适合什么样的数据存储系统？

1. 缓存

1.1 Cache

用户系统特点：读非常多，写非常少，一定要用Cache进行优化

Cache 是什么？
- 缓存，把之后可能要查询的东西先存一下
  - 下次用的时候直接从这里拿，无需重新计算和存取数据库
- 可以理解为一个Java中的HashMap
- key-value的结构
有哪些常用的Cache软件？
- memcached（不支持数据持久化）
- Redis(支持数据持久化)
Cache一定存在内存中么？
- 不是
- Cache是用于连接不同的介质，解决速度差异的问题
- File System有时候也是一种cache
- CPU也有Cache
- 内存是硬盘和CPU的cache
Cache一定是Server Cache 么?
- 不，浏览器也可能有客户端的cache

1.2 Mem-Cache

内存中的Cache

Memcached：一个内存cache软件，就看成hashmap用

memcached如何优化DB的查询?

先去cache中查找，如果没有，再去DB中查找：

分析：

我们认为database中的才是最正确的

A：database set时可能会出现问题，但没有太大问题，比如你发了一条微博，显示没成功。

但是如果database成功了，cache更新失败了，那么用户得到的数据都是更新之前的数据。

B：如果cache成功了，但是database没有成功，cache里存的不是database中的真正数据，看成脏数据。

C：如果cache delete成功了，但是database更新失败，没关系，还可以去database里面读取

D：如果database 修改成功了，但是cache失败了，此时用户从cache读取的就是之前的数据

相比之下C比较好，但是C也存在一定的问题：

比如第8行和第9行程序，如果我们刚刚获取了user但是这个时候有另一个进程修改了用户信息，此时再更新cache中的user信息就是旧数据了。

1.3 Cache Aside 和 Cache Through

Cache Aside

前面代码中的例子就是Cache Aside，需要分别对Cache和DB进行操作，这样就会造成不同步的后果

Cache Through

2. Service 服务

2.1. Authentication Service

如何实现用户登录和保持登录
会话表，session

用户Login之后
- 创建一个session对象
- 并把seesion_key作为cookie返回给浏览器
- 浏览器将该值记录在浏览器的cookie中
- 用户每次想服务器发送的访问，都会自动带上该网站所有的cookie
- 此时服务器检测到cookie中的session_key是有效的，就认为用户登录了
用户logout之后，从session table中删除对应的数据
Session table存在哪？
- 数据库？
- 缓存？
- 都可以？
- 理论上都可以的，但是如果只存在cache中，一旦负责cache的机器宕机，就会有很多用户同时需要重新登录，所以存在数据库里更好一些，如果访问用户多的话，可以用cache做优化。

2.2. Friendship Service

好友关系分类

单向好友关系（微博、twitter、Instagram）

双向好友关系（微信、Facebook）
- 方案一：存为两条信息，A关注了B，B关注了A
- 方案二：存为一条信息，但查询的时候需要查询两次
好友关系所涉及的操作非常简单，基本都是Key-value
- 求某个user的所有关注对象
- 求某个user的所有粉丝
- A关注B → 插入一条数据
- B关注A → 删除一条数据

2.3. 小结

对于用户系统而言：
- 写很少
- 读很多
写操作很少，意味着
- 从QPS角度来说，一台mysql就够了
读操作很多，意味着
- 可以使用memcached进行读操作的缓存优化
进一步的问题，如果读写操作都很多怎么办？
- 方法一：使用更多的数据库服务器分摊流量
- 方法二：使用像Redis这样的读写操作都很快的Cache-through型数据库
  - Memcached是一个Cached-aside型的database,Client需要自己负责管理Cache-miss时的数据的loading

3. Storage 数据库的选取

3.1. 数据库的选取原则SQL vs NoSQL

大部分情况用SQL和noSQL都可以
需要支持transaction的话不能选用NoSQL

什么是transaction？（交易）

transaction需要数据处理同时成立，比如在银行转账，A转给B10元，需要A-10和B+10同时成立
SQL型的数据库比较成熟，可以帮你做很多事，但是NoSQL很多事都要亲力亲为，比如序列化，多级索引
如果想省点服务器获得更高的性能，NoSQL更好，硬盘型的NoSQL比SQL一般要快10倍以上

3.2. 好友关系的存储

存在SQL
存在NoSQL

3.3. 以Cassandra为例剖析经典的NOSQL数据结构

Cassandra是一个三层结构(三元组结构)的NoSQL数据库:

插入数据：insert(row_key,column_key,value)

第一层：row_key
- 又称为hash_key，cassandra会根据这个key计算一个hash值，然后决定这条数据存在哪
- 是传统我们所说的key-value中的key
- 任何查询都需要带上这个key，但无法进行range query
- 最常用的row_key:uer_id
第二层：column_key
- 是排序的，可以进行range query
- 可以按column指定顺序排序，支持按column范围查询query(row_key,column_start,column_end)
- 可以是复合值，比如是一个timestamp+user_id的组合
第三层：value
- 一般是string
- 如果需要存很多信息的话，可以自己做序列化

SQL vs NoSQL

SQL的一条数据以行为单位，取出整个row作为一条数据
SQL的column实在Schema中事先指定好的，不能随意添加。
NoSQL的column是动态的，无限大，可以随意添加
一条数据以grid为单位，row_key + column_key + value = 一条数据
只需要提前定义好column_key本身的格式（是int还是int+string）

Cassandra存储friendship

重要的信息，需要频繁查的信息不能放在value中，要放在column_key中

Cassandra存储NewsFeed

将create_time存在column_key中可以按时间排序

4. How to scale? 单点失效

100M用户存在一台mysql数据库存的下，Storage没问题

通过Cache优化读操作之后，只有300QPS的写，QPS也没有问题

还有什么问题？

单点失效 Simgle Point Failure

万一某一台数据库挂了，短暂的挂：网站不可用了，彻底挂了：数据全部丢失

需要做sharding和Replica

4.1. Sharding 数据拆分

按照一定的规则，将数据拆分成不同的部分，保存在不同的机器上
这样就算某个机器挂了，也不会导致网站100%不可用。

4.1.1. Sharding in SQL vs NoSQL

SQL自身不带Sharding功能，需要手动实现

以Cassandra为代表的NoSQL大多自带Sharding

这就是为什么发明NoSQL

4.1.2. 纵向拆分（Horiaontal Sharding）

简单的纵向切分：

user table 放一台数据库
Friendship Table 放一台数据库
Message Table 放一台数据库

复杂的纵向切分：

比如User Table里有如下信息：
- Email
- Username
- Password
- push_preference
- avatar
一般email/username/password不会经常变动，而push_preference,avatar变动频率较高
可以把这样的一张表拆分成两个表，User Table 和User Profile Table
- 将这两张表放在两台机器上
- 如果UserprofileTable挂了，不会影响user的正常登录操作

实际上就是将table按column进行切分，存储在不同的机器上

缺点：如果数据量很大，有很多很多个用户，纵向拆分之后，仍然很大

4.1.3. 横向拆分（核心）

一个粗暴的想法：

假如拆分Friendship Table，假设有10台数据库的机器，可以想到按照from_user_id%10来进行查分，这样做有什么问题？

假设10台机器不够用了，现在买了一台新机器，原来的%10变成了%11，几乎所有的数据都需要进行位置大迁移！！！！

数据迁移造成的问题：

慢，牵一发而动全身
前一期间，服务器压力增大，容易宕机
容易造成数据不一致

如何解决？

一致性Hash算法

更具体的内容听说在下一节，哈哈

4.2. Replica 数据备份

通常的做法是：一式三份（重要的事情说三遍）
Replica同时还能分摊读请求

剩下的内容听说也在下一节，哈哈

5. 缓存淘汰算法：

缓存调度算法，缓存页面调度算法：先分配一定的页面空间，使用页面的时候首先去查询空间是否有该页面的缓存，如果有的话直接拿出来，如果没有的话先查询，如果页面空间没有满的时候，使用新页面的时候，就释放旧的页面空间，把新页面缓存起来，以便下次使用同样的页面的时候方便调用。

伪代码如下：

def getUser(user_id):
	user = cache.get(user_id)
    if user :
      return user
    user = database.get(user_id)
    cache.set(key, user)
    return user
  
def setUser(user):
  cache.delete(user.user_id)
  database.set(user)

cache 一般是有有效期的，也就是如果缓存中这个数据过期了，那就从缓存中清理出去。而cache 的实现过程和淘汰机制不同，会导致不同的性能表现。常见的就是IFIO，LRU，LFU缓存过期策略。

FIFO(First In First Out) : 先进先出。淘汰掉很久以前进来的数据，而新数据等到之后再淘汰。也就是一个队列。
LRU (Least recently used) : 最近最少使用。淘汰最近不适用的数据
LFU (Least frequently used) : 最近使用次数最少。淘汰掉使用次数最少的页面。

5.1. FIFO

按照“先进先出（First In，First Out）”的原理淘汰数据，正好符合队列的特性，数据结构上使用队列Queue来实现。

如下图：

新访问的数据插入FIFO队列尾部，数据在FIFO队列中顺序移动；
淘汰FIFO队列头部的数据；

5.2. LRU Cache

（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”，因此优先将最近没有被访问的数据删掉。

最常见的实现是使用一个链表保存缓存数据，详细算法实现如下：

新数据插入到链表头部；

每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
当链表满的时候，将链表尾部的数据丢弃。

leetcode题目： LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Follow up:
Could you do both operations in O(1) time complexity?

Example:
> LRUCache cache = new LRUCache( 2 /* capacity */ );
>
> cache.put(1, 1);
> cache.put(2, 2);
> cache.get(1);       // returns 1
> cache.put(3, 3);    // evicts key 2
> cache.get(2);       // returns -1 (not found)
> cache.put(4, 4);    // evicts key 1
> cache.get(1);       // returns -1 (not found)
> cache.get(3);       // returns 3
> cache.get(4);       // returns 4
>

简单的说，就是保证基本的get和set的功能的同时，还要保证最近访问(get或put)的节点保持在限定容量的Cache中，如果超过容量则应该把LRU(近期最少使用)的节点删除掉。

思路：

题目要求利用LRU缓存淘汰机制，在 $O(1)$ 时间复杂度下实现缓存的加入和删除操作

代码：

【九章系统设计】从用户系统理解数据库和缓存