共享内存RESUME机制综述

Posted on | In

前言

共享内存RESUME机制是指的: 通过将游戏状态数据保存在共享内存中, 当游戏进程crash后通过重启游戏服务器并attach已有的共享内存来恢复游戏状态, 以此达到玩家游戏体验在出现宕机时的连贯性, 提升游戏的容灾能力.

共享内存RESUME出现的背景: 为什么选择共享内存RESUME而不是集群冗余+故障转移

MMOACT相比传统互联网的异同

在web领域中, 业务和数据分离, 从而达成’业务无状态化’, 开发人员专注于业务本身, 状态数据的一致性问题和容灾问题转移到可以较为独立解决的数据存储领域, 这个领域有非常多的论文和解决方案, 以及成熟的服务等.

而对于游戏领域来说, 互联网成熟的解决的方案很难在这个地方应用, 当然 对于外围系统来说, 我们仍然可以按照互联网成熟的解决方案进行布局, 例如聊天系统, 好友系统, 邮件系统, 日志系统, 或者一些游戏中的公会系统等.

MMOACT的特性:

  • CPU计算密集

    • 地图单位扫描选择 命中包围盒碰撞检测 战斗事件响应处理 AI的扫描检测,行为决策, 移动的寻路/碰撞避免/检测等

  • IO密集

    • 视野内所有玩家的事件都要同步所有玩家(理想情况下), 这是一个$O(N^2)$的广播复杂度
    • 大世界内视野范围较为开阔

  • 低延迟响应

    • 在战斗中, 一次攻击动作被拆解成逐帧开启和关闭的 霸体 无敌 攻击窗口 可闪避窗口 可打断窗口等流程片段, 一帧16.7ms
    • 在战斗中每秒平均5~7米的移动距离, 100ms的延迟将会带来一个身位的偏差造成命中失败
    • 弓箭的速度大约每秒50米, 30帧的客户端一帧就有两个身位的偏差
    • 互联网骨干网20ms的延迟 每一点额外的延迟都会给同步带来较为巨大的压力.

  • 共享状态高频读写

    • 战斗单位与战斗单位之间, 战斗单位的模块与模块之间
    • ACT战斗中实时响应判定的AI(大量事件和回调)
    • 装备, 属性, 能量槽, 状态标签与技能和移动之间的相互引用与保证
      • BUFF对属性的修改 标签的装载和卸载 子弹时间的进出等都需要严格保证对称
    • 技能BUFF流程中跨战斗单位跨模块并需要严格保证时序的事件判定与脚本回执等

  • 重业务逻辑,需求易变

    • 业务类型繁多复杂且耦合, 见上栏’共享状态高频读写’

传统互联网特性:

  • 数据规模大 用户量大 并发大
  • 轻业务, 重存储 对数据一致性要求较高
    • 读写改查这几个基本操作可以涵盖绝大部分互联网业务的核心内容
  • 业务较为稳定
  • 延迟不敏感 通常都是秒级以上.
    • google Analytics速度报告中, 网页的平均加载时间为4~8秒 2秒打开网页我们会觉得飞快(秒开)
    • 互动式直播和视频会议的延迟平均1~3秒
    • 苹果支付服务器验证一个支付凭据需要3s-6s
    • 45秒才能看视频

游戏业务的形式化描述:
$$
S_k=\begin{cases}
g(P, C), \qquad if \quad k = 0 \\
t(S_{k-1}, C, I_k), \quad if \quad k \geq 1
\end{cases}
$$

I是游戏状态变化的根本原因的集合 往往是各个玩家(按键)操作
S是游戏状态的集合 由众多状态子集组成

该公式的描述:

  • 游戏在第0个逻辑帧时 根据玩家信息P和游戏配置C 进行初始化运算g 得出初始化状态集合$S_0$
  • 游戏在第k个逻辑帧时 根据前一个状态集合$S_{k-1}$和游戏配置C 根据第k帧收到的外部变化原因集合$I_k$ 进行逻辑t运算 得出第k个逻辑帧新的游戏状态集合$S_k$

