专栏首页呼延类似微博等社交软件中用户关注关系的存储实现方案遐想

类似微博等社交软件中用户关注关系的存储实现方案遐想

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

前言

在两个月的某次面试中,被问到了如何设计微博的关注关系,当时只考虑了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. 查看某个用户的关注列表.
select to_uid from follow where from_uid = 'A' order by ts

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

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

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

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

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

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. 获取两个人的共同关注.
select to_uid from follow where from_uid = 'A' and to_uid in (select to_uid from follow where from_uid = 'B')

可以拿到A和B的共同关注列表.

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

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

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

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

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

Redis的hash来实现

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

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

follow_A:
	B:ds1
	C:ds2
fan_A:
	null;

follow_B:
	C:ds3
fan_B:
	A:ds1

follow_C:
	null;
fans_C:
	B:ds3
	A:ds2

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

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

public class Followtest {

    static String FOLLOW_PREFIX = "follow_";
    static String FANS_PREFIX = "fans_";

    static Jedis jedis = new Jedis();

    public Set<String> getFollows(String id) {
        return jedis.hgetAll(FOLLOW_PREFIX + id).keySet();
    }

    public Set<String> getfans(String id) {
        return jedis.hgetAll(FANS_PREFIX + id).keySet();
    }

    // 获取互相关注的列表
    public Set<String> getTwoFollow(String id) {
        Set<String> follows = getFollows(id);
        Set<String> fans = getfans(id);
        follows.retainAll(fans);
        return follows;
    }

    // 判断from - > to 的关系
    public RelationShip getRelationShip(String from, String to) {
        boolean isFollow = getFollows(from).contains(to);
        boolean isFans = getfans(from).contains(to);

        if (isFollow) {
            if (isFans) {
                return RelationShip.TWOFOLLOW;
            }
            return RelationShip.FOLLOW;
        }
        return isFans ? RelationShip.FANS : RelationShip.NOONE;
    }

    // 获取共同关注列表
    public Set<String> publicFollow(String id1, String id2) {
        Set<String> id1Follow = getFollows(id1);
        Set<String> id2Follow = getfans(id2);

        id1Follow.retainAll(id2Follow);

        return id1Follow;
    }


    public enum RelationShip {
        FOLLOW, FANS, TWOFOLLOW, NOONE;
    }
    
}

使用Redis的sorted set 实现

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

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

follow_A:
        B-ds1
        C-ds2
fans_A: null

follow_B:
        C-ds3
fans_B:
        A-ds1

follow_C:null;
fan_C: 
        B-ds3
        A-ds2

java代码如下:

public class FollowTest1 {

    static String FOLLOW_PREFIX = "follow_";
    static String FANS_PREFIX = "fans_";

    static Jedis jedis = new Jedis();

    public Set<String> getFollows(String id) {
        return jedis.zrange(FOLLOW_PREFIX + id, 0, -1);
    }

    public Set<String> getfans(String id) {
        return jedis.zrange(FANS_PREFIX + id, 0, -1);
    }

    // 获取互相关注的列表
    public Set<String> getTwoFollow(String id) {
        Set<String> follows = getFollows(id);
        Set<String> fans = getfans(id);
        follows.retainAll(fans);
        return follows;
    }

    // 判断from - > to 的关系
    public Followtest.RelationShip getRelationShip(String from, String to) {
        boolean isFollow = getFollows(from).contains(to);
        boolean isFans = getfans(from).contains(to);

        if (isFollow) {
            if (isFans) {
                return Followtest.RelationShip.TWOFOLLOW;
            }
            return Followtest.RelationShip.FOLLOW;
        }
        return isFans ? Followtest.RelationShip.FANS : Followtest.RelationShip.NOONE;
    }

    // 获取共同关注列表
    public Set<String> publicFollow(String id1, String id2) {
        Set<String> id1Follow = getFollows(id1);
        Set<String> id2Follow = getfans(id2);

        id1Follow.retainAll(id2Follow);

        return id1Follow;
    }


    public enum RelationShip {
        FOLLOW, FANS, TWOFOLLOW, NOONE;
    }
}

主要是在获取列表的时候由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

ChangeLog

2019-05-10 完成

以上皆为个人所思所得,如有错误欢迎评论区指正。

欢迎转载,烦请署名并保留原文链接。

联系邮箱:huyanshi2580@gmail.com

更多学习笔记见个人博客——>呼延十

var gitment = new Gitment({ id: '类似微博等社交软件中用户关注关系的存储实现方案遐想', // 可选。默认为 location.href owner: 'hublanker', repo: 'blog', oauth: { client_id: '2297651c181f632a31db', client_secret: 'a62f60d8da404586acc965a2ba6a6da9f053703b', }, }) gitment.render('container')



本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • String Stringbuilder Stringbuffer异同

    字符串在编程中使用的非常频繁,同时又是面试中的常见题型,那么我们的对字符串相关类String,StringBuilder,StringBuffer的理解真的正确...

    呼延十
  • Guava中的一些增强集合类

    写了好多和Java集合类有关的文章,学习了好多集合类的用法,有没有感觉还是有一些常见的需求集合类没有办法满足呢?需要自己使用Java集合中的类去实现,但是这种常...

    呼延十
  • 后缀数组(suffix array)在字符串匹配中的应用

    首先抛出一个问题: 给定300w字符串A, 之后给定80w字符串B, 需要求出 B中的每一个字符串, 是否是A中某一个字符串的子串. 也就是拿到80w个boo...

    呼延十
  • LintCode 恢复IP地址题目分析

    [ "255.255.11.135", "255.255.111.35" ] (顺序无关紧要)

    desperate633
  • Swift3.0 - 扩展

    b.如果想要在定义协议的时候,不指定变量名称,在实现协议的时候,再去设定变量类型,应该怎么写?

    酷走天涯
  • Spring Data(二)查询

    查询的构建机制对于Spring Data的基础是非常有用的。构建的机制将截断前缀find…By、read…By、query…By、count…By、get…By...

    小忽悠
  • Ruby程序区分运行来源

    当我们在写模块的时候,或多或少需要直接运行这个文件也可以执行一些方法,但是这样对于当这个模块被require或者include时,显得不好,在ruby里,有没有...

    技术小黑屋
  • 求求你大蕉别学了之 Flink No.127

    Flink ,为纯粹的流计算为生的一个大数据项目,玩一波先。跟 Spark 有什么区别呢?其实就一个区别,Spark 永远是批量处理,Flink 可以批量也可以...

    大蕉
  • Spring Boot 实现定时任务的动态增删启停等管理!

    在spring boot项目中,可以通过@EnableScheduling注解和@Scheduled注解实现定时任务,也可以通过SchedulingConfig...

    业余草
  • 17-Flink消费Kafka写入Mysql

    王知无

扫码关注云+社区

领取腾讯云代金券