Multi-versioning in Transactional Memory View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2015

AUTHORS

Idit Keidar , Dmitri Perelman

ABSTRACT

Reducing the number of aborts is one of the biggest challenges of most transactional systems: existing TMs may abort many transactions that could, in fact, commit without violating correctness. Historically, the commonly used method for reducing the abort rate was maintaining multiple object versions. Multiversion concurrency control is a classical approach for providing concurrent access to the database in database management systems. Its idea is to let a reading transaction obtain a consistent snapshot corresponding to an arbitrary point in time (e.g., defined at the beginning of a transaction) – concurrent updates are isolated through maintaining old versions rather than via scheduling decisions.Multi-versioning was adopted by transactional memory algorithms as well. In this chapter we overview the multi-versioning approach by studying the inherent properties of STMs that use multiple versions to guarantee successful commits of all read-only transactions.We first consider the challenges of garbage collecting of old object versions, and show that no STM can be optimal in the number of previous versions kept, while following the naïve approach of keeping a constant number of last versions per object might lead to an exponential memory growth.We then show the potential performance challenges of multi-versioned STMs, including disjoint-access parallelism and visibility of read-only transactions.We demonstrate the advantages of implementing multi-versioned STMs in managed memory environments by presenting Selective Multi-Versioning (SMV) algorithm. SMV relies on automatic garbage collection, and thus efficiently deals with old versions while still allowing invisible read-only transactions. More... »

PAGES

150-165

Book

TITLE

Transactional Memory. Foundations, Algorithms, Tools, and Applications

ISBN

978-3-319-14719-2
978-3-319-14720-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-14720-8_7

DOI

