A similarity-aware multiversion concurrency control and updating algorithm forup-to-date snapshots of data∗Thomas Gustafsson, Hugo Hallqvist, and Jörgen HanssonDepartment of Computer Science, Linköping University, SwedenE-mail: {thogu,jorha}@ida.liu.seAbstractReal-time databases handle reading and writing of datawith time constraints on transactions. Normally, data itemsin a real-time system have freshness requirements whichneed to be guaranteed, and for many transactions it is im-portant that accessed data items origin from the same sys-tem state, which can be ensured by letting the transactionsread a snapshot of the database. In this context, a snap-shot at a specific time represents values on data items thatwere stored in the database at this time. Furthermore, simi-lar values can be considered equal because values withingiven bounds do not affect the results from calculations.Previous work shows that using similarity among valuesof data items greatly increases the performance becausethere is a possibility to skip calculations. In this paper wepresent the MVTO-S concurrency control algorithm, whichsupports similarity and multiple versions of data and en-sures that transactions read an up-to-date snapshot of adatabase. Performance evaluations show that MVTO-S in-creases the performance considerably compared to well-established single-version concurrency control algorithms.1. IntroductionThe number of data items that are used in real-timeembedded systems has increased over the years. The rea-sons are the availability of more powerful CPUs and largeramounts of memory, and more advanced functions in thesoftware. A data item can have freshness requirementsand a calculation can have a deadline, i.e., there is meta-information on data, e.g., its freshness and the maximumtime allowed for calculating it. One way to organize dataand its meta-information is to use a database system, wheredata is stored centrally, which is in contrast to ad hoc so-lutions where storage of data is spread out in the software.∗ This work was funded by ISIS (Information Systems for IndustrialControl and Supervision) and CENIIT (Center for Industrial Informa-tion Technology) under contract 01.07.The benefit of having data stored centrally is that the soft-ware becomes easier to maintain. Using a database it is pos-sible to determine which data items are used in the soft-ware and their meta-information. This can be difficult to de-termine if the data is spread out in the software. Also, thedatabase system can be extended with algorithms that au-tomatically maintain data, e.g., the freshness of data. Thisis possible since the database system has a global knowl-edge of all data.For applications the required precision for input datamight vary and where the maximum allowed tolerated de-viation between, e.g., two consecutive readings of a datavalue, can be specified. If some tolerance is accepted, thenexact values of data items are not important. This can beformalized by assuming an upper bound on how old thevalue of a data item may be. Ramamritham gives a defini-tion of data freshness using the time domain [16]. Anotherway to define data freshness of a data item is to use its val-ues. Similarity is a formalization by Kuo and Mok on howto determine if two values of a data item can be consideredequal [11]. A value needs only be recalculated if at leastone of the values it depends on are dissimilar to the val-ues used deriving the value. Thus, data freshness can be de-fined in the value domain of data items. Performance evalu-ations have shown that using similarity can improve the per-formance of the system [5,6,8,15,21].In this paper, we use an engine electronic control unit(EECU) in a car as an example (this is one of our target ap-plications). Control loop calculations need to base their re-sults on up-to-date data values. Also, the EECU has a di-agnosis subsystem that executes with the lowest priority.Hence, it is likely that the diagnosis task in the worst casegets interrupted frequently. These interruptions cause the di-agnosis task to read values from different states of the exter-nal environment giving untrustworthy diagnosis results. Bya snapshot at time t we mean that the values of data itemsin the database are frozen at t, and these values are read bya transaction. By an up-to-date snapshot at time t we meana snapshot at t where all values are up-to-date, i.e., all dataitems that are affected by changes in values of other dataitems are updated. Sundell and Tsigas have developed wait-free snapshot algorithms that guarantee a calculation usesvalues on data items from the same state of the system [20].However, current snapshot algorithms do not consider sim-ilarity or that values need to be updated when a snapshotof data items is derived. Single-version concurrency controlalgorithms, e.g., high-priority two-phase locking (HP2PL)and optimistic concurrency control (OCC), need restarts toguarantee to give a snapshot to a transaction [4].We have built a real-time database that can be used in theEECU software. The data in an EECU is derived from sen-sor readings or from derived data items. This means thatan algorithm deriving snapshots must take into considera-tion that additional data items, to those read by a transac-tion, need to be updated to have an up-to-date snapshot.In this paper we contribute by introducing a new multi-version timestamp ordering with similarity (MVTO-S) con-currency control algorithm that ensures transactions see anup-to-date snapshot of the database. By using multiple ver-sions of data items it is possible to drastically decrease thenumber of conflicts between transactions. In single-versionconcurrency control, every conflict results in a restart of atransaction.Performance evaluations are conducted using a real-timedatabase and well-established single-version concurrencycontrol algorithms: HP2PL and OCC, a similarity-awareimplementation of OCC denoted OCC-S, and three dif-ferent implementations of MVTO-S (each implementationuses different techniques to store data versions). The eval-uations show that the number of transactions committingwithin their deadlines compared to single-version concur-rency control algorithms can significantly increase usingMVTO-S. Transactions read an up-to-date snapshot of thedatabase whereas this cannot be guaranteed using a single-version concurrency control.The outline of the paper is as follows. A data and trans-action model is given in section 2.