Sequential access: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
No edit summary
mNo edit summary
(41 intermediate revisions by 25 users not shown)
Line 1: Line 1:
[[File:Random vs sequential access.svg|thumb|right|Sequential access compared to [[random access]].]]
[[File:Random vs sequential access.svg|thumb|right|Sequential access compared to [[random access]]]]
In [[computer science]], '''sequential access''' means that a group of elements (such as data in a memory array or a disk file or on [[magnetic tape data storage]]) is accessed in a predetermined, ordered [[sequence]]. Sequential access is sometimes the only way of accessing the data, for example if it is on a tape. It may also be the access method of choice, for example if all that is wanted is to process a sequence of data elements in order.<ref>[http://technet.microsoft.com/en-us/library/cc938619.aspx Random and Sequential Data Access], Microsoft TechNet</ref>


'''Sequential access''' is a term describing a group of elements (such as data in a memory array or a [[Hard disk drive|disk]] file or on [[magnetic-tape data storage]]) being accessed in a predetermined, ordered [[sequence]]. It is the opposite of [[random access]], the ability to access an arbitrary element of a sequence as easily and efficiently as any other at any time.
However, there is no consistent definition of sequential access or sequentiality.<ref>''Irfan Ahmad'', [http://www.vmware.com/files/pdf/iiswc_2007_distribute.pdf Easy and Efficient Disk I/O Workload Characterization in VMware ESX Server], IISWC, 2007.</ref><ref>''Eric Anderson'', [https://www.usenix.org/legacy/event/fast09/tech/full_papers/anderson/anderson.pdf Capture, Conversion, and Analysis of an Intense NFS Workload], FAST, 2009.</ref><ref>''Yanpei Chen et al.'' [http://dl.acm.org/citation.cfm?id=2043562 Design Implications for Enterprise Storage Systems via Multi-dimensional Trace Analysis]. SOSP. 2011</ref><ref>''Andrew Leung et al.'' [http://www.ssrc.ucsc.edu/Papers/leung-usenix08.pdf Measurement and Analysis of Large-scale Network File System Workloads]. USENIX ATC. 2008</ref><ref>''Frank Schmuck and Roger Haskin'', [https://www.usenix.org/legacy/events/fast02/full_papers/schmuck/schmuck.pdf GPFS: A Shared-Disk File System for Large Computing Clusters], FAST. 2002</ref><ref>''Alan Smith''. [http://www-inst.eecs.berkeley.edu/~cs266/sp10/readings/smith78.pdf Sequentiality and Prefetching in Database Systems]. ACM TOS</ref><ref>''Hyong Shim et al.'' [http://0b4af6cdc2f0c5998459-c0245c5c937c5dedcca3f1764ecc9b2f.r43.cf2.rackcdn.com/11747-atc13-shim.pdf Characterization of Incremental Data Changes for Efficient Data Protection]. USENIX ATC. 2013.</ref><ref>''Avishay Traeger et al.'' [http://www.fsl.cs.sunysb.edu/docs/fsbench/fsbench.pdf A Nine Year Study of File System and Storage Benchmarking]. ACM TOS. 2007.</ref> In fact, different sequentiality definitions can lead to different sequentiality quantification results. In spatial dimension, request size, strided distance, backward accesses, re-accesses can affect sequentiality. For temporal sequentiality, characteristics such as multi-stream and inter-arrival time threshold has impact on the definition of sequentiality.<ref>''Cheng Li et al.'' [https://www.usenix.org/node/183622 Assert(!Defined(Sequential I/O))]. HotStorage. 2014</ref>


Sequential access is sometimes the only way of accessing the data, for example if it is on a tape. It may also be the access method of choice, for example if all that is wanted is to process a sequence of data elements in order.<ref>[https://technet.microsoft.com/en-us/library/cc938619.aspx Random and Sequential Data Access], Microsoft TechNet</ref>
In [[data structure]]s, a data structure is said to have sequential access if one can only visit the values it contains in one particular order. The canonical example is the [[linked list]]. Indexing into a list that has sequential access requires [[Big O notation|O]](''k'') time, where ''k'' is the index. As a result, many algorithms such as [[quicksort]] and [[Binary search algorithm|binary search]] degenerate into bad algorithms that are even less efficient than their naive alternatives; these algorithms are impractical without [[random access]]. On the other hand, some algorithms, typically those that do not have index, require only sequential access, such as [[mergesort]], and face no penalty.

==Definition==
There is no consistent definition in [[computer science]] of sequential access or sequentiality.<ref>''Irfan Ahmad'', [http://www.vmware.com/files/pdf/iiswc_2007_distribute.pdf Easy and Efficient Disk I/O Workload Characterization in VMware ESX Server], IISWC, 2007.</ref><ref>''Eric Anderson'', [https://www.usenix.org/legacy/event/fast09/tech/full_papers/anderson/anderson.pdf Capture, Conversion, and Analysis of an Intense NFS Workload], FAST, 2009.</ref><ref>''Yanpei Chen et al.'' [http://dl.acm.org/citation.cfm?id=2043562 Design Implications for Enterprise Storage Systems via Multi-dimensional Trace Analysis]. SOSP. 2011</ref><ref>''Andrew Leung et al.'' [http://www.ssrc.ucsc.edu/Papers/leung-usenix08.pdf Measurement and Analysis of Large-scale Network File System Workloads]. USENIX ATC. 2008</ref><ref>''Frank Schmuck and Roger Haskin'', [https://www.usenix.org/legacy/events/fast02/full_papers/schmuck/schmuck.pdf GPFS: A Shared-Disk File System for Large Computing Clusters], FAST. 2002</ref><ref>''Alan Smith''. [http://www-inst.eecs.berkeley.edu/~cs266/sp10/readings/smith78.pdf Sequentiality and Prefetching in Database Systems]. ACM TOS</ref><ref>''Hyong Shim et al.'' [http://0b4af6cdc2f0c5998459-c0245c5c937c5dedcca3f1764ecc9b2f.r43.cf2.rackcdn.com/11747-atc13-shim.pdf Characterization of Incremental Data Changes for Efficient Data Protection]. USENIX ATC. 2013.</ref><ref>''Avishay Traeger et al.'' [http://www.fsl.cs.sunysb.edu/docs/fsbench/fsbench.pdf A Nine Year Study of File System and Storage Benchmarking]. ACM TOS. 2007.</ref> In fact, different sequentiality definitions can lead to different sequentiality quantification results. In spatial dimension, request size, stride distance, backward accesses, re-accesses can affect sequentiality. For temporal sequentiality, characteristics such as multi-stream and inter-arrival time threshold has impact on the definition of sequentiality.<ref>''Cheng Li et al.'' [https://www.usenix.org/node/183622 Assert(!Defined(Sequential I/O))]. HotStorage. 2014</ref>

In [[data structure]]s, a data structure is said to have sequential access if one can only visit the values it contains in one particular order. The canonical example is the [[linked list]]. Indexing into a list that has sequential access requires [[Big O notation|O]](''n'') time, where ''n'' is the index. As a result, many algorithms such as [[quicksort]] and [[Binary search algorithm|binary search]] degenerate into bad algorithms that are even less efficient than their naive alternatives; these algorithms are impractical without [[random access]]. On the other hand, some algorithms, typically those that do not have index, require only sequential access, such as [[mergesort]], and face no penalty.


==See also==
==See also==
* [[Direct access storage device]]
* [[Direct-access storage device]]
* [[Queued sequential access method]]
* [[Queued Sequential Access Method|Queued sequential access method]]


==References==
==References==

Revision as of 23:21, 31 March 2023

Sequential access compared to random access

Sequential access is a term describing a group of elements (such as data in a memory array or a disk file or on magnetic-tape data storage) being accessed in a predetermined, ordered sequence. It is the opposite of random access, the ability to access an arbitrary element of a sequence as easily and efficiently as any other at any time.

Sequential access is sometimes the only way of accessing the data, for example if it is on a tape. It may also be the access method of choice, for example if all that is wanted is to process a sequence of data elements in order.[1]

Definition

There is no consistent definition in computer science of sequential access or sequentiality.[2][3][4][5][6][7][8][9] In fact, different sequentiality definitions can lead to different sequentiality quantification results. In spatial dimension, request size, stride distance, backward accesses, re-accesses can affect sequentiality. For temporal sequentiality, characteristics such as multi-stream and inter-arrival time threshold has impact on the definition of sequentiality.[10]

In data structures, a data structure is said to have sequential access if one can only visit the values it contains in one particular order. The canonical example is the linked list. Indexing into a list that has sequential access requires O(n) time, where n is the index. As a result, many algorithms such as quicksort and binary search degenerate into bad algorithms that are even less efficient than their naive alternatives; these algorithms are impractical without random access. On the other hand, some algorithms, typically those that do not have index, require only sequential access, such as mergesort, and face no penalty.

See also

References