2025年5月30日 星期五 1:44pm

高性能访客记录系统如何设计？

640?wx_fmt=gif

640?wx_fmt=png

640?wx_fmt=png

 

 

640?wx_fmt=png

人工智能学习路线+实战训练

https://edu.csdn.net/topic/ai30?utm_source=csdn_bw

需求要点

每个用户都有自己的个人空间，当有其他用户来访问的时候，需要添加访客记录，并且更新为最新的访客，这里设计到一个坑，如果存在这个用户的访问记录需要更新用户的最后访问时间。那这个需求在技术维度来说，有什么特点吗？

 

先想10秒钟，再接着往下看！！！有什么设计要点呢？

 

  • 用户的访客记录一定要缓存，要不然怎么抗住大并发呢?

  • 由于最新的访客记录变化非常快，要有一种能快速添加新数据，删除老数据的数据结构。

 

缓存的篇章今日暂且不说，说一下以上的第二点，也就引出了今日数据结构主角：链表。

 

 

640?wx_fmt=png

链表

 

 

链表百科：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表属于线性结构。

 

链表分类

 

1. 单链表：链表中的元素的指向只能指向链表中的下一个元素或者为空，元素之间不能相互指向。也就是一种线性链表。

 

640?wx_fmt=png

 

public class Node

    {

        //当前节点的数据元素

        public T Data { get; set; }

        //当前节点的下一个元素

        public Node NextNode { get; set; }

    }

 

 

2. 双向链表：每个链表元素既有指向下一个元素的指针，又有指向前一个元素的指针，其中每个结点都有两种指针。

 

640?wx_fmt=png

public class Node

    {

        //当前节点的前一个节点

        public Node PreNode { get; set; }

        //当前节点的数据元素

        public T Data { get; set; }

        //当前节点的下一个元素

        public Node NextNode { get; set; }

    }

 

 

3. 循环链表：指的是在单向链表和双向链表的基础上，将两种链表的最后一个结点指向第一个结点从而实现循环。

 

640?wx_fmt=png

640?wx_fmt=png

 

特性

 

1. 元素的数量可以随时扩充。由于链表在物理的存储单元上是非连续的，这就早就了它天生的优势，我的节点可以在任意符合要求的地方分配内存。

 

2. 添加元素：

 

单链表：

 

当在一个位置N之后插入新元素的时候，单链表首先把当前位置N的元素的Next指针指向新的元素，然后新的元素的Next指针指向N+1位置的元素。当然如果是在首位置插入新元素，只需要把新元素的Next指针指向链表的首元素即可，同理，如果要在单链表尾部插入新元素，只需要把单链表的尾部元素的Next指针指向新元素。至于循环单链表，无所谓首元素和尾元素之分。

640?wx_fmt=png

双向链表：

 

在位置N之后添加新元素和单链表原理类似，原理也是修改元素的指针指向。但是这里有一个不同，双向链表要修改前后元素(N位置和N+1位置)和新元素三个Node的指针，所以略微麻烦一点。

640?wx_fmt=png

3. 删除元素：

 

单链表：

 

当要删除位置N的元素的时候，只需要把N-1位置元素的Next指针指向N+1即可。

 

640?wx_fmt=jpeg

 

双向链表：

 

当要删除位置N的元素的时候，需要修改N-1位置元素的Next指针指向N+1元素，同时还要修改N+1位置元素的Pre指针指向N-1元素。

 

640?wx_fmt=png

 

4. 查找元素：

 

由于链表的元素在内存中并非连续，所以不能像数组那样拥有O（1）的查找时间复杂度，只能是通过首元素去遍历链表，所以时间复杂度为O（n）

 

 

640?wx_fmt=png

程序设计

 

 

给你10秒回到X总的需求中来。通过对链表的介绍，我们该选择哪种链表呢？这里我先说一下我的思路，如有错误请指正：

 

1. 当一个访客进入个人空间的首页时，大多数情况下，访客记录只需要缓存前100条或者200条即可，也就是说这个场景是存在热点数据的，80%（甚至更高）的请求命中在最近100条访客数据上，很少人会去查看很久以前的记录。所以基于占用内存空间上的考虑，我决定缓存最近的100条访客数据。

 

