시퀀셜 액세스
Sequential access
시퀀셜 액세스란, 액세스 되고 있는 요소(메모리 어레이, 디스크 파일, 또는 자기 테이프 데이터 스토리지상의 데이터 등)의 그룹을 미리 정해진 순서로 기술하는 용어입니다.랜덤 액세스와 반대되는 것은 시퀀스의 임의의 요소에 언제든지 다른 요소처럼 쉽고 효율적으로 액세스할 수 있는 기능입니다.
데이터가 테이프에 있는 경우처럼 순차적 액세스가 데이터에 액세스하는 유일한 방법일 수 있습니다.예를 들어,[1] 데이터 요소의 시퀀스를 순서대로 처리하는 것만으로 액세스 방법을 선택할 수도 있습니다.
정의.
컴퓨터 사이언스에서는 시퀀셜 액세스 [2][3][4][5][6][7][8][9]또는 시퀀셜리티에 대한 일관된 정의는 없습니다.실제로 순차성 정의가 다르면 순차성 정량화 결과가 달라질 수 있습니다.공간 차원, 요청 크기, 스트라이드 거리, 역방향 액세스, 재접근은 순차성에 영향을 미칠 수 있습니다.시간적 시퀀셜리티의 경우 다중 스트림 및 도착 간 시간 임계값과 같은 특성이 시퀀셜리티 [10]정의에 영향을 미칩니다.
데이터 구조에서 데이터 구조가 포함된 값을 특정 순서로만 볼 수 있는 경우 순차적 액세스 권한을 갖는다고 합니다.표준적인 예는 링크 리스트입니다.순차적 액세스 권한이 있는 목록에 인덱싱하려면 O(n) 시간이 필요합니다. 여기서 n은 색인입니다.그 결과, 퀵소트나 바이너리 검색등의 많은 알고리즘은, 순진한 대체 알고리즘보다 효율이 낮은 불량 알고리즘으로 전락해 버립니다.이러한 알고리즘은 랜덤 액세스 없이는 실용적이지 않습니다.한편, 일반적으로 인덱스가 없는 알고리즘 중에는 mergesort 등의 순차적 액세스만 필요하며 패널티는 발생하지 않습니다.
「 」를 참조해 주세요.
레퍼런스
- ^ 랜덤 및 시퀀셜 데이터 액세스, Microsoft TechNet
- ^ IRfan Ahmad, VMware ESX Server의 간편하고 효율적인 디스크 I/O 워크로드 특성, IISWC, 2007.
- ^ Eric Anderson, Capture, Conversion, and Analysis of a Intensive NFS Workload, FAST, 2009.
- ^ 옌페이 첸 외다차원 트레이스 분석을 통한 엔터프라이즈 스토리지 시스템 설계 시사점SOSP. 2011
- ^ 앤드류 렁 외대규모 네트워크 파일 시스템 워크로드 측정 및 분석USENIX ATC. 2008
- ^ Frank Schmuck과 Roger Haskin, GPFS: 대규모 컴퓨팅 클러스터용 공유 디스크 파일 시스템, FAST. 2002년
- ^ 앨런 스미스.데이터베이스 시스템의 시퀀셜리티와 프리페치.ACM TOS
- ^ 형심 등효율적인 데이터 보호를 위한 증분 데이터 변경 특성 분석USENIX ATC, 2013.
- ^ Avishay Traeger 등파일 시스템과 스토리지 벤치마크에 관한 9년간의 연구.ACM TOS. 2007.
- ^ 청리 등단언(!정의(시퀀셜 I/O)핫 스토리지2014
