Konkurrentzia-kontrola: Serializagarritasuna eta protokoloak

gaia: Konkurrentzia-kontrola

Sarrera

• Erabiltzaile anitzeko DBKS batean, aldi berean hainbat erabiltzailek lan egin dezakete.
• Datuen aldibereko atzipenak ez du zertan egoera koherente batera eraman.
• Konkurrenteki egikaritzen diren transakzio desberdinek objektu berberak erabil ditzakete.

Sarrera: ACID propietateak

• Isolation - Isolamendua (konkurrentzia kontrolerako unitate logikoa):
  • Transakzio bat beste transakzioetatik isolatuta exekutatzen ari balitz bezala exekutatu behar da.
  • Transakzio baten exekuzioak ezin du interferentziarik sortu modu konkurrentean exekutatzen ari diren beste transakzioekin.

Konkurrentzia-arazoak

• Eguneratze galduak
• Behin-behineko aldatzeak (irakurketa zikinak)
• Irakurketa ez-koherenteak

Transakzioen plangintzak

Definizioa

• N transakzioen plangintza bat transakzio horietako eragiketen tartekatzea da, non transakzio bakoitzeko eragiketen ordena mantentzen den.
• P izendatzen ditugun N transakzioen P plangintza emanda, T_i bakoitzeko T_i-ren eragiketak:
  • P plangintzan T_i-n agertzen diren orden berean agertzen dira.
  • Beste transakzioetako eragiketekin tarteka daitezke.

Plangintza seriala

• Transakzio bakoitzaren eragiketak elkarren segidan egikaritzen dira, beste transakzioko eragiketarik tartekatu gabe.
• Konkurrentziari probetxu ateratzen ez zaio.
• Transakzioak ez dira modu eraginkorrean egikaritzen.

Transakzioen tartekatzea

• Hainbat transakzioren eragiketak tarteka badaitezke, plangintza asko existitzen dira.
• Serializaziogarritasunaren teoriari esker:
  • Plangintzak zuzenak diren edo ez erabaki daiteke.
  • Plangintza okerrak saihesten dituzten konkurrentzia-kontrolerako teknikak defini daitezke.

Plangintza serializagarriak

• Plangintza bat serializagarria da baldin eta plangintza serial baten baliokidea bada.
• Bi plangintza baliokideak dira:
  • DB-ko edozein egoeratik azken egoera berdina sortzen badute.
  • Objektu bakoitzari eragiketa berdinak eta orden berean aplikatzen bazaizkio.

Gatazkak (I)

• Plangintza bateko bi eragiketak gatazkan daude baldin eta:
  • Transakzio desberdinetakoak badira.
  • X elementu/objektu bera atzitzen badute.
  • Eragiketetako bat gutxienez WRITE(X) da.

Gatazkak (III)

• Bi plangintza gatazka-baliokideak dira baldin eta gatazka sorrarazten duten edozein bi eragiketaren ordena berdina bada bi plangintzetan.
• P plangintza gatazkagatiko serializagarria da baldin eta plangintza serial baten gatazka-baliokidea bada:
  • P plangintzan gatazkan dauden eragiketen ordena plangintza serial baten berdina da.
  • Gatazkan ez dauden P-ko eragiketak berrantolatu egin ditzakegu plangintza serial baliokidea osatzen dugun arte.

Gatazka-serializagarritasuna aztertzea (I)

• READ eta WRITE eragiketei bakarrik begiratzen zaie.
• Lehentasun-grafo (edo serializazio-grafo) zuzendu bat eraiki G={N,A}:
  • T_i transakzio bakoitzerako adabegi bat dago (N = {T₁, T₂, …, T_n}).
  • A = {a₁, a₂, …, a_m} ertz zuzenduen multzoa da non
    • (T_i → T_j) ertza existitzen da baldin eta T_i-ko eragiketa bat gatazkan dagoen T_j-ko eragiketa baten aurretik agertzen bada plangintzan.

Gatazka-serializagarritasuna aztertzea (II)

• G grafoan ziklo bat badago, plangintza ez da izango gatazka-serializagarria.
• Zikloa ertz-segida bat da non:
  • Ertz bakoitzaren hasierako adabegia (lehen ertza izan ezik) aurreko ertzaren amaierako adabegiaren berdina da.
  • Lehen ertzaren hasierako adabegia azken ertzaren amaierako adabegiaren berdina da.

Gatazka-serializagarritasuna aztertzea (III)

• G grafoan ziklorik ez badago, plangintza (gatazka-)serializagarria da:
  • P-ren baliokidea den plangintza serial baliokidea bat sor dezakegu P-n parte hartzen duten transakzioak ordenatuz.
  • (T_i → T_j) ertzak adierazten du edozein plangintza serial baliokidetan T_i T_j-ren aurretik agertu behar dela.

Gatazka-serializagarritasuna aztertzea (IV)

• Arazoa:
  • Transakzioak sistemara etengabe bidaltzen direnez, oso zaila da plangintza bat serializagarria den edo ez aurretik aztertzea.

Serializagarritasuna bermatzen duten protokoloak

• Serializagarritasunaren teorian oinarritutako erregela multzoak.
• Transakzioen plangintza serializagarria da baldin eta:
  • Transakzio guztiek erregelak betetzen badituzte, edo
  • Konkurrentzia-kontrolerako azpisistemak erregelak automatikoki betearazten baditu.
• DBKS-ek ezartzen ditu protokoloak.