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

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

  1. 大部分情况用SQL和noSQL都可以

  2. 需要支持transaction的话不能选用NoSQL

    什么是transaction?(交易)

    transaction需要数据处理同时成立,比如在银行转账,A转给B10元,需要A-10和B+10同时成立

  3. SQL型的数据库比较成熟,可以帮你做很多事,但是NoSQL很多事都要亲力亲为,比如序列化,多级索引

  4. 如果想省点服务器获得更高的性能,NoSQL更好,硬盘型的NoSQL比SQL一般要快10倍以上

3.2. 好友关系的存储

  1. 存在SQL

  2. 存在NoSQL

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

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

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

  1. 第一层:row_key
    • 又称为hash_key,cassandra会根据这个key计算一个hash值,然后决定这条数据存在哪
    • 是传统我们所说的key-value中的key
    • 任何查询都需要带上这个key,但无法进行range query
    • 最常用的row_key:uer_id
  2. 第二层:column_key
    • 是排序的,可以进行range query
    • 可以按column指定顺序排序,支持按column范围查询query(row_key,column_start,column_end)
    • 可以是复合值,比如是一个timestamp+user_id的组合
  3. 第三层: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,几乎所有的数据都需要进行位置大迁移!!!!

数据迁移造成的问题:

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

如何解决?

一致性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缓存过期策略。

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

5.1. FIFO

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

如下图:

img

  1. 新访问的数据插入FIFO队列尾部,数据在FIFO队列中顺序移动;
  2. 淘汰FIFO队列头部的数据;

5.2. LRU Cache

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

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

img

  1. 新数据插入到链表头部;
  1. 每当缓存命中(即缓存数据被访问),则将数据移到链表头部;
  2. 当链表满的时候,将链表尾部的数据丢弃。

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缓存淘汰机制,在 时间复杂度下实现缓存的加入和删除操作

代码:

5.2. LFU Cache