http://dx.doi.org/10.1007/978-3-319-14720-8_7

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1016916880


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Israel Institute of Technology, Technion, Israel", 
          "id": "http://www.grid.ac/institutes/grid.6451.6", 
          "name": [
            "Israel Institute of Technology, Technion, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Keidar", 
        "givenName": "Idit", 
        "id": "sg:person.07674464077.03", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07674464077.03"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Facebook Inc., USA", 
          "id": "http://www.grid.ac/institutes/grid.453567.6", 
          "name": [
            "Facebook Inc., USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Perelman", 
        "givenName": "Dmitri", 
        "id": "sg:person.015440102124.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015440102124.28"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015", 
    "datePublishedReg": "2015-01-01", 
    "description": "Reducing the number of aborts is one of the biggest challenges of most transactional systems: existing TMs may abort many transactions that could, in fact, commit without violating correctness. Historically, the commonly used method for reducing the abort rate was maintaining multiple object versions. Multiversion concurrency control is a classical approach for providing concurrent access to the database in database management systems. Its idea is to let a reading transaction obtain a consistent snapshot corresponding to an arbitrary point in time (e.g., defined at the beginning of a transaction) \u2013 concurrent updates are isolated through maintaining old versions rather than via scheduling decisions.Multi-versioning was adopted by transactional memory algorithms as well. In this chapter we overview the multi-versioning approach by studying the inherent properties of STMs that use multiple versions to guarantee successful commits of all read-only transactions.We first consider the challenges of garbage collecting of old object versions, and show that no STM can be optimal in the number of previous versions kept, while following the na\u00efve approach of keeping a constant number of last versions per object might lead to an exponential memory growth.We then show the potential performance challenges of multi-versioned STMs, including disjoint-access parallelism and visibility of read-only transactions.We demonstrate the advantages of implementing multi-versioned STMs in managed memory environments by presenting Selective Multi-Versioning (SMV) algorithm. SMV relies on automatic garbage collection, and thus efficiently deals with old versions while still allowing invisible read-only transactions.", 
    "editor": [
      {
        "familyName": "Guerraoui", 
        "givenName": "Rachid", 
        "type": "Person"
      }, 
      {
        "familyName": "Romano", 
        "givenName": "Paolo", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-14720-8_7", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-14719-2", 
        "978-3-319-14720-8"
      ], 
      "name": "Transactional Memory. Foundations, Algorithms, Tools, and Applications", 
      "type": "Book"
    }, 
    "keywords": [
      "object versions", 
      "automatic garbage collection", 
      "transactional memory algorithms", 
      "multiversion concurrency control", 
      "database management system", 
      "multiple object versions", 
      "old version", 
      "number of aborts", 
      "memory algorithm", 
      "concurrency control", 
      "memory environment", 
      "transactional systems", 
      "consistent snapshots", 
      "transactional memory", 
      "concurrent access", 
      "scheduling decisions", 
      "abort rate", 
      "garbage collection", 
      "multiple versions", 
      "na\u00efve approach", 
      "performance challenges", 
      "management system", 
      "disjoint-access parallelism", 
      "memory growth", 
      "successful commits", 
      "big challenge", 
      "transactions", 
      "previous version", 
      "constant number", 
      "algorithm", 
      "reading transaction", 
      "classical approach", 
      "last version", 
      "versioning", 
      "version", 
      "parallelism", 
      "correctness", 
      "challenges", 
      "commits", 
      "arbitrary point", 
      "abort", 
      "SMV", 
      "objects", 
      "system", 
      "inherent properties", 
      "database", 
      "update", 
      "environment", 
      "access", 
      "snapshot", 
      "memory", 
      "number", 
      "advantages", 
      "visibility", 
      "idea", 
      "collection", 
      "decisions", 
      "garbage", 
      "method", 
      "point", 
      "fact", 
      "control", 
      "chapter", 
      "STM", 
      "rate", 
      "properties", 
      "growth", 
      "Tm", 
      "approach", 
      "most transactional systems", 
      "time (e.g., defined at the beginning of a transaction) \u2013 concurrent updates", 
      "versioning approach", 
      "challenges of garbage", 
      "old object versions", 
      "exponential memory growth", 
      "potential performance challenges", 
      "multi-versioned STMs", 
      "Selective Multi-Versioning (SMV) algorithm", 
      "Multi-Versioning (SMV) algorithm"
    ], 
    "name": "Multi-versioning in Transactional Memory", 
    "pagination": "150-165", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1016916880"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-14720-8_7"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-14720-8_7", 
      "https://app.dimensions.ai/details/publication/pub.1016916880"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:16", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_281.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-14720-8_7"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-14720-8_7'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-14720-8_7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-14720-8_7'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-14720-8_7'


 

This table displays all metadata directly associated to this object as RDF triples.

154 TRIPLES      23 PREDICATES      104 URIs      97 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-14720-8_7 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author N63fd7a81446a40be8d6389b19ceb44df
4 schema:datePublished 2015
5 schema:datePublishedReg 2015-01-01
6 schema:description Reducing the number of aborts is one of the biggest challenges of most transactional systems: existing TMs may abort many transactions that could, in fact, commit without violating correctness. Historically, the commonly used method for reducing the abort rate was maintaining multiple object versions. Multiversion concurrency control is a classical approach for providing concurrent access to the database in database management systems. Its idea is to let a reading transaction obtain a consistent snapshot corresponding to an arbitrary point in time (e.g., defined at the beginning of a transaction) – concurrent updates are isolated through maintaining old versions rather than via scheduling decisions.Multi-versioning was adopted by transactional memory algorithms as well. In this chapter we overview the multi-versioning approach by studying the inherent properties of STMs that use multiple versions to guarantee successful commits of all read-only transactions.We first consider the challenges of garbage collecting of old object versions, and show that no STM can be optimal in the number of previous versions kept, while following the naïve approach of keeping a constant number of last versions per object might lead to an exponential memory growth.We then show the potential performance challenges of multi-versioned STMs, including disjoint-access parallelism and visibility of read-only transactions.We demonstrate the advantages of implementing multi-versioned STMs in managed memory environments by presenting Selective Multi-Versioning (SMV) algorithm. SMV relies on automatic garbage collection, and thus efficiently deals with old versions while still allowing invisible read-only transactions.
7 schema:editor N6ebbdd878d1d4310a7ad1e0192969e0d
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nfd404da71164444887714c1c1671e00a
12 schema:keywords Multi-Versioning (SMV) algorithm
13 SMV
14 STM
15 Selective Multi-Versioning (SMV) algorithm
16 Tm
17 abort
18 abort rate
19 access
20 advantages
21 algorithm
22 approach
23 arbitrary point
24 automatic garbage collection
25 big challenge
26 challenges
27 challenges of garbage
28 chapter
29 classical approach
30 collection
31 commits
32 concurrency control
33 concurrent access
34 consistent snapshots
35 constant number
36 control
37 correctness
38 database
39 database management system
40 decisions
41 disjoint-access parallelism
42 environment
43 exponential memory growth
44 fact
45 garbage
46 garbage collection
47 growth
48 idea
49 inherent properties
50 last version
51 management system
52 memory
53 memory algorithm
54 memory environment
55 memory growth
56 method
57 most transactional systems
58 multi-versioned STMs
59 multiple object versions
60 multiple versions
61 multiversion concurrency control
62 naïve approach
63 number
64 number of aborts
65 object versions
66 objects
67 old object versions
68 old version
69 parallelism
70 performance challenges
71 point
72 potential performance challenges
73 previous version
74 properties
75 rate
76 reading transaction
77 scheduling decisions
78 snapshot
79 successful commits
80 system
81 time (e.g., defined at the beginning of a transaction) – concurrent updates
82 transactional memory
83 transactional memory algorithms
84 transactional systems
85 transactions
86 update
87 version
88 versioning
89 versioning approach
90 visibility
91 schema:name Multi-versioning in Transactional Memory
92 schema:pagination 150-165
93 schema:productId Nc0d753990f69472fb286cce8577c3b5a
94 Nfed0de93bfa740b888f8c6d58e678b93
95 schema:publisher N8b79989b60e24813af2fbb0fd722150f
96 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016916880
97 https://doi.org/10.1007/978-3-319-14720-8_7
98 schema:sdDatePublished 2022-01-01T19:16
99 schema:sdLicense https://scigraph.springernature.com/explorer/license/
100 schema:sdPublisher N75cdf2f20cb3473e9feb3dad58a29d79
101 schema:url https://doi.org/10.1007/978-3-319-14720-8_7
102 sgo:license sg:explorer/license/
103 sgo:sdDataset chapters
104 rdf:type schema:Chapter
105 N13693b0333a94d3ca196076f4c687ee2 rdf:first sg:person.015440102124.28
106 rdf:rest rdf:nil
107 N26a17ed9b557496cad9a1435aea9154e rdf:first N923fbc14756a4d2cafdfa015508065e7
108 rdf:rest rdf:nil
109 N49a4deeccc2e42618d0a7cc42b71bb14 schema:familyName Guerraoui
110 schema:givenName Rachid
111 rdf:type schema:Person
112 N63fd7a81446a40be8d6389b19ceb44df rdf:first sg:person.07674464077.03
113 rdf:rest N13693b0333a94d3ca196076f4c687ee2
114 N6ebbdd878d1d4310a7ad1e0192969e0d rdf:first N49a4deeccc2e42618d0a7cc42b71bb14
115 rdf:rest N26a17ed9b557496cad9a1435aea9154e
116 N75cdf2f20cb3473e9feb3dad58a29d79 schema:name Springer Nature - SN SciGraph project
117 rdf:type schema:Organization
118 N8b79989b60e24813af2fbb0fd722150f schema:name Springer Nature
119 rdf:type schema:Organisation
120 N923fbc14756a4d2cafdfa015508065e7 schema:familyName Romano
121 schema:givenName Paolo
122 rdf:type schema:Person
123 Nc0d753990f69472fb286cce8577c3b5a schema:name dimensions_id
124 schema:value pub.1016916880
125 rdf:type schema:PropertyValue
126 Nfd404da71164444887714c1c1671e00a schema:isbn 978-3-319-14719-2
127 978-3-319-14720-8
128 schema:name Transactional Memory. Foundations, Algorithms, Tools, and Applications
129 rdf:type schema:Book
130 Nfed0de93bfa740b888f8c6d58e678b93 schema:name doi
131 schema:value 10.1007/978-3-319-14720-8_7
132 rdf:type schema:PropertyValue
133 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
134 schema:name Information and Computing Sciences
135 rdf:type schema:DefinedTerm
136 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
137 schema:name Information Systems
138 rdf:type schema:DefinedTerm
139 sg:person.015440102124.28 schema:affiliation grid-institutes:grid.453567.6
140 schema:familyName Perelman
141 schema:givenName Dmitri
142 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015440102124.28
143 rdf:type schema:Person
144 sg:person.07674464077.03 schema:affiliation grid-institutes:grid.6451.6
145 schema:familyName Keidar
146 schema:givenName Idit
147 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07674464077.03
148 rdf:type schema:Person
149 grid-institutes:grid.453567.6 schema:alternateName Facebook Inc., USA
150 schema:name Facebook Inc., USA
151 rdf:type schema:Organization
152 grid-institutes:grid.6451.6 schema:alternateName Israel Institute of Technology, Technion, Israel
153 schema:name Israel Institute of Technology, Technion, Israel
154 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...