本文主要对设计方案进行一些思考及测试,思考结果的正确性无法保证,测试结果保证正确.

前言

在两个月的某次面试中,被问到了如何设计微博的关注关系,当时只考虑了mysql等关系型数据库的方案,回答的不是很让人满意.面试结束后即决定要研究一下这一块,但是之后太忙 ,就到了现在,趁着周六无聊,做一些思考以及测试.

这种关注关系的需求十分常见,大到微博,Ins,Twitter,小到很多论坛,博客,都有这个需求.为了方便举例与理解,这里都以微博为例(天天刷).

需求分析

常用微博的胖友们,肯定知道两个人之间有这么几种关系.

  1. A关注了B.
  2. B关注了A.
  3. A和B互相关注.
  4. 毫无关系.

那么针对这些关系有常见的以下几个需求:

  1. 查看某个用户的关注列表.
  2. 查看某个用户的粉丝列表.
  3. 查看某个人的互相关注列表,(好友圈的定义就是和你互相关注的人的微博会在这里出现.
  4. 判断两个用户之间的关系.(在微博中,你查看别人主页时左下角的集中状态).
  5. 获取两个人的共同关注.(微博中查看别人的关注列表时会有这个栏目,展示你和他共同关注的一些人).

设计的结构要实现以上的需求.

关系型数据库实现(Mysql)

这个就比较简单了,将关注这一个关系作为一种实体存储下来.数据表结构(follow)如下:

id from_uid to_uid ts
1 A B time1
2 B C time1
3 A C time1

这种存储在功能上市勉强可以实现的.

  1. 查看某个用户的关注列表.
  1. select to_uid from follow where from_uid = 'A' order by ts

可以拿到用户A的关注列表,按照时间关注的时间进行排序.

  1. 查看用户的粉丝列表
  1. select from_uid from follow where to_uid = 'C' order by ts

可以拿到用户C的粉丝列表,根据关注的时间进行排序.

  1. 查看某个人的互相关注列表

上面两个语句的交集,在mysql中:

  1. select to_uid from follow where to_uid in (select from_uid from follow where to_uid= 'A') and and from_uid = 'A'

进行了一次子查询且语句中有in,当数据量稍大的时候查询效果太差劲了.

  1. 这个比较复杂一些,很难通过一条sql查询得到.
  2. 获取两个人的共同关注.
  1. select to_uid from follow where from_uid = 'A' and to_uid in (select to_uid from follow where from_uid = 'B')
  3. 可以拿到A和B的共同关注列表.

使用MySQL当然是可以实现的,而且查询的复杂性还不是最难搞的问题.

难搞的是,当数据量直线上升,使用mysql就必须要进行分库分表,这时候分表的策略就很难定了.

使用follow表的id来进行分表,那么久意味着对每一个用户的关注或者粉丝查询都需要从多个表查到数据再进行聚合,这个操作不科学.

使用uid进行分表,就意味着有数据冗余,且没有办法避免热点数据问题,比如微博很多大v有几千万的粉丝,这些数据放在一张表中仍然很拥挤,而且这样分表,表的数量会很多.

在参考文章微博关系服务与Redis的故事一文中,微博确实是经历了mysql这个阶段之后,选择了Redis.使用Redis中的hash结构来存储关系数据,我们模拟一下实现.

Redis的hash来实现

在该文中说,使用了hash数据结构,每个用户对应两个hash表,一个存储关注,一个存储粉丝.

还是上面数据表格中的三条数据,存储在redis中表现为:

  1. follow_A:
  2.     B:ds1
  3.     C:ds2
  4. fan_A:
  5.     null;
  7. follow_B:
  8.     C:ds3
  9. fan_B:
  10.     A:ds1
  12. follow_C:
  13.     null;
  14. fans_C:
  15.     B:ds3
  16.     A:ds2

这样在在获取列表的时候,可以直接使用hgetall来获取,十分简单.但是仍要注意一下问题,hgetall是一个时间复杂度为O(n)的命令,当用户的关注列表或者粉丝列表太大的时候,仍然有超时的可能.

用代码来实现以下上面那五个需求.如下(java):

  1. public class Followtest {
  3.     static String FOLLOW_PREFIX = "follow_";
  4.     static String FANS_PREFIX = "fans_";
  6.     static Jedis jedis = new Jedis();
  8.     public Set<String> getFollows(String id) {
  9.         return jedis.hgetAll(FOLLOW_PREFIX + id).keySet();
  10.     }
  12.     public Set<String> getfans(String id) {
  13.         return jedis.hgetAll(FANS_PREFIX + id).keySet();
  14.     }
  16.     // 获取互相关注的列表
  17.     public Set<String> getTwoFollow(String id) {
  18.         Set<String> follows = getFollows(id);
  19.         Set<String> fans = getfans(id);
  20.         follows.retainAll(fans);
  21.         return follows;
  22.     }
  24.     // 判断from - > to 的关系
  25.     public RelationShip getRelationShip(String from, String to) {
  26.         boolean isFollow = getFollows(from).contains(to);
  27.         boolean isFans = getfans(from).contains(to);
  29.         if (isFollow) {
  30.             if (isFans) {
  31.                 return RelationShip.TWOFOLLOW;
  32.             }
  33.             return RelationShip.FOLLOW;
  34.         }
  35.         return isFans ? RelationShip.FANS : RelationShip.NOONE;
  36.     }
  38.     // 获取共同关注列表
  39.     public Set<String> publicFollow(String id1, String id2) {
  40.         Set<String> id1Follow = getFollows(id1);
  41.         Set<String> id2Follow = getfans(id2);
  43.         id1Follow.retainAll(id2Follow);
  45.         return id1Follow;
  46.     }
  49.     public enum RelationShip {
  50.         FOLLOW, FANS, TWOFOLLOW, NOONE;
  51.     }
  53. }

使用Redis的sorted set 实现

此外,还可以使用sorted set 来实现,将关注或者粉丝的id放在set中,将其关注时间作为分值,这样也可以获取到一个有序的关注列表.

上面几条数据的存储格式为:

  1. follow_A:
  2.         B-ds1
  3.         C-ds2
  4. fans_A: null
  6. follow_B:
  7.         C-ds3
  8. fans_B:
  9.         A-ds1
  11. follow_C:null;
  12. fan_C: 
  13.         B-ds3
  14.         A-ds2

java代码如下:

  1. public class FollowTest1 {
  3.     static String FOLLOW_PREFIX = "follow_";
  4.     static String FANS_PREFIX = "fans_";
  6.     static Jedis jedis = new Jedis();
  8.     public Set<String> getFollows(String id) {
  9.         return jedis.zrange(FOLLOW_PREFIX + id, 0, -1);
  10.     }
  12.     public Set<String> getfans(String id) {
  13.         return jedis.zrange(FANS_PREFIX + id, 0, -1);
  14.     }
  16.     // 获取互相关注的列表
  17.     public Set<String> getTwoFollow(String id) {
  18.         Set<String> follows = getFollows(id);
  19.         Set<String> fans = getfans(id);
  20.         follows.retainAll(fans);
  21.         return follows;
  22.     }
  24.     // 判断from - > to 的关系
  25.     public Followtest.RelationShip getRelationShip(String from, String to) {
  26.         boolean isFollow = getFollows(from).contains(to);
  27.         boolean isFans = getfans(from).contains(to);
  29.         if (isFollow) {
  30.             if (isFans) {
  31.                 return Followtest.RelationShip.TWOFOLLOW;
  32.             }
  33.             return Followtest.RelationShip.FOLLOW;
  34.         }
  35.         return isFans ? Followtest.RelationShip.FANS : Followtest.RelationShip.NOONE;
  36.     }
  38.     // 获取共同关注列表
  39.     public Set<String> publicFollow(String id1, String id2) {
  40.         Set<String> id1Follow = getFollows(id1);
  41.         Set<String> id2Follow = getfans(id2);
  43.         id1Follow.retainAll(id2Follow);
  45.         return id1Follow;
  46.     }
  49.     public enum RelationShip {
  50.         FOLLOW, FANS, TWOFOLLOW, NOONE;
  51.     }
  52. }

主要是在获取列表的时候由hgetall转而使用了zrange.

当然,在获取某两个列表的交集的时候,可以直接使用ZINTERSTORE,这个命令会将指定的集合的交集存在一个新的集合中,然后可以获取结果集合的所有元素.

但是考虑到这个命令会额外造成一部分内存的占用,而这份内容并没有太多缓存的价值,因为用户的关注列表会经常变化,所以实现方式可以根据实际情况做一些调整.

总结

  1. 使用mysql的话在数据量较小的时候勉强可以,在数据量逐渐增大,mysql的分库分表方案将很难抉择.
  2. 使用Redis的hash结构来存储,需要在查询时hgetall之前还要加一层缓存,否则hgetall会有一些局部超时.
  3. 使用Redis的sorted-set结构,个人觉得目前是比较好的,因为sorted-set可以直接获取交集,且可以使用zscan命令来逐页获取数据,比较契合大部分的使用场景.

参考文章

https://www.infoq.cn/article/weibo-relation-service-with-redis