DOMANDA inserimenti consistenti(acid) di nodi in liste concatenate in C.

[BigIssue]

Cio che voglio ottenere è poter inserire tre nodi in una lista collegata in modo atomico/consistente.

Simulando un inserimento:
ho una lista in cui sono gia prsenti 5 nodi.
Inserisco il primo nodo,
Inserisco il secondo nodo ma qualcosa non va a buon fine.
Allora utilizzo la funzione di restore che vuol dire cancellare il primo nodo inserito precedentemente, in modo da lasciare la lista collegata come era prima di fatto 5 nodi.

Pensavo di inserire nella lista collegata un campo atomic e un campo transaction cosi so che il primo nodo e il secondo nodo sono inseriti assieme nella stessa transazione.
Se qualcosa va storto negli inserimenti attraversando i nodi della lista quelli con atomic settati 1 posso settarli nuovamente a 0 e ripulire la transazione, di fatto cancellando i nodi nuovi inseriti.

Sto provando a realizzare un sistema dbms e voglio usare le liste collegate per costruire le tabelle e sfruttare i puntatori per salvare i dati in colonne.
L'inserimento nella lista collegata in un certo senso deve rispettare le proprietà acid di un sistema dbms.
Qualche consiglio, come fare?

struct rowlist{
    int *atomic;
    int *transaction;
    /*sono campi anche vuoti che differenza il tipo di dato se intero, stringa, o bit
       non avendo in C un modo di allocare dinamicamente il tipo di dato */
    int choice; //scelto il tipo di dato 0 int, 1 varchar, 2 bit
    int i;          //int
    char *v;    //varchar
    bool b;     //bit

    struct rowlist *next;
};

struct columnlist{
    int *atomic; //anche l'intestazione della tabella devono essere consistenti
    int *transaction;

    int *k;     //chiave della colonna
    char *n; //nome della colonna
    struct rowlist *r;  //totale della righe di una colonna come lista collegata
    struct columnlist *next;
};

 

[Utente cancellato 371741]

Vedo che stai postando in piu posti:

atomic and consistency(ACID) insertion in linked list in c

what i want to get is to do in atomic mode the insertion of three nodes in a linked list. Simulating the insertion of second node in the linked list, if this doesn't go well I execute the restore

stackoverflow.com

e' un esercizio per scuola ?


Cmq, per eseguire un blocco di operazioni in maniera atomica seve un meccanismo di mutual exclusion.

 

[BigIssue]

È un esercizio ma non per scuola. Si sono sempre io ad aver postato anche di là. Cerco di capire se artigianamente sia possibile fare una tabella con liste concatenate ed inserire una riga in modo consistente.

Inviato da BLN-L21 tramite App ufficiale di Tom\'s Hardware Italia Forum

 

[Utente cancellato 371741]

Un esempio

void add_item_to_db(struct ll *list, int id, char * data) {
    lock();
    entry->data = data;;
    entry->id = 1;
    list->next = entry;
    unlock();
}

lock(), unlock() sono simbolici, meccanismo di mutual exclusion e' a tuo piacimenti, dipende dall'os e dalel esigenze.

Poi io non sono specializzato in db, ci saranno migliori maestri qui, certo dovresti controllare che id non esista gia, se sovrascrivere, etc

 

[BigIssue]

Alla domanda se struct è atomico ragionandoci i membri primitivi sono atomici int char. Non penso lo siano le stringhe dunque char *. Nel complesso allocazione penso sia atomica ma un assegnamento non lo è. Per atomico intendo tutto cio che puo essere entità. Ma data questa definizione allora modificando due campi di una struttura di seguito sarebbe una operazione atomica. La confondo forse con consistenza.

Un esempio

void add_item_to_db(struct ll *list, int id, char * data) {
lock();
entry->data = data;;
entry->id = 1;
list->next = entry;
unlock();
}

lock(), unlock() sono simbolici, meccanismo di mutual exclusion e' a tuo piacimenti, dipende dall'os e dalel esigenze.

