Väitöskirjatyö/Dissertation
Väitöskirjan tiivistelmä suomeksi
Optimistisia samanaikaisuudenhallintamenetelmiä tosiaikatietokantoihin
Jan Lindström
Tietojenkäsittelytieteen laitos
Matemaattis-luonnontieteellinen tiedekunta
Helsingin Yliopisto
Monet tosielämän sovellukset sisältävät sekä aikarajoitteista tiedon käsittelyä että vain tietyn ajan voimassaolevaa tietoa. Tällaisia sovelluksia ovat esimerkiksi tietoliikennevaihde, verkonhallinta, navigaatiojärjestelmät ja pörssi. Yhteistä näille järjestelmille on muuttuvan tiedon kerääminen ympäristöstä, kerätyn aikaan sidotun tiedon käsittely ja oikea-aikainen vaste. Siksi nämä järjestelmät tarvitsevat tosiaikatietokannan eli tietokantajärjestelmän missä käsittelylle on määritelty aikaraja, johon mennessä vaste tulee muodostaa.
Samanaikaisuudenhallinta on yksi tärkeimmistä tutkimusalueista tosiaikatietokannoissa. Monet kirjallisuudessa esitetyt tosiaikaiset samanaikaisuudenhallintamenetelmät perustuvat pessimistiseen kaksivaiheiseen lukitukseen (2PL), missä tapahtuma pyytää lukkon tietoalkioon ennen tietoalkion käsittelyä ja odottaa jos lukkoa ei voida myöntää. Kaksivaiheisella lukituksella on kuitenkin sisäänrakennettuja ongelmia kuten lukkiuman mahdollisuus ja arvaamaton lukon odotusaika. Nämä ongelmat saattavat muodostua vakaviksi tosiaikajärjestelmissä, koska tosiaikaiset tapahtumat tulee suorittaa aikarajaansa mennessä muiden eheysehtojen lisäksi.
Optimistiset menetelmät takaavat pääsyn tietoalkioihin ilman odotusta ja ovat lukkiumattomia. Nämä ominaisuudet ovat tosiaikatietokannan kannalta edullisia. Koska tapahtumien suoritus tarkistetaan vasta tapahtuman sitoutumisvaiheessa, on käytössä enemmän informaatiota mahdollisten konfliktien hallintaan. Optimistisilla menetelmillä ongelmaksi muodostuu turhat peruutukset ja raskas peruutuskustannus, koska lähellä valmistumista olevan tapahtuman muutokset perutaan. Siksi optimistinen menetelmän suunnittelussa pyritään löytämään menetelmiä, jolla vältetään turhat peruuntumiset. Turha peruutus tapahtuu jos tapahtuma perutaan vaikka suoritus säilyttäisi tietokannan eheyden.
Väitöskirjassa osoitetaan että useat aikaisemmin esitetyt menetelmät peruuttavat tapahtumia turhaan. Tämän ongelman ratkaisemiseksi esitetään uusi optimistinen menetelmä, joka vähentää turhaan peruutettujen tapahtumien määrää. Menetelmä perustuu sitoutumisaikaleiman valitsemiseen mahdollisimman läheltä todellista aikaa ja tapahtumien järjestyksen dynaamiseen muuttamiseen. Menetelmä takaa tietokannan eheyden säilymisen tuottamalla vain sarjallistuvia ajoituksia ja niistäkin vain tiukat sallitaan.
Aikatietoisuus on tärkeässä roolissa tosiaikatietokannoissa. Siksi väitöskirjassa esitetään aikatietoisia laajennuksia esitettyyn perusmenetelmään. Tämän lisäksi esitetään menetelmä, jossa sekä perusmenetelmä että aikatietoiset menetelmät integroidaan yhdeksi menetelmäksi, joka ajonaikaisesti adaptoituu tilanteen mukaan.
Menetelmien käyttökelpoisuus osoitetaan kattavalla testauksella tarkoitukseen toteutetulla tosiaikatietokannan prototyypillä ja tietoliikennemaailman tietokannalla. Testikuorma kuvaa yhden palveluntarjoajan tarjoamia palveluita ja niiden käyttäjiä. Saadut tulokset osoittavat että turhia peruutuksia voidaan vähentää tehokkaasti ja näin parantaa tosiaikatietokannan tehokkuutta ja ennustettavuutta verrattuna aikaisemmin hyviksi osoitettuihin menetelmiin. Lisäksi havaitaan että aikatietoisuudella ei voida parantaa tosiaikatietokantojen tehokkuutta perusmenetelmään verrattuna. Adaptaatio sen sijaan tehostaa tosiaikatietokantoja ja on käyttökelpoinen menetelmä integroida sekä aikatiedostamaton menetelmä että aikatietoinen menetelmä tehokkaasti. Integroitu ja adaptiivinen menetelmä vähentää turhia peruutuksia ja tarjoaa tärkeille tapahtumille paremmat mahdollisuudet valmistua ennen aikarajaa.
Abstract of the Dissertation
Optimistic Concurrency Controm Methods for Real-Time Databases
Jan Lindström
Department of Computer Science
University of Helsinki
Many real-world applications contain time-constrained access to data as well as access to data that has temporal validity. For example, consider a telephone switching system, network management, navigation systems, stock trading, and command and control systems. These applications require gathering data from the environment, processing information in the context of information obtained in the past, and contributing {\em timely} response. Hence, these applications need a real-time database system, i.e. database system where transactions are associated with deadlines on their completion times.
Concurrency control is one of the main issues in the studies of real-time database systems. Many real-time concurrency control methods considered in the literature are based on pessimistic two-phase locking (2PL), where transaction acquires a lock before database operation and waits for the lock if it cannot be granted. However, 2PL has some inherent problems such as the possibility of deadlocks and unpredictable blocking time. These problems appear to be serious in real-time systems since real-time transactions need to meet their timing constraints, in addition to consistency requirements.
Optimistic concurrency control methods have the attractive properties of being non-blocking and deadlock-free. These properties make them especially attractive for real-time database systems. Because conflict resolution between the transactions is delayed until a transaction is near to its completion, there will be more information available on making the conflict resolution. Optimistic methods have the problem of unnecessary restarts and heavy restart overhead because some near-to-complete transactions have to be restarted. Therefore, the major concern in designing optimistic concurrency control methods is to design methods that minimize the number of transactions to be restarted.
This thesis shows that some of the well-known previous methods include unnecessary restart problems. A method to reduce these unnecessary restarts is proposed. This method is based on selecting a commit timestamp as near to the validation time as possible and a new method to resolve conflicts by adjusting the serialization order dynamically amongst the conflicting transactions after the validation is successful. This method maintains serializability or, more precisely, strict serializability. We show that many unnecessary restarts can be avoided efficiently and avoiding unnecessary restarts is an efficient approach for improving the performance and predictability of concurrency control methods for main-memory database systems beyond the current state-of-the-art.
Additionally, methods to incorporate information about the timing constraints of transactions in the conflict resolution is proposed. We show that priority cognizance is not a viable approach for improving the performance and predictability of real-time concurrency control methods for main-memory real-time database systems. The results show that the proposed methods offer better chances for critical transactions to complete before their deadlines.
Finally, the work identifies a need for adaptive and integrated concurrency control methods in real-time database systems. Therefore, a new optimistic concurrency control method is presented where conflict resolution is based on adaptation to the current workload. This method is shown to produce correct results and was experimentally tested. The performance of the proposed method is shown to be superior to previous approaches.
The feasibility of the proposed methods have been experimentally tested using a prototype of a main-memory real-time database system for telecommunications with a telecommunication service workload. The results show that optimistic methods can be used in this kind of environment.
Jan Lindström (Jan.Lindstrom@cs.Helsinki.FI)