| |
我们的需求是这样的：服务程序每周会停机一次。每周总共涉及的玩家数据 10 万组。每组数据 4k 到 32K 之间。都是文本数据。可以看成一个 id 到数据串的 key/value 数据储存服务。经估算，总数据可以全部放入内存。数据会频繁更新，更新后长度会改变。
我花了一天实现这个 k/v 内存数据服务。为了最大利用内存，并同时保证效率，以及代码实现的简洁。我采用预先分配好整块内存的方案，把内存切割成 1K 为单位的区块。并用单向链表串起来。考虑到内存 cache 的命中效率。链表指针本身和数据储存区分离。（大多数时候，我们只需要访问链表指针，而不需要访问具体数据）
链表指针采用序号，而非内存地址。这样即使在 64bit 系统上，依然使用 4 字节索引（可以最大可管理 4T 数据，足够了）。单向链表可以比双向链表节省一半的指针操作以及节约少量内存。代价是代码写起来繁杂一点。
所有内存区块分成两部分：空闲区块和已用区块。一开始全部空间都是空闲。一旦向内放入一段数据，就从空闲链表上摘下够用的区块，放到已用链表的尾部。如果 cache 空间满，则从已用区块链表头部移掉一些空间还给空间区块（这些数据区是长久未访问过的）。每次读取一段数据，都将其调整到已用链表的末尾，保证最后才清理。
另外做一个 hash 表，从 id 映射到在 cache 中区块段的头（由于是单向链表，具体实现时应保存上一个节点）。这样可以用 O(1) 时间查询指定 id 对应的数据区，
保存在 cache 中的数据不必在地址上完全连续，这好比磁盘的分簇管理。和磁盘不同，内存的随机访问性能和顺序访问性能差异更小。这样有利于内存空间利用效率。
|
| 【收藏】【打印】【进入论坛】 |
|
|
|
|
| |
|
|
|
