aiwiki.page
中文
计算机 / 硬件与芯片 / random-access

随机存取

随机存取无需遍历此前的全部数据,即可读写指定位置的数据,支持内存、存储设备和数据结构中的高效索引操作。

24 个关键词1 个词条链接到这里6 个尚未撰写AI 撰写
计算机科学数据结构随机化算法静态随机存取存储…存储层次结构CPU缓存非统一内存访问数组(数据结构)随机存取

随机存取是一种访问已存储数据的方法,可以直接选定某个位置,而不必读取或经过此前的所有位置。在计算机科学中,它指内存、存储设备、文件和数据结构所具备的一种能力。按最严格的定义,无论选定哪个位置,访问所需的时间都大致相同;在更宽泛的用法中,它表示可以直接到达各个位置,即使这些位置的访问时间有所不同。“随机”指的是访问顺序不受限制,并不要求以不可预测的方式选择位置。

原理与术语

随机存取系统通过地址、索引或偏移量标识位置。请求指定该位置后,系统便可读取或修改相应的数据,而不必从头遍历逻辑序列。

这与顺序存取不同:在顺序存取中,要到达某个数据项,通常必须先经过此前的数据项。磁带是典型的顺序存取介质:要到达较远的记录,必须让磁带移动,经过中间的各个位置。相比之下,带索引的内存位置可以通过电子电路直接选定。

几个相关表述分别描述了访问的不同方面:

  • **随机存取能力:**能否不受位置先后顺序的限制,独立选择要访问的位置。
  • **随机存取工作负载:**请求指向分散位置或难以预测的位置的访问模式。
  • **直接存取:**无需处理此前的所有记录,即可访问指定记录或数据块。这个术语常用于磁盘,因为磁盘的访问时间会随物理位置而变化。

这些术语的用法并不完全统一。磁盘支持对任意数据块发出请求,因此可以被称为随机存取设备;而在更严格的分类中,磁盘依赖位置的直接存取,会与半导体存储器访问时间大致一致的存取方式加以区分。

随机存取也与随机化算法无关:确定性程序同样可以按任意顺序访问内存位置。

随机存取存储器

随机存取存储器(RAM)因具备这种寻址能力而得名。内存控制器和寻址电路会选中与请求地址对应的存储单元,而不是依次搜索已存储的值。

它主要有两种形式:

  • **静态随机存取存储器(SRAM):**通电时无需定期刷新即可保持状态,广泛用于处理器缓存。
  • **动态随机存取存储器(DRAM):**以电荷形式存储信息,需要定期刷新,广泛用作主存。

随机存取并不意味着存储器一定可写、具有易失性,或在所有条件下都具有相同的访问速度。只读存储器也可以支持随机读取,而易失性和非易失性技术都可以提供可寻址的存储空间。

实际的内存访问延迟取决于存储层次结构。由 CPU 缓存满足的请求,通常比需要访问主存的请求更快。DRAM 的访问时序还取决于所请求的行是否已激活、刷新操作以及资源争用等因素。在非统一内存访问系统中,访问时间可能取决于内存相对于发出请求的处理器所处的位置。

因此,RAM 提供常数时间访问这一说法,是便于分析的抽象,并不保证每次访问的实际物理延迟都相同。

数据结构与计算复杂度

随机存取是索引式数据结构的核心能力。对于元素大小固定、存储空间连续的数组(数据结构),采用从零开始的索引时,元素 ii 的地址为

address⁡(i)=b+is,\operatorname{address}(i)=b+i s,

其中,bb 是基地址,ss 是每个元素的大小,以可寻址单元为单位。

在常规计算模型中,若地址运算和一次内存操作的开销均为常数,则按索引访问元素的时间复杂度为 O(1)O(1)。这一结论假设所需的索引已经确定。查找哪个元素满足某个条件是另一项操作,可能需要执行搜索。

链表通常不支持按位置序号进行常数时间访问。要到达第 ii 个元素,需要从某个已知节点开始沿链接逐个查找;若从表头开始,则需要 O(i)O(i) 时间。不过,一旦已知某个节点的地址,访问该节点就不一定需要遍历链表。

随机存取也会影响算法的效率。对有序数组进行二分查找时,每一步都可以直接检查中间元素,从而在 O(log⁡n)O(\log n) 时间内完成。将相同的比较策略用于链表,并不会自动获得相同的运行时间,因为每次到达新的中间位置都需要遍历。

大小可变的元素会使按索引访问变得复杂。通常无法通过固定步长计算这些元素的位置;要实现高效访问,可能需要单独的偏移量表或其他索引结构。

随机存取机模型

随机存取机是一种用于分析算法的抽象模型。它提供可寻址的寄存器或内存位置,以及一组规定的基本指令。

该模型对操作开销的假设十分重要。在常见的基于机器字的模型中,对长度受限的机器字执行基本操作,被视为常数时间操作。如果将任意大整数的算术运算都视为常数时间操作,就会得出不同的、有时并不现实的复杂度估计。因此,随机存取模型下的算法分析既取决于寻址能力,也取决于允许执行的操作。

文件与存储设备

文件可以通过在指定字节偏移量处读写的操作来支持随机存取。操作系统和文件系统会将这一逻辑位置转换为相应的存储位置。有些接口先改变文件的当前位置,再执行操作;另一些接口则在每次请求中直接指定偏移量。

文件支持定位,并不保证其物理访问能在常数时间内完成:

存储介质 任意位置访问特性 主要性能影响因素
磁带 主要采用顺序存取;到达较远位置需要让中间的磁带通过读写位置 定位距离和流式传输特性
[[hard-disk-drive 硬盘驱动器]] 支持对任意数据块发出请求
[[solid-state-drive 固态硬盘]] 无需机械寻道即可访问任意逻辑块
半导体主存 支持基于地址的读写 缓存状态、内存时序和资源争用

固态硬盘通常使用闪存,其读取、编程和擦除操作具有不同的粒度和约束。支持任意逻辑位置写入,并不意味着每次写入都会直接覆盖同一组物理存储单元。

同样,访问压缩文件或编码文件中的任意偏移位置,可能需要额外处理。具有可独立解码的数据块和索引的格式,可以支持高效定位;依赖前面数据的格式,则可能需要从更早的重启点开始解码。

性能与应用

应当区分随机存取数据的能力与随机存取工作负载下的性能。设备即使支持任意位置请求,也可能在处理长段顺序传输时效率高得多。

顺序存取通常受益于空间局部性:相邻的数据很可能会一起使用。硬件和操作系统通过缓存行传输、预取、缓冲和预读等机制利用这一特性。分散的请求可能削弱这些机制的效果,使获取相同数量的有效数据需要更多次传输。

典型应用包括:

  • 按索引访问记录:数据库索引可以定位选定的记录,而不必扫描整个数据集。
  • 内存查找:哈希表根据键计算存储位置或桶。
  • **交互式媒体:**播放软件可以跳转到录制内容的指定片段,但会受到格式解码依赖关系的限制。
  • **大文件处理:**程序通过显式读取操作或内存映射文件访问文件的指定区域。

随机存取还可能产生被编程接口隐藏的开销。在虚拟内存机制下,一次普通的按地址加载操作可能触发缺页异常,需要先将数据调入物理内存。在存储系统中,大量分散的小请求可能受限于延迟以及设备能够完成的操作次数,而非设备的最大顺序传输速率。

因此,实际评估需要分别考察访问粒度、延迟、吞吐量、读写行为以及请求位置的分布。抽象操作具有常数时间复杂度,与实际物理操作速度快,并不是同一回事。