高性能访客记录系统如何设计？
需求要点
每个用户都有自己的个人空间，当有其他用户来访问的时候，需要添加访客记录，并且更新为最新的访客，这里设计到一个坑，如果存在这个用户的访问记录需要更新用户的最后访问时间。那这个需求在技术维度来说，有什么特点吗？
先想10秒钟，再接着往下看！！！有什么设计要点呢？
用户的访客记录一定要缓存，要不然怎么抗住大并发呢?
由于最新的访客记录变化非常快，要有一种能快速添加新数据，删除老数据的数据结构。
缓存的篇章今日暂且不说，说一下以上的第二点，也就引出了今日数据结构主角：链表。
链表
链表百科：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表属于线性结构。
链表分类
1. 单链表：链表中的元素的指向只能指向链表中的下一个元素或者为空，元素之间不能相互指向。也就是一种线性链表。
public class Node<T>
{
//当前节点的数据元素
public T Data { get; set; }
//当前节点的下一个元素
public Node<T> NextNode { get; set; }
}
2. 双向链表：每个链表元素既有指向下一个元素的指针，又有指向前一个元素的指针，其中每个结点都有两种指针。
public class Node<T>
{
//当前节点的前一个节点
public Node<T> PreNode { get; set; }
//当前节点的数据元素
public T Data { get; set; }
//当前节点的下一个元素
public Node<T> NextNode { get; set; }
}
3. 循环链表：指的是在单向链表和双向链表的基础上，将两种链表的最后一个结点指向第一个结点从而实现循环。
特性
1. 元素的数量可以随时扩充。由于链表在物理的存储单元上是非连续的，这就早就了它天生的优势，我的节点可以在任意符合要求的地方分配内存。
2. 添加元素：
单链表：
当在一个位置N之后插入新元素的时候，单链表首先把当前位置N的元素的Next指针指向新的元素，然后新的元素的Next指针指向N+1位置的元素。当然如果是在首位置插入新元素，只需要把新元素的Next指针指向链表的首元素即可，同理，如果要在单链表尾部插入新元素，只需要把单链表的尾部元素的Next指针指向新元素。至于循环单链表，无所谓首元素和尾元素之分。
双向链表：
在位置N之后添加新元素和单链表原理类似，原理也是修改元素的指针指向。但是这里有一个不同，双向链表要修改前后元素(N位置和N+1位置)和新元素三个Node的指针，所以略微麻烦一点。
3. 删除元素：
单链表：
当要删除位置N的元素的时候，只需要把N-1位置元素的Next指针指向N+1即可。
双向链表：
当要删除位置N的元素的时候，需要修改N-1位置元素的Next指针指向N+1元素，同时还要修改N+1位置元素的Pre指针指向N-1元素。
4. 查找元素：
由于链表的元素在内存中并非连续，所以不能像数组那样拥有O（1）的查找时间复杂度，只能是通过首元素去遍历链表，所以时间复杂度为O（n）
程序设计
给你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 不太了解的同学可以度娘一下。
优化
1. 阅读到这里你是否感觉哪里有问题呢？是的，就是链表元素的查找，由于只能是遍历，所有链表查找元素的时间复杂度为O（n），那有没有办法优化呢？那就是我们以后要讲的另外一种数据结构了。
2. 空间的访客记录是以时间为维度的倒序排列，所以业务以及DB时间列的设计类型推荐为UTC时间戳long类型，毕竟long类型在多数语言中比datetime类型占用内存要小很多。
3. 无论是否使用缓存，用户的访问记录都是需要DB来持久化的，当有大量的请求的时候，我们可以利用某种机制来批量持久化到DB，而不是一个请求就访问数据库一次。
4. 当对空间的访客记录实时性要求不是很高的时候，我们可以每10秒或者5秒更新缓存，也就是批量更新缓存，这比单条加锁更新缓存效果更好。
把用户访问记录优化到极致
但是，在用户访问记录的缓存中怎么来判断是否有当前用户的记录呢？链表虽然是我们这个业务场景最主要的数据结构，但并不是当前这个问题最好的解决方案，所以我们需要一种能快速访问元素的数据结构来解决这个问题？那就是今天我们要谈一谈的——散列表。
散列表
散列表（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)。如下图所示：
2. 链地址法（拉链法）
拉链法属于一种最常用的解决散列值冲突的方式。基本思想是数组的每个元素指向一个链表，当散列值冲突的时候，在链表的末尾增加新元素。查找的时候同理，根据散列值定位到数组位置之后，然后沿着链表查找元素。如果散列函数设计的非常糟糕的话，相同的散列值非常多的话，散列表元素的查找会退化成链表查找，时间复杂度退化成O（n）。
3. 再散列法
这种方式本质上是计算多次散列值，那就必然需要多个散列函数，在产生冲突时再使用另一个散列函数计算散列值，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。
4. 建立一个公共溢出区
至于这种方案网络上介绍的比较少，一般应用的也比较少。可以这样理解：散列值冲突的元素放到另外的容器中，当然容器的选择有可能是数组，有可能是链表甚至队列都可以。但是无论是什么，想要保证散列表的优点还是需要慎重考虑这个容器的选择。
写在后面
1. 这里需要再强调一次，散列表底层依赖的是数组按照下标访问的特性（时间复杂度为O(1）），而且一般散列表为了避免大量冲突都有装载因子的定义，这就涉及到了数组扩容的特性：需要为新数组开辟空间，并且需要把元素copy到新数组。如果我们知道数据的存储量或者数据的大概存储量，在初始化散列表的时候，可以尽量一次性分配足够大的空间。避免之后的数组扩容弊端。事实证明，在内存比较紧张的时候，优先考虑这种一次性分配的方案也要比其他方案好的多。
2. 散列表的寻址方案中，有一种特殊情况：如果我寻找到数组的末尾仍然无空闲位置，怎么办呢？这让我想到了循环链表，数组也一样，可以组装一个循环数组。末尾如果无空位，就可以继续在数组首位继续搜索。
3. 关于散列表元素的删除，我觉得有必要说一说。首先基于拉链方式的散列表由于元素在链表中，所有删除一个元素的时间复杂度和链表是一样的，后续的查找也没有任何问题。但是寻址方式的散列表就不同了，我们假设一下把位置N元素删除，那N之后相同散列值的元素就搜索不出来了，因为N位置已经是空位置了。散列表的搜索方式决定了空位置之后的元素就断片了....这也是为什么基于拉链方式的散列表更常用的原因之一吧。
4. 在工业级的散列函数中，元素的散列值做到尽量平均分布是其中的要求之一，这不仅仅是为了空间的充分利用，也是为了防止大量的hashCode落在同一个位置，设想在拉链方式的极端情况下，查找一个元素的时间复杂度退化成在链表中查找元素的时间复杂度O（n），这就导致了散列表最大特性的丢失。
5. 拉链方式实现的链表中，其实我更倾向于使用双向链表，这样在删除一个元素的时候，双向链表的优势可以同时发挥出来，这样可以把散列表删除元素的时间复杂度降低为O（1）。
6. 在散列表中，由于元素的位置是散列函数来决定的，所有遍历一个散列表的时候，元素的顺序并非是添加元素先后的顺序，这一点需要我们在具体业务应用中要注意。
Net Core c# 代码
有几个地方需要再强调一下：
1. 在当前项目中用的分布式框架为基于Actor模型的Orleans，所以我每个用户的访问记录不必担心多线程问题；
2. 我没用使用hashtable这个数据容器，是因为hashtable太容易发生装箱拆箱的问题；
3. 使用双向链表是因为查找到了当前元素，相当于也查找到了上个元素和下个元素，当前元素的删除操作时间复杂度可以为O(1)。
class UserViewInfo
{
//用户ID
public int UserId { get; set; }
//访问时间，utc时间戳
public int Time { get; set; }
//用户姓名
public string UserName { get; set; }
}
class UserSpace
{
//缓存的最大数量
const int CacheLimit = 1000;
//这里用双向链表来缓存用户空间的访问记录
LinkedList<UserViewInfo> cacheUserViewInfo = new LinkedList<UserViewInfo>();
//这里用哈希表的变种Dictionary来存储访问记录，实现快速访问，同时设置容量大于缓存的数量限制，减小哈希冲突
Dictionary<int, UserViewInfo> dicUserView = new Dictionary<int, UserViewInfo>(1250);
//添加用户的访问记录
public void AddUserView(UserViewInfo uv)
{
//首先查找缓存列表中是否存在，利用hashtable来实现快速查找
if (dicUserView.TryGetValue(uv.UserId, out UserViewInfo currentUserView))
{
//如果存在，则把该用户访问记录从缓存当前位置移除，添加到头位置
cacheUserViewInfo.Remove(currentUserView);
cacheUserViewInfo.AddFirst(currentUserView);
}
else
{
//如果不存在，则添加到缓存头部 并添加到哈希表中
cacheUserViewInfo.AddFirst(uv);
dicUserView.Add(uv.UserId, uv);
}
//这里每次都判断一下缓存是否超过限制
if (cacheUserViewInfo.Count > CacheLimit)
{
//移除缓存最后一个元素，并从hashtable中删除,理论上来说，dictionary的内部会两个指针指向首元素和尾元素，所以查找这两个元素的时间复杂度为O（1）
var lastItem = cacheUserViewInfo.Last.Value;
dicUserView.Remove(lastItem.UserId);
cacheUserViewInfo.RemoveLast();
}
}
}作者：菜菜，一个奔走在通往互联网更高之路的工程师，热衷于互联网技术。目前就职于某互联网教育公司，应用服务端主要负责人。拥有10年+互联网开发经验，热衷于高性能、高并发、分布式技术领域的研究，主要工作语言为C#和Golang 。
声明：本文为作者投稿，版权归其个人所有，责编郭芮。
【完】
热 文 推 荐
☞ 被V神点赞, 我是如何用五子棋打败以太坊排名最高的应用的？ |人物志
print_r('点个好看吧！');
var_dump('点个好看吧！');
NSLog(@"点个好看吧！");
System.out.println("点个好看吧！");
console.log("点个好看吧！");
print("点个好看吧！");
printf("点个好看吧！\n");
cout << "点个好看吧！" << endl;
Console.WriteLine("点个好看吧！");
fmt.Println("点个好看吧！");
Response.Write("点个好看吧！");
alert("点个好看吧！")
echo "点个好看吧！"