首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >HashMap加双向链表构建IM系统会话列表内存模型

HashMap加双向链表构建IM系统会话列表内存模型

作者头像
普通程序员
发布2019-10-23 11:47:32
1.1K0
发布2019-10-23 11:47:32
举报
文章被收录于专栏:普通程序员普通程序员

IM系统都有一个会话列表页,如下图所示

当某个会话收到或者发送消息后,该会话会排到会话顶部。由于支持消息漫游,服务器端需要保存每个用户客户端的会话顺序。如何才能在海量消息收发的场景下,准确记录各个客户端的会话顺序呢?

可以采用一个类似LRU内存淘汰的算法来解决这个问题。采用HashMap与LinkList(链表)组合的方式(如下图)。

图中左边是一个Map结构,可以通过sessionid快速索引到具体session(会话)数据,session数据以链表形式存储(图中右边部分)。

当这个会话收到或者发送消息时,通过Map在O(1)的时间定位到具体会话数据,然后修改会话数据的链表指针,将此会话数据放到链表头部(top)。完成整个操作时间复杂度是常量,可视为O(1)级别。效率很高。

当其他设备拉取会话列表时,按照链表顺序,分批返回会话列表即可。

实际研发层面,考虑到数据持久化以及研发效率,可选用Redis的SortedSet结构,时间复杂度为O(lg N),N为会话数量。适当控制保存会话的数量,这个复杂度完全可以接受。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2017-07-05,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 普通程序员 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
云数据库 Redis
腾讯云数据库 Redis(TencentDB for Redis)是腾讯云打造的兼容 Redis 协议的缓存和存储服务。丰富的数据结构能帮助您完成不同类型的业务场景开发。支持主从热备,提供自动容灾切换、数据备份、故障迁移、实例监控、在线扩容、数据回档等全套的数据库服务。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档