V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
simonlu9
V2EX  ›  程序员

社交权限类似于朋友圈权限,遇到以下场景你会怎样设计

  •  
  •   simonlu9 · 2022-08-08 10:34:05 +08:00 · 1576 次点击
    这是一个创建于 598 天前的主题,其中的信息可能已经有所发展或是发生改变。

    需要如下,用户发布的动态可分为 自己可看,朋友可看,指定用户可看,公开 这几种

    场景 1 ,朋友访问他人主页动态,要显示可看的动态条数,

    解决方案:一条条判断,过滤可看,效率比较低

    场景 2 朋友访问他人的点赞动态,要显示可看的动态条数

    解决方案:a->b->(c,d,e,f,g) 要这样查找,过滤可看条数

    场景 3 ,话题要显示数量,推荐的话题中针对于当前用户要显示 比如 李米的猜想(35),速度激情(32),当中也要权限判断

    解决方案:一条条判断,过滤可看,效率比较低

    场景 4: 搜索也要做权限判断,elasticsearch 真的无能为力

    目前没有很好的解决方案,不知道怎样优化,主要这个数字要准确,推拉 feed 我觉得大材小用,目前用户量真的不多,个人觉得没必要

    12 条回复    2022-08-09 11:42:32 +08:00
    stevefan1999
        1
    stevefan1999  
       2022-08-08 11:32:46 +08:00
    肯定是用圖數據庫(neo4j 之類) 然後做動態權限推導
    placeholder
        2
    placeholder  
       2022-08-08 12:45:16 +08:00
    1 楼说的有道理,反正用户也不多,先上,再说后面的
    wxf666
        3
    wxf666  
       2022-08-08 18:22:09 +08:00
    关系数据库新手求问,这样设计,性能会很差吗?

    用户动态权限信息表『主键:「作者 ID ,权限类型 TINYINT ,允许用户 ID 」,时间,动态 ID 』

    (假设使用 MySQL 的 Innodb 引擎 Dynamic 或 Compact 行格式,则该表的叶节点中,每行记录占 35 字节)


    场景一,按时间倒序,获取访问他人主页时,应该能看到的「动态 ID 」列表

    select 动态 ID
    from 用户动态权限信息表
    where 作者 ID = <他人 ID>
      and (权限类型 = <公开> or
       (权限类型 = <指定> and 允许用户 ID = <自己 ID>) or
       (exists <他人和自己是好友> and 权限类型 = <朋友>))
    order by 时间 desc;


    假设此表 B+ 树有 3 ~ 4 层高,前两层容易被缓存,且都是随机插入,即每个叶节点只有一半可用(能存约 234 行)

    如果应能看到他人主页 公开、指定自己、朋友可见『各』 1W 条动态,对于此条查询,我设想会发生的硬盘 IO 次数:


    1. 花 1 ~ 2 次 IO ,查询其他表,来确定 <他人和自己是好友>

    2. 查询 <公开>、<指定><自己 ID>、<朋友可见> 每种类型的前 234 条记录,各花费 1 ~ 2 次 IO (从树根向叶子查)

    往后每查询 234 条,再花费 1 次 IO (叶子是双向链表)。则总计 3 * ( 1~2 + ceil(10000 / 234)) = 132 ~ 135 次 IO


    总结:若某人有(除自己可见外)各种类型『共』 3W 条动态,为获得这些动态 ID 列表,需读取硬盘 130 多次

    如果固态 16KB IOPS 有 13W ,那每秒最多可查询 1000 个类似这样的人的所有动态 ID 列表

    不知算得对不对
    simonlu9
        4
    simonlu9  
    OP
       2022-08-08 19:36:57 +08:00
    @wxf666 基本上是可行的,查询性能估计要建立 showWith 索引和 user_id 索引,两者可可能联合索引,只是多了一步他人是否为好友,空间换时间,可用推来解决,我自己是没用 mysql,直接上 elasticsearch 查出来,然后再一条条过滤,效率极低,现在可以试着用户如果发非公开动态的时候,采用推模式,把动态先推给有权限的人,缓存成列表,然后查询的时候加上条件为
    公开&&可看 ID 列表,就可以解决上面的几个问题
    wxf666
        5
    wxf666  
       2022-08-08 22:18:39 +08:00
    @simonlu9 诶,突然发现,主键设成那样,不就一堆重复的了。。脑子瓦特了

    应该是『主键:「作者 ID ,权限类型 TINYINT ,允许用户 ID ,动态 ID 」,时间 』

    但叶子节点的结论不变(因为还是 35 字节 / 行)


    你说的『 showWith ,user_id 』索引,是『权限类型,作者 ID 』索引的意思吗?
    simonlu9
        6
    simonlu9  
    OP
       2022-08-09 08:57:15 +08:00
    @wxf666 对的,但是这这样设计解决不了 3 和 4 的问题,只能解决查看他人主页的问题
    simonlu9
        7
    simonlu9  
    OP
       2022-08-09 08:58:20 +08:00
    @wxf666 一般主键不建议这样设计的,唯一索引就可以了
    wxf666
        8
    wxf666  
       2022-08-09 10:03:41 +08:00
    @simonlu9 这样设计,会有何问题呢?

    另外,你是在动态表上,建唯一索引吗?

    这样:动态表『主键「动态 ID 」,唯一索引「权限类型,作者 ID 」,允许用户 IDs JSON ,动态内容 TEXT ,…… 』?

    或「允许用户 IDs 」独立成一个「用户动态指定可见表」『主键「动态 ID ,允许用户 ID 」』?
    simonlu9
        9
    simonlu9  
    OP
       2022-08-09 10:20:12 +08:00
    比如说查看他人主页,彼此是好友关系 sql 如下,select * from moment where user_id = ? and show_with in('OPEN' ,'FRIEND') or at_user_id in(当前用户 ID) ,分析这条语句,主要走索引的是 userId,主键如果设那么长考虑插入时候分裂情况,第二个允许用户( at_user_id )最好是建另外一个表,字符串查找不建议
    wxf666
        10
    wxf666  
       2022-08-09 11:18:25 +08:00
    @simonlu9

    > 主键如果设那么长考虑插入时候分裂情况

    我 3 楼的设计,直接按照『最差情况』,全部『随机插入』,叶节点『全裂成一半』考虑的


    > 允许用户( at_user_id )最好是建另外一个表,字符串查找不建议

    我打完下面这堆,才看到你的回复。最后计算,也大体验证你所说,『单独表』更可能比『字符串查找』快




    如果是我 8 楼所认为的那样设计,那么:

    唯一索引『主键「权限类型,作者 ID 」,动态 ID 』,叶节点每行记录 14 字节。

    随机插入情况下,一个叶节点一半空间可用,可存约 585 行。



    再拿 3 楼的 3W 条动态+1W 条<指定><他人 ID>可见动态(这对 3 楼的设计无影响,且合情合理),计算下硬盘 IO:


    1. 花 1 ~ 2 次 IO ,查询其他表,来确定 <他人和自己是好友>

    2. 查询 <公开>、<朋友可见> 每种类型的前 585 条记录,各花费 1 ~ 2 次 IO 。往后每 585 条,再花费 1 次 IO 。

    3. 查询 <指定> 类型,和第 2 步类似,但还要确定自己是否在权限内:


    3.1 「允许用户 IDs 」 JSON

    每条动态,都要花 1 ~ 2 次 IO (偏向 2 ~ 3 次,此表很容易变深)回『动态表』,获取「允许用户 IDs 」,然后 find_in_set 或 json 函数确定。

    假设『动态表』每行记录 0.5KB (不大吧),顺序插入情况下,叶子节点预留 1/16 空间,每个叶子节点可存 30 行

    运气好,用户连发 30 条动态,全在一个叶子节点里,能命中缓存 29 次。运气差,无法命中缓存


    3.2 『用户动态指定可见表』

    每条动态,都要花 1 ~ 2 次 IO ,exists

    此表叶节点每行记录 26 字节,随机插入情况下,一半空间可用,可存约 315 行。

    运气好,用户连发 315 条动态,且每条动态都只指定一人可见,则可全在一个叶节点里。反之分散各处,无法命中缓存



    final. 总计:1~2 + 2 * (1~2 + ceil(10000 / 585)) + (1~2 + ceil(20000 / 585) + …) = 75 ~ 79 + …

    若用 3.1:75~79 + (ceil(20000 / 30) ~ 20000) * 1~2 = 742 ~ 40079 次 IO

    若用 3.2:75~79 + (ceil(20000 / 315) ~ 20000) * 1~2 = 139 ~ 40079 次 IO

    如果固态 16KB IOPS 有 13W ,那每秒最多可查询 3 ~ 1000 个类似这样的人的所有动态 ID 列表



    看起来,是因为每条动态,都要验证权限,导致的回表 /查表次数太多

    当然,指定某人可见的动态,应该不会这么多。可以算出个阈值,超过此值这种设计不划算



    我 3 楼那样的设计,是将同类动态的行记录(某人公开、某人私有、某人朋友可见、某人指定他人 1 ,某人指定他人 2 ,……),尽可能凑在一起,实现:

    1. 能迅速跳过某些类别的所有行记录(如,跳过某人私有、某人指定非自己的其他所有人)
    2. 能迅速定位到某一类的第一行
    3. 能利用上 B+ 树的叶子节点双向链表的特性,迅速遍历完某一类的余下行


    这样的表,用文件系统类比,就是(如下),要啥类别,就直接读那个文件(叶子节点),直接跳过其他所有:

    用户动态权限文件夹 /
     用户 A/
      公开动态 ID 列表.txt
      私有….txt
      朋友可见….txt
      指定可见 /
       用户 B 可见….txt
       用户 C 可见….txt
     用户 B/
      ……
    wxf666
        11
    wxf666  
       2022-08-09 11:28:39 +08:00
    @simonlu9 不对,「权限类型,作者 ID 」咋能成唯一索引呢。。只能是索引


    另外,如果是这样设计,或许你的会比我 3 楼 的设计快:

    动态表『主键「动态 ID 」,索引「权限类型,作者 ID ,允许用户 IDs JSON 」,动态内容 TEXT ,…… 』


    因为每条动态不用回『动态表』查权限,也不用查『其他表』是否存在该权限了

    「允许用户 IDs 」字符串操作,应该比一次 IO ,快几个数量级吧
    wxf666
        12
    wxf666  
       2022-08-09 11:42:31 +08:00
    @simonlu9 再修正一下,10 楼 3.2 计算,这个表更应该是顺序插入,那预留 1/16 后,叶节点可存约 590 行,

    若用 3.2:75~79 + (ceil(20000 / 590) ~ 20000) * 1~2 = 109 ~ 40079 次 IO

    如果固态 16KB IOPS 有 13W ,那每秒最多可查询 3 ~ 1200 个类似这样的人的所有动态 ID 列表
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   961 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 35ms · UTC 21:46 · PVG 05:46 · LAX 14:46 · JFK 17:46
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.