2. 假设我用链表缓存了前100条数据，其中在非首位置有一条访客A的记录，此时A又访问的这个用户空间，我需要把A的记录移到首位置，这个过程经历了删除A数据，在首位置添加A数据。假如A开始的位置是N，我在删除N位置数据的时候，需要查找N-1的位置元素修改其指针指向，如果是单链表由于当前位置N的元素中没有N-1位置元素的信息，所有需要重新遍历链表。如果是双向链表呢，位置N的元素中保存了位置N-1的元素，所以没有必要在重新遍历链表了，这也是双向链表对比单链表的优势，虽然内存占用上多了一个指针的内存大小，但是在实际的应用场景中更为常用。所以我选择双向链表。删除操作和添加操作时间复杂度都是O（1）.

 

3. 对同一个空间的访问，必然存在锁和多线程的问题。所以我在选择框架的时候优先选择了基于Actor模型的框架。避免了在同一个用户空间上加锁的操作。

 

4. 由于基于Actor模型的框架，所以我没有采用类似Redis这样的进程外缓存，而是采用了进程内缓存，毕竟网络传输的速度再快也比内存操作要慢的多。应用层的Actor服务天然支持分布式。如果对actor 不太了解的同学可以度娘一下。

 

 

640?wx_fmt=png

优化

 

 

1. 阅读到这里你是否感觉哪里有问题呢？是的，就是链表元素的查找，由于只能是遍历，所有链表查找元素的时间复杂度为O（n），那有没有办法优化呢？那就是我们以后要讲的另外一种数据结构了。

 

2. 空间的访客记录是以时间为维度的倒序排列，所以业务以及DB时间列的设计类型推荐为UTC时间戳long类型，毕竟long类型在多数语言中比datetime类型占用内存要小很多。

 

3. 无论是否使用缓存，用户的访问记录都是需要DB来持久化的，当有大量的请求的时候，我们可以利用某种机制来批量持久化到DB，而不是一个请求就访问数据库一次。

 

4. 当对空间的访客记录实时性要求不是很高的时候，我们可以每10秒或者5秒更新缓存，也就是批量更新缓存，这比单条加锁更新缓存效果更好。

 

 

640?wx_fmt=png

把用户访问记录优化到极致

 

 

但是，在用户访问记录的缓存中怎么来判断是否有当前用户的记录呢？链表虽然是我们这个业务场景最主要的数据结构，但并不是当前这个问题最好的解决方案，所以我们需要一种能快速访问元素的数据结构来解决这个问题？那就是今天我们要谈一谈的——散列表。

 

640?wx_fmt=png

640?wx_fmt=png

 

 

640?wx_fmt=png

散列表

 

 

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

 

散列表其实可以约等于我们常说的Key-Value形式。散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。为什么要用数组呢？因为数组按照下标来访问元素的时间复杂度为O（1），不明白的同学可以参考菜菜以前的关于数组的文章。

 

既然要按照数组的下标来访问元素，必然也必须考虑怎么样才能把Key转化为下标。这就是接下来要谈一谈的散列函数。

 

散列函数

 

散列函数通俗来讲就是把一个Key转化为数组下标的黑盒。散列函数在散列表中起着非常关键的作用。散列函数，顾名思义，它是一个函数。我们可以把它定义成hash(key)，其中 key 表示元素的键值，hash(key) 的值表示经过散列函数计算得到的散列值。

 

那一个散列函数有哪些要求呢？

 

  • 散列函数计算得到的值是一个非负整数值；

  • 如果 key1 = key2，那hash(key1) == hash(key2) ；

  • 如果 key1 ≠ key2，那hash(key1) ≠ hash(key2) 。

 

简单说一下以上三点，第一点：因为散列值其实就是数组的下标，所以必须是非负整数（>=0），第二点：同一个key计算的散列值必须相同。重点说一下第三点，其实第三点只是理论上的，我们想象着不同的Key得到的散列值应该不同，但是事实上，这一点很难做到。我们可以反证一下，如果这个公式成立，我计算无限个Key的散列值，那散列表底层的数组必须做到无限大才行。像业界比较著名的MD5、SHA等哈希算法，也无法完全避免这样的冲突。当然如果底层的数组越小，这种冲突的几率就越大。

 

所以一个完美的散列函数其实是不存在的，即便存在，付出的时间成本，人力成本可能超乎想象。

 