大部分互联网核心业务都能很好的进行业务和状态存储上的解耦, 以stateless形式在现有成熟的数据库相关的存储服务之上通过已有的成熟的解决方案来订制解决, 其核心往往是通过牺牲响应速度, 提高解决方案的复杂度来实现大规模高一致性的互联网需求.

(12306的业务也不算复杂 但是难在大规模并发下, 状态之间难以解耦进行传统的分而治之而造成的)

而游戏服务, 很多时候游戏服务可以看成一个复杂的非确定状态机, 有非常庞大的状态集合, 实时响应所有玩家的请求并不断的推演下去, 并且其业务变更非常频繁, 往往是通过牺牲一定程度的可靠性和一致性来做到在有限的开发周期和资源里, 把一个尽可能满足策划设计和玩家体验的游戏做出来.
实际上大部分的游戏项目也都在解决这个问题, 也因此互联网成熟的解决方案, 流行的解决方案 往往很难在游戏项目得到及时的应用, 尽管如此, 在靠近外围的架构和服务节点上, 我们仍然可以追着互联网潮流进行演进, 例如微服务.

附图, MMO技能的基本流程如下:

  • 技能释放条件 –> 判断自身脚本 –>判断目标是否有脚本有则等待执行结果
  • 技能预处理 –> 判定
  • 技能释放成功 –> 判定
  • 技能命中开始扫描目标 –> 是否有反向过滤 –> 等待执行结果
  • 技能遍历所有选中目标
    • 即将对目标发起命中处理 –> 判定
    • 对目标发起命中处理
      • 遍历所有效果
        • 即将对目标产生效果 –> 判定
          • 如果是伤害则有 伤害预处理 – >判定
          • 如果是BUFF则有额外的buff流程判定
        • 已经对目标产生效果 –> 判定
          • 如果是伤害则有 伤害已经处理 –>判定
      • 遍历所有效果完毕
    • 已经对目标执行完命中处理 –> 判定
  • 技能遍历目标发起命中结束
  • 下一段命中
  • 技能即将结束 –> 判定
  • 技能已经结束 –>判定

通常1V1战斗一次可能需要保证时序的同步点大约就有20个 而混战情况下则会有N倍的提升, 在非分布式的情况下, 所有的同步点带来的处理复杂度都是一次分支判定, 但是如果是分布式则会是一次rpc .
如果是共享内存下的消息队列实现(大吞吐) 一次rpc来回则可能有平均10ms的延迟, 那么在不牺牲时序逻辑的情况下, 则可能带来几百ms的巨大延迟.

方案对比和决策

有成功案例的两种做法:

一种不常见的BIGWORLD的做法(冗余系统&故障切换):

  • 以战斗单位进行解耦, 不同的战斗单位可以分布在不同节点

  • 游戏世界不按照场景地图划分, 而是按照战斗单位的负载动态切分

  • 所有单位进行跨物理节点的冗余, 故障后直接切换到备份单位继续战斗

  • 跨节点的战斗, 如果战斗系统同步点过多则不可避免的带来额外的延迟

  • RPC需求让系统变得更为复杂 开发和调试都会带来更多困难

  • 动态负载均衡难以实现

  • 需要面临的技术挑战过大参考资料和技术储备太少

另外一种, 基于共享内存RESUME做法:

  • 状态数据持久化在共享内存中, 进程crash之后数据不丢失
  • 对使用者透明, 状态数据是在本地内存还是共享内存 对C/C++这种语言的使用者来说没有区别
    • 经过完善的合理的包装设计, 可以做到业务人员对’共享内存’无感, 基本上做好状态和逻辑分离即可.
  • 对共享内存上的状态访问读写操作等同本地内存, 无额外性能消耗和处理延迟
  • RESUME后保持业务的连贯性, 对用户体验非常友好
  • 原理简单容易(分阶段)实现, 且每阶段都可验证, 有较多成功案例.