Poi io non sono specializzato in db, ci saranno migliori maestri qui, certo dovresti controllare che id non esista gia, se sovrascrivere, etc

Ma utilizzo del lock e unlock è piu che altro per gestire la concorrenza. Se due thread tentano di inserire 5 valori lo fanno in transazioni diverse. Con il lock e mutua esclusione ho accesso alla tabella in modo esclusivo. Prima inserisce il thread1 e poi il secondo thread2 successivamente.

Ma utilizzo del lock e unlock è piu che altro per gestire la concorrenza. Se due thread tentano di inserire 5 valori lo fanno in transazioni diverse. Con il lock e mutua esclusione ho accesso alla tabella in modo esclusivo. Prima inserisce il thread1 e poi il secondo thread2 successivamente.

Inviato da BLN-L21 tramite App ufficiale di Tom\'s Hardware Italia Forum

Infatti ho messo il campo int transaction per tenere traccia della transazione. Mettiamo che non ce ne siano al momento. È solo una.

Inviato da BLN-L21 tramite App ufficiale di Tom\'s Hardware Italia Forum

 

[Utente cancellato 371741]

1) atomicita' e' una cosa che serve quando la stessa risorsa (memoria nel tuo caso) e' utilizzata da piu processi/thread. O, anche da un interrupt.
2) se "list->next = ptr;" e' atomico o meno dipende dall'architettura e da cosa fa il compilatore. Supponi che sei su un x86_64, allora stai lavorando in long mode e i puntatori sono 64 bit, probabile l'operazione si traduca in un
mov, tipo ad esempio "mov rsi, rax" quindi atomico. La certezza e' nel decompilare e vedere l'assembly.
3) Tuttavia non c'entra per il tuo caso, infatti ho editato, perche tu devi inserire un item database e dovrai rendere esclusivo l'inserimento di tutti i dati.
4) tipo di lock, o semaforo, o spinlock o quant'altro va valutato dall'os e dalle esigenze

 

[BigIssue]

Sono d'accordo con bigendian sul fatto dell'atomicità e del lock.
Comunque le proprietà che mi interessa rispettare sono per lo più, la Consistency e Durability.

"Avevo una rowlist di 2 elementi. Come dicevo che se capita un errore nell'inserimento di rowlist vorrei riavere la rowlist allo stato in cui era con i soli 2 elementi."

Posso implementare il lock e unlock per la proprietà di Isolation e per gestire la concorrenza.
Proverò l'utilizzo dei due campi atomic e transaction e vi farò sapere.
grazie per l'aiuto.

 

[Andretti60]

Quello che stai chiedendo è estremamente complicato, in quanto fa parte di uno degli aspetti principali della struttura di un database, ossia come rispristinare il database in caso che non sia possibile completare una operazione. Esistono svariati metodi, in base alla struttura e alla complessità del database, non esiste la soluzione ottimale e infatti i database ne usano più di una.

Ovviamente i lock fanno parte della operazione, perché stiamo modificando il database, ma sono estremamente difficili da gestire, perché ovviamente vogliamo un lock di sola scrittura e occorre un meccanismo per disabilitarli nel caso il cliente che lo richiede vada in crash. E un lock deve avere un ciclo brevissimo, perché non vogliamo che altri utenti rimangono bloccati per periodi troppo lunghi, per questo non si usa un lock solo ma tanti piccoli, ognuno che blocca solo la parte che stiamo andando a modificare.

Per esempio un database embedded come per esempio SQLite (che usa un solo file) mette un lock sul file, esegue la transizione in memoria e riscrive il file quando completata, cosa che ovviamente non vogliamo fare con un database distribuito. E SQLite è un buon esempio da studiare in quanto è un progetto Open il cui sorgente è quindi disponibile.

 

[BigIssue]

Quello che stai chiedendo è estremamente complicato, in quanto fa parte di uno degli aspetti principali della struttura di un database, ossia come rispristinare il database in caso che non sia possibile completare una operazione. Esistono svariati metodi, in base alla struttura e alla complessità del database, non esiste la soluzione ottimale e infatti i database ne usano più di una.