散列冲突

 

既然再好的散列函数都无法避免散列冲突，那我们就必须寻找其他途径来解决这个问题。

 

1. 寻址

 

如果遇到冲突的时候怎么办呢？方法之一是在冲突的位置开始找数组中空余的空间，找到空余的空间然后插入。就像你去商店买东西，发现东西卖光了，怎么办呢？找下一家有东西卖的商家买呗。不管采用哪种探测方法，当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位。我们用装载因子（load factor）来表示空位的多少。

 

散列表的装载因子 = 填入表中的元素个数 / 散列表的长度

 

装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。假设散列函数为 f=(key%1000)。如下图所示：

 

640?wx_fmt=png

 

2. 链地址法（拉链法）

 

拉链法属于一种最常用的解决散列值冲突的方式。基本思想是数组的每个元素指向一个链表，当散列值冲突的时候，在链表的末尾增加新元素。查找的时候同理，根据散列值定位到数组位置之后，然后沿着链表查找元素。如果散列函数设计的非常糟糕的话，相同的散列值非常多的话，散列表元素的查找会退化成链表查找，时间复杂度退化成O（n）。

 

3. 再散列法

 

这种方式本质上是计算多次散列值，那就必然需要多个散列函数，在产生冲突时再使用另一个散列函数计算散列值，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。

 

4. 建立一个公共溢出区

 

至于这种方案网络上介绍的比较少，一般应用的也比较少。可以这样理解：散列值冲突的元素放到另外的容器中，当然容器的选择有可能是数组，有可能是链表甚至队列都可以。但是无论是什么，想要保证散列表的优点还是需要慎重考虑这个容器的选择。

 

 

 

640?wx_fmt=png

写在后面

 

 