方案差异:

  • 提高可靠性
    • 多点备份 故障转移
      • 可在更多情景下做到可用性 例如网络故障 宕机
      • 可以考虑在小项目或者中台部门进行MVP迭代到一定完成度
    • 快速RESUME
      • 只支持crash情况, 但是根据行业经验 绝大部分情况都是代码bug带来的crash
  • 保障业务连续性
    • 都能做到业务连续性
  • 成本
    • 共享内存RESUME方案无论是在开发阶段还是QA/运维部署等阶段成本都大大低于多点备份+故障转移的做法
  • 团队项目
    • 立项之初团队规模很小 人力资源总预算有限

方案选定:

  • 尽可能的拆分外围服务 以stateless集群+数据库存储方案来实现

    • 例如好友 聊天 邮件等

  • 对无法做到stateless又难以拆分的管理节点和战斗节点进行RESUME设计.

    • World管理节点 战斗场景

可行性分析和验证

隔离业务状态数据与非业务环境数据

第一个问题是, 哪些数据应该放在共享内存中, 哪些数据不能放在共享内存中, 这个问题决定了具体的业务恢复情况.

  • 在游戏业务的RESUME机制中, 我们不做指令级的恢复, 也就是说, 首先 栈数据我们不会存放在共享内存中而是故障时直接丢弃

    • 一旦把栈放在共享内存中, 意味着我们要记录所有的指令状态和序列以及执行情况, 以及这意味着我们在发明一套新的支持resume的vm语言(这种发明有没有现实意义是另外一个新的问题) 而不是在C/C++语言之上resume我们的业务.
    • crash可以发生在任意时刻的代码处理中, 难以避免的产生一些状态错误.
      • 规范: 不能在共享内存中的对象或者内存中 有存在指向任何栈上或者堆上的指针
      • 规范: 不能在共享内存中的对象或者内存中 有存在指向函数或者虚函数的指针 如果无法避免则需要在RESUME的时候恢复为正确的指针
      • 规范: 如非必要, 不能有被栈管理的共享内存资源
        • 例如使用智能指针获取共享内存上的某个对象, 然后经过一段复杂且经常变化的业务代码后release 控制权交给位于共享内存的map进行管理等. 这种情况一旦crash 这个对象无论crash多少次都会被永久挂起.
      • 规范: 尽可能的做好结构和流程的局部化设计, 并且做好兜底设计:
        • 例如 技能错误不影响战斗单位, 战斗单位错误不应该影响其他玩家等
        • 例如, 创建一个技能实例:
          • 获取创建实例的信息
          • 用准备好的信息数据创建一个实例并填充一个基础状态, 再接下来的复杂逻辑中一旦crash, resume之后仍然能检测到技能实例的异常状态或者到期后自动清理
          • 进行新实例创建后的脚本触发, 其他模块的同步调用通知等
        • 例如 技能中修改属性
          • 获取好单位的属性位置, 计算好要修改的值信息等
          • 没有任何错误和异常的话 进行连续的赋值修改等 (这种操作通常不会crash)
          • 执行一些变更通知 或者其他逻辑等
          • 技能实例到期销毁, 根据记录的属性修改记录进行反向恢复
        • 例如技能状态切换过程中出现错误 RESUME后正Tick检测到会再次执行切换操作
    • 规范: 内部分阶段REVIEW新人的代码 检查是否有不符合RESUME或者带来隐患的设计

  • 隔离一些不能resume的三方库或者逻辑

    • 例如PROTOBUF不能做RESUME 那么就需要禁止在任何业务状态中有存储指向pbin的指针, 必须是用时查找读取, 启服初始化时或者RESUME时重新加载.
    • 消息/事件/任务队列等进行逻辑处理时应先标记当前’消息/事件/任务’在队列中已经被处理, 然后执行具体的逻辑. 一旦发生crash后不会重复执行该任务, 跳过故障流程
      • 如果需要关注处理结果则应该有对应的处理超时机制, resume后等待一段时间后进行超时处理

    隔离业务状态和业务逻辑(数据和逻辑分离)

    一般来说, 我们在写可resumable的代码时要注意自己使用到的状态是不是放在共享内存中以及如何聚合在resumable框架中的, 但是为了减少开发人员的犯错机会以及心智负担, 我们可以参考ECS框架来单独的聚合所有resumable状态数据, 或者更进一步的, 所有状态数据都通过schema以单独的描述文件进行生成, 通过这种明确的定义和聚合形式, 做到让开发人员难以写出错误的代码, 以及可以更准确的跟踪resumable结构的变更(有利于热修复的风险控制).

    • 业务状态和逻辑代码拆分后, 可以直观的观测和追溯状态的拓扑结构变更
    • 共享内存RESUME机制是对代码热更友好的, 如果考虑线上代码热更, 则方便进行数据结构的拓扑对比
    • 编写业务时因状态数据单独存放, 会起到’业务状态是放在共享内存而不是本地内存’的提醒作用, 减少心智负担.
    • 方便进行REVIEW检查

    最小化验证, FIRST GLOBAL STATE

    基础原理为, 定义单独的抽象类作为单个服务节点的索引起点(框架), 该节点下所有共享内存上的状态均以对象,静态内存数组等数据成员的形式聚合为该类的数据成员.
    在启服时候通过简单的静态计算算出来总大小并分配共享内存, 以此跑在共享内存之上, 在RESUME时则查找该共享内存并把框架类的指针指向共享内存区域.

    • 基础的shmget/shmat流程

      • 启服创建共享内存, 并把global state指针指向共享内存完成构造初始化
      • 启服绑定共享内存, 并把global state指针指向共享内存完成绑定和resume回调等

    • 所有游戏从global state这个Server类中聚合 例如

      • global state: scene server
        • map<场景>
          • 场景:
            • 地图大小
            • 怪物列表
        • map<玩家>
          • 玩家:
            • 技能模块
              • 技能
              • buff
              • 标签
            • 移动模块
        • 事件队列

    解决方案和实践

    RESUME状态重建/恢复的基础问题

    • 代码段因代码变更或者ASLR随机化发生改变
      • 函数指针变化 虚函数位置变化
    * 共享内存地址不固定情况下每次shmat会导致共享内存映射的地址发生变化 * 记录的地址指针错误 * 只能使用地址无关的容器 例如std::array
    • 共享内存地址固定会因ASLR的HEAP/MMAP随机化而导致RESUME后冲突
      • 关闭ASLR并估算一个不会冲突的位置 (版本更新, 新的so库 都会带来小的改变 但是只要能启服成功 RESUME也会成功)
      • 不关闭ASLR并寻找一个不会被ASLR影响到区间

    基础问题以及解决策略

    共享内存RESUME方案需要配合一定的代码规范, 或者说共享内存方案本身需要让系统具备状态可恢复这种机制上, 一定会多多少少带来代码和设计上的约束, 我们会通过以下策略尽量减少这套机制对业务层的感知和对开发人员的限制.

    • 数据结构和算法的地址无关化设计
      • 避免出现指针, 特别是可能指向系统堆栈, 代码段等非共享内存位置的指针.
      • 能使用相对偏移量代替地址的尽量用偏移量
        • 例如下标 长度等信息
      • 尽量使用静态容器代替包含有动态内存分配的容器, 如果没有就实现一个
        • 使用数组方案, 或者std::array以及手动实现的static array来代替std::vector
      • 业务上尽量使用无地址的解决方案
        • 例如现在有个事件队列, 我们手动定义事件枚举A,B,C,D
          • 在入队时, 我们根据需求push进去对应的事件ID和参数
          • 在出队时, 我们获取到事件ID进行switch case 事件枚举: 并调用指定的处理函数
    • 固定虚拟地址空间中共享内存的映射地址
      • 让所有指向共享内存中的数据地址指针在RESUME后直接可用, 从共享内存RESUME整体出发降低系统的复杂度.
      • 需要关闭ASLR或者固定一个不会出现地址冲突问题的地址

    • 间接地址方案, 隔离运行环境的真实地址

      • 基础思路为, 不直接使用和保存(函数)地址, 而是在第一次启动初始化时或者RESUME启动时把要使用的地址预先注册到某个公共位置, 使用时从这个位置读取正确的地址进行使用.
      • 情景1: 参考网络消息序列化的一般手段: 注册消息号和处理函数的映射关系
        • 函数类型相同

    • 地址重定位方案, 直接修改失效的地址为当前执行环境的有效地址

      • 基础思路为: 记录下每个使用某(函数)地址的位置, 在RESUME后使用正确的(函数)地址替换掉记录中旧的记录
      • 例如我们记录下使用中所有带虚函数的对象位置, 在RESUME后对该对象的虚表指针进行替换.

    • 面向RESUME机制的手动编程, 不算兜底的兜底方案

      • 对于可以复用的底层框架代码或者容器代码, 我们会针对性的进行流程和框架上的封装, 或者提供支持RESUME容器实现来减少业务层对RESUME系统的感知以提高业务开发效率.
      • 但是无可避免的, 我们还是会遇到一些复杂的问题因为过于业务具体没有复用的价值, 或者无法预期进行集成, 因此一定程度上, 我们需要保留一定的开放性让用户自己去实现初始化和RESUME代码
        • 例如我们记录下所有包含OnResume方法的有效对象, 在RESUME后执行这些对象的OnResume方法来完成一些用户自定义的RESUME方案
          • 例如一些战斗单位绑定了RVO, 而这个RVO库并不运行在共享内存上, 那么这些战斗单位需要在OnResume里面进行重置操作或者根据当前的坐标移动信息重新绑定RVO库

    附: 在随机化的ASLR中确立确定性的地址空间

    - 用户空间布局 -
    0x0
    保留区
    代码段(PLT代码表部分)
    代码段
    数据段(GOT) 只读
    数据段(.got.plt) 惰性加载机制
    数据段(Data)
    数据段(BSS)
    堆空间(Heap)
    ↓
    未分配区域
    ↑
    内存映射区域(mmap)
    栈空间(进程栈)
    TASK_SIZE

    地址空间配置随机加载（英语：Address space layout randomization，缩写ASLR，又称地址空间配置随机化、地址空间布局随机化）是一种通过随机放置进程关键数据区域的地址空间来防止攻击者能可靠地跳转到内存的特定位置, 从而防范这类内存损坏漏洞被利用的计算机安全技术, 例如常见的Return-to-libc攻击.

    这些数据区域一般包括代码段 数据段 堆区 栈区 mmap 动态库等, 其中涉及代码段的随机一般需要代码位置无关化的支持(PIC PIE机制), 不同版本的操作系统和内核版本, 在ASLR的实现上以及默认系统选项都会有细节的不同, 在X86-64位最高等级下, 我们可以找到不会被随机到但是可以通过mmap建立有效映射的(0x0000 7F00 0000 0000 ~ 0x0000 5655 5555 5555)大约44T的地址空间(128T的1/3), 前者为mmap开始位置 后者为HEAP(BRK)开始位置.

    在实践中, 我们把共享内存的位置设置在靠中间的位置, 给系统mmap和heap留有足够的空间. 例如 0x0000 7000 0000 000, 这样和MMAP区域有17T的间隙, 充分安全, 无论ASLR开什么级别RESUME多少次 始终不会和共享内存选定的地址产生冲突

    细节内核代码分析见:linux内存布局和ASLR下的可分配地址空间

    对象池和基础容器等通用性设计

    对象池(定长内存池+对象分配回收接口)的基础设计

    设计目的:

    • 静态内存一次性分配, 动态分配和回收固定大小的内存
    • 解决虚表失效问题
      • 解决单继承和多重继承问题
    • 提供自定义的OnResume接口进行自定义的恢复 提高易用性和扩展性
      • 向用户层抛出一个自定义解决方案
    • 提供FOREACH的分批轮询机制 平滑负载峰值

    实现方案:
    接口层实现:

    • 类型枚举定义
    • 注册(绑定)类型信息, 对象大小, 对象上限数量, 是否有虚表需要恢复, 是否需要支持OnResume
    • 对象分配和回收接口

    对象池管理器(管理头):

    • FREE索引ID(FREE LIST), CHUNK大小(包含fence-next-id和obj), 数量上限, 虚表标志, OnResume标志, 起始地址偏移, BITMAP使用标志位图位置等

    对象池:

    • FENCE-HEAD-OBJ 数组

    分配和回收流程:
    分配:

    • POP FREE HEAD指向的CHUNK
    • 进行原地构造
    • 设置BITMAP的使用标记

    回收:

    • 根据指针换算成CHUNK的索引ID
    • 检测BITMAP的使用标记并移除标记
    • 执行析构函数
    • PUSH到FREE LIST中(设置为新的FREE HEAD)

    FOREACH轮询流程:
    按STEP数量遍历BITMAP使用标记并执行对象指定的轮询回调

    • 例如对于一个每秒执行一次OnTick的对象, 可以拆分成100ms执行1/10的使用中对象的OnTick, 分10次在1秒内完成. 这样可以平滑CPU的负载, 并且不会出现迭代器失效等隐患问题

    INIT和OnResume流程
    一般放在对象池中的对象可以正在的构造函数中去完成初始化处理, Init这种二次初始化由用户去定义即可.
    如果该对象需要在Resume中做一些自定义的检测或者恢复处理, 则需要定义该回调并进行标记

    地址无关的容器实现

    这里放在一起说, 第一优先级是数组 其次是map和list.

    • 数组容器的实现

      • 一般情况下可以用std::array或者原生数组来开发, 本身是地址无关的可以直接RESUME
      • 为了更方便和更通用, 实现了STATIC ARRAY, 接口和std::vector基本对齐, 但是元素数量上限是确定的

    • MAP容器

      • hash map的实现比较简单, 第一个版本中首先提供支持的就是hash map
      • 基本做法是分配上限大小的桶并以FREE LIST形式串联, 再分配上限大小的桶位(指向桶索引ID的编号数组), 在插入KV结构时hash到对应的桶位, 如果有冲突则在该位置串联. 查找删除时候过程相似.
      • std::map未实现 通过基于共享内存分配器实现的allocator直接对std::map进行支持

    • LIST容器

      • 相比数组容器, 这个提供了稳定的迭代器和搞性能的插入删除性能

    小结

    通过框架和通用底层的数据结构实现, 以及对象池, 链表 数组 HASH_MAP等
    已经实现了非常易用的一套基于共享内存RESUME的框架和系统

    整体结构为两部分:

    | GLOBAL SERVER | OBJECT POOLS |

    在服务的main入口通过对共享内存的启动BOOT封装, 完成自动化的共享内存的创建和恢复机制.
    开发人员在开发新的服务节点时, 通过继承GLOBAL SERVER把所有数据以静态的形式聚合在GLOBAL SERVER下即可, 对于涉及到动态分配和管理的, 使用提供好的map/list/array即可.

    需要注意的其他问题

    • RESUME检测和恢复时间带来的超时问题和业务连贯性问题
      • RESUME恢复时间
        • 进程crash检测间隔
        • 共享内存上的状态恢复(通常非常快)
        • 被隔离的代码和模块的重新加载和初始化
          • 不在共享内存上的资源重新load
      • 被时间影响的功能
        • 大量移动包在RESUME成功之前无法处理消耗造成
          • 逻辑服没有移动包 战斗服是产生移动包的位置 其他节点结构简单不容易宕机
        • 异步请求出现超时

    通用性上的挑战: 在共享内存上构建通用内存管理器

    • 移植stl的容器而非去独立实现(一劳永逸的兜底方案)
      • 实现shm allocator
    • 移植更多的三方库到共享内存上
      • 通用的内存分配器是基础