Andretti60 grazie di avermi risposto e di metterci del tempo in questa discussione. Sono d'accordo.

Il mio è un tentativo di implementare un database stile sqlite che usi per lo piu le liste concatenate come struttura dati. Sono curioso.

Pur imparando le strutture dati all'università, Btree e binary search tree AVL, rosso-neri e altri mi risulta comunque difficile dare un impostazione per implementare un database management system.

Volevo portarlo avanti come progetto serio, conscio del fatto che ci sono almeno 100 database in circolazione. Ma rispetto altri progetti come per esempio un sistema operativo mi permetterà di capire meglio il codice di altri database e quindi contribuire al loro sviluppo non piu al mio.

Lo implemento tanto per "tenerlo in piedi nel suo funzionamento" finchè non risulta complicato.

Comunque ho scelto il C invece che un altro linguaggio ma perchè si usa in laboratorio di algoritmi in unimi.

primo problema che ho incontrato è stato che programmando in C, non ho trovato un modo per dichiarare una variabile di tipo generico come invece è presente in C# con la parola chiave var.
Quindi ogni cella della mia tabella ha tanti campi quanti i tipi definiti a priori che sono integer, varchar, e bit. (molto artigiano l'approccio in merito :) )

L'utente con la creazione della tabella in SQL

create table person(
   person_id INT NOT NULL AUTO_INCREMENT,
   person_fullname VARCHAR(100) NOT NULL,
   person_submission_date DATE,
   PRIMARY KEY ( person_id )
);

secondo problema: come rendere acid l'operazione di modifica o inserimento nella tabella.
Sia SQL di creazione della tabella che SQL di inserimento di una riga vanno implementate in modo ACID.

quindi la tabella person ha gia una riga popolata
person
id fullname submission_date
10 Michele Vezzoli 04-13-2021 20:15

insert into person(person_id,person_fullname) values (10,"Mario Rossi");
insert into person(person_id,person_fullname) values(11,"Nicola Paganotti");

per come l'ho realizzato la struttura funziona cosi: crea le colonne.
Imaginiamo che abbia gia una riga quella di Mario Rossi.
il successivo inserimento "Nicola Paganotti" fallisce.
Allora chiamo la funzione di rollback/restore che ripulisce tutto.

cioè rimango con la sola riga Mario Rossi. In pratica Atomic viene settato a 1 durante l'inserimento. Quando ho finito di inserire la riga nelle varie celle Atomic viene settata a 2. Cioè una sorta di operazione commit. Se la commit fallisce per qualche strano motivo mi ritrovo alcuni campi ad atomic settati a 1 e altri settati atomic a 2. Ma semplicemente la riga inserita risulta temporaneamente non in "produzione" ma ancora in fase 1. Percio verificando che ci sono ancora celle ad atomic settate a 1 rieseguo l'operazione di commit che le setta a 2. Quando anche l'ultimo campo è ad atomic settati a 2 ecco che elimino la transazione dal in_work cosi che è confermata in produzione.

Puo funzionare. non mi pare un ragionamento sbagliato di certo non eccelente.

 

[Andretti60]

Non ringraziarmi, mi piace aiutare quando posso purtroppo non ho molto tempo in questi giorni.
Stai mettendo troppa carne sul fuoco in questa discussione, se fai domande più specifiche in discussioni separate potrai avere più risposte.

Per esempio, la scelta del linguaggio C per un database server direi sia quasi obbligatoria, e non perché lo si insegna a scuola. Rimane il linguaggio più flessibile, efficiente e portatile, che con minimi cambiamenti lo si più compilare su tutte i sistemi operativi e su tutte le piattaforme. E la mancanza di native librerie per interazione utente (GUI) non è un problema per un database (come per ogni servizio o libreria di sistema).

vedo se più tardi riesco a collegarmi di nuovo.