1.  这里需要再强调一次，散列表底层依赖的是数组按照下标访问的特性（时间复杂度为O(1）），而且一般散列表为了避免大量冲突都有装载因子的定义，这就涉及到了数组扩容的特性：需要为新数组开辟空间，并且需要把元素copy到新数组。如果我们知道数据的存储量或者数据的大概存储量，在初始化散列表的时候，可以尽量一次性分配足够大的空间。避免之后的数组扩容弊端。事实证明，在内存比较紧张的时候，优先考虑这种一次性分配的方案也要比其他方案好的多。

 

2.  散列表的寻址方案中，有一种特殊情况：如果我寻找到数组的末尾仍然无空闲位置，怎么办呢？这让我想到了循环链表，数组也一样，可以组装一个循环数组。末尾如果无空位，就可以继续在数组首位继续搜索。

 

3.  关于散列表元素的删除，我觉得有必要说一说。首先基于拉链方式的散列表由于元素在链表中，所有删除一个元素的时间复杂度和链表是一样的，后续的查找也没有任何问题。但是寻址方式的散列表就不同了，我们假设一下把位置N元素删除，那N之后相同散列值的元素就搜索不出来了，因为N位置已经是空位置了。散列表的搜索方式决定了空位置之后的元素就断片了....这也是为什么基于拉链方式的散列表更常用的原因之一吧。

 

4.  在工业级的散列函数中，元素的散列值做到尽量平均分布是其中的要求之一，这不仅仅是为了空间的充分利用，也是为了防止大量的hashCode落在同一个位置，设想在拉链方式的极端情况下，查找一个元素的时间复杂度退化成在链表中查找元素的时间复杂度O（n），这就导致了散列表最大特性的丢失。

 

5.  拉链方式实现的链表中，其实我更倾向于使用双向链表，这样在删除一个元素的时候，双向链表的优势可以同时发挥出来，这样可以把散列表删除元素的时间复杂度降低为O（1）。

 

6.  在散列表中，由于元素的位置是散列函数来决定的，所有遍历一个散列表的时候，元素的顺序并非是添加元素先后的顺序，这一点需要我们在具体业务应用中要注意。

 

 

640?wx_fmt=png

 Net Core c# 代码

 

 

有几个地方需要再强调一下：

 

1.  在当前项目中用的分布式框架为基于Actor模型的Orleans，所以我每个用户的访问记录不必担心多线程问题；

2.  我没用使用hashtable这个数据容器，是因为hashtable太容易发生装箱拆箱的问题；

3.  使用双向链表是因为查找到了当前元素，相当于也查找到了上个元素和下个元素，当前元素的删除操作时间复杂度可以为O(1)。

 

  1.  class UserViewInfo
  2.     {
  3.         //用户ID
  4.         public int UserId { get; set; }
  5.         //访问时间，utc时间戳
  6.         public int Time { get; set; }
  7.         //用户姓名
  8.         public string UserName { get; set; }
  9.     }
  1. class UserSpace
  2.     {
  3.         //缓存的最大数量
  4.         const int CacheLimit = 1000;
  5.         //这里用双向链表来缓存用户空间的访问记录
  6.         LinkedList<UserViewInfo> cacheUserViewInfo = new LinkedList<UserViewInfo>();
  7.         //这里用哈希表的变种Dictionary来存储访问记录，实现快速访问，同时设置容量大于缓存的数量限制，减小哈希冲突
  8.         Dictionary<int, UserViewInfo> dicUserView = new Dictionary<int, UserViewInfo>(1250);
  9.  
  10.         //添加用户的访问记录
  11.         public void AddUserView(UserViewInfo uv)
  12.         {
  13.             //首先查找缓存列表中是否存在，利用hashtable来实现快速查找
  14.             if (dicUserView.TryGetValue(uv.UserId, out UserViewInfo currentUserView))
  15.             {
  16.                 //如果存在，则把该用户访问记录从缓存当前位置移除，添加到头位置
  17.                 cacheUserViewInfo.Remove(currentUserView);
  18.                 cacheUserViewInfo.AddFirst(currentUserView);
  19.             }
  20.             else
  21.             {
  22.                 //如果不存在，则添加到缓存头部 并添加到哈希表中
  23.                 cacheUserViewInfo.AddFirst(uv);
  24.                 dicUserView.Add(uv.UserId, uv);
  25.             }
  26.             //这里每次都判断一下缓存是否超过限制
  27.             if (cacheUserViewInfo.Count > CacheLimit)
  28.             {
  29.                 //移除缓存最后一个元素，并从hashtable中删除,理论上来说，dictionary的内部会两个指针指向首元素和尾元素，所以查找这两个元素的时间复杂度为O（1）
  30.                 var lastItem = cacheUserViewInfo.Last.Value;
  31.                 dicUserView.Remove(lastItem.UserId);
  32.                 cacheUserViewInfo.RemoveLast();
  33.             }
  34.         }
  35.     }

 

作者：菜菜，一个奔走在通往互联网更高之路的工程师，热衷于互联网技术。目前就职于某互联网教育公司，应用服务端主要负责人。拥有10年+互联网开发经验，热衷于高性能、高并发、分布式技术领域的研究，主要工作语言为C#和Golang 。

声明：本文为作者投稿，版权归其个人所有，责编郭芮。

人工智能如何学？

https://edu.csdn.net/topic/ai30?utm_source=csdn_bw

【完】

640?wx_fmt=jpeg

 热 文 推 荐 

开源，二世而亡？

☞郑州没有互联网 | 畅言

☞华为抄袭苹果？

☞ 那些简历造假拿 Offer 的程序员，后来都怎么样了？

☞ 被V神点赞, 我是如何用五子棋打败以太坊排名最高的应用的？ |人物志

☞ 50个最有价值的数据可视化图表（推荐收藏）

一键免费自动AI抠图，效果连PS大哥也点赞！

史上最难的一道Java面试题

 

print_r('点个好看吧！');
var_dump('点个好看吧！');
NSLog(@"点个好看吧！");
System.out.println("点个好看吧！");
console.log("点个好看吧！");
print("点个好看吧！");
printf("点个好看吧！\n");
cout << "点个好看吧！" << endl;
Console.WriteLine("点个好看吧！");
fmt.Println("点个好看吧！");
Response.Write("点个好看吧！");
alert("点个好看吧！")
echo "点个好看吧！"

640?wx_fmt=gif点击阅读原文，输入关键词，即可搜索您想要的 CSDN 文章。

640?wx_fmt=png喜欢就点击“好看”吧！

CSDN
微信公众号
成就一亿技术人
注：本文转载自blog.csdn.net的CSDN资讯的文章"https://blog.csdn.net/csdnnews/article/details/87887803"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！