Forem: Drimil Mendapara

Ensuring Data Integrity in Multi-User Environments

Drimil Mendapara — Sat, 31 Aug 2024 10:34:31 +0000

What is in Concurrency Control?

Concurrency Control in databases refers to the methods and techniques used to ensure that multiple transactions can occur simultaneously without leading to data inconsistencies, corruption, or loss.

A database handles more than one transaction at the same time, and some transactions may read and update the same data. This can lead to issues like dirty reads and write-write conflicts. To manage this, databases use techniques known as concurrency control techniques.

Lock-Based Concurrency Control
Timestamp-Based Concurrency Control
Multiversion Concurrency Control (MVCC)

Lock Based Concurrency Control

In this technique, transactions use a locking mechanism to update or modify data in the database. This method helps the database prevent conflicts and maintain consistency

We basically use two types of locks for any database resources.

Shared Locks (S): Allow multiple transactions to read (or acquire a shared lock on) the same resource but prevent any transaction from modifying it.
Exclusive Locks (X): Allow a single transaction to both read and modify a resource. When a transaction holds an exclusive lock, no other transaction can acquire any type of lock (shared or exclusive) on that resource.

A shared lock is used when a transaction reads some data. During this time, the transaction acquires a shared lock, and more than one transaction can acquire a shared lock on the same database resource. However, when a transaction wants to update data, it acquires an exclusive lock. This lock is used when a transaction modifies or updates data. When one transaction acquires an exclusive lock, other transactions cannot acquire either a shared or an exclusive lock on that resource.

We use two type of method into lock base concurrency control

Two-Phase Locking (2PL): A protocol where transactions acquire all the necessary locks before releasing any of them. It consists of two phases:
- Growing Phase: The transaction acquires locks but does not release any.
- Shrinking Phase: The transaction releases locks and cannot acquire any new locks.
Strict Two-Phase Locking (Strict 2PL): A stricter form of 2PL where transactions must hold all their locks until they commit or abort.

We have to consider trade-offs between concurrency and locking. In lock-based concurrency control, a transaction may lock an entire page or table of the resource. While this approach reduces the number of locks the database has to manage, it also results in lower concurrency. This type of lock is called Coarse-Grained Locking. Alternatively, we can lock only the specific row that the transaction is used. Although this approach requires the database to manage more locks, it allows for higher concurrency, and is referred to as Fine-Grained Locking. Depending on our use case, we should choose the appropriate technique.

In this concurrency technique, a deadlock situation can occur when one transaction acquires a resource that is needed by another transaction, and the other transaction acquires a resource that is needed by the first transaction. In such cases, a deadlock occurs. To resolve this, the database uses deadlock prevention and deadlock detection techniques.

Dead Lock Prevention

We have two techniques Wait-Die and Wound-Wait Schemes
- Wait-Die: If an older transaction requests a lock held by a younger transaction, it waits (wait). If a younger transaction requests a lock held by an older transaction, the younger transaction is aborted (die).
- Wound-Wait: If an older transaction requests a lock held by a younger transaction, the younger transaction is aborted (wound). If a younger transaction requests a lock held by an older transaction, it waits (wait).
Dead Lock Detection

The database system builds a graph where each node represents a transaction. An edge from T1 to T2 indicates that T1 is waiting for a lock held by T2. If this graph contains a cycle, a deadlock is detected.
Deadlock Resolution

Once a deadlock is detected, the system resolves it by rolling back one or more transactions. The chosen transaction is known as the "victim.”

The selection of a victim can be based on various criteria
- Minimum Cost: The transaction that has made the least progress (e.g., has executed the fewest statements) is rolled back.
- Lowest Priority: Transactions are assigned priorities, and the one with the lowest priority is rolled back.
After rolling back a transaction, it can be retried either immediately or after a certain delay.

Timestamp-Based Concurrency Control

Timestamp-Based Concurrency Control (TBCC) is a method used in database systems to ensure that transactions are executed in a serialisable manner without using locks. Instead of relying on locks, TBCC assigns a unique timestamp to each transaction and uses these timestamps to enforce the order of transaction execution.

In this technique, when a transaction is incoming, we assign a unique timestamp to that transaction. If more than one transaction arrives at the same time, the system ensures that each transaction receives a unique timestamp.

The database data has two types of timestamps that help handle concurrency in transactions.

Read Timestamp (RTS): The RTS of a data item is the largest timestamp of any transaction that has successfully read that data item.
Write Timestamp (WTS): The WTS of a data item is the largest timestamp of any transaction that has successfully written to that data item.

Operation Rules in Timestamp-Based Concurrency Control

In TBCC, when a transaction tries to perform a read or write operation on a data item, the system compares the transaction’s timestamp with the RTS and WTS of the data item to decide whether the operation is allowed, aborted, or delayed.

Read Operation

When transaction Ti try to access resource X with timestamp TS

Condition 1: TS ≤ WTS(X): The transaction is reading outdated data, meaning another transaction with a later timestamp has already written to X. then Ti is abort and rollback.

Condition 2: TS ≥ WTS(X): The transaction is allowed to read the data. The RTS of X is updated with TS timestamp (RTS(X) = TS ).

Example

Transaction T1 (with timestamp 5) writes to data item X, setting WTS(X) = 5

Transaction T2 (with timestamp 3) tries to read X. Since TS(T2) is less than WTS(X), T2 is aborted.
Write Operation

When transaction Ti try to write resource X with timestamp TS

Condition 1: TS < RTS(X): The write operation would violate the order of operations, as a transaction with a later timestamp has already read X. then Ti is abort and rollback.

Condition 2: TS < WTS(X): The write operation is ignored because the data item X has already been written by a newer transaction.

Condition 3: TS ≥ WTS(X) and RTS(X): The write operation is allowed. The WTS of X is updated to TS(Ti)

Example

Transaction T1 (with timestamp 7) reads data item X, setting RTS(X) = 7

Transaction T2 (with timestamp 5) tries to write to X, TS (T2) is less than RTS(X) so transaction is aborted and rollback

Transaction T3 (with timestamp 8) tries to write to X, TS (T3) is grater then RTS(X) and WTS(X) so transaction is allow to write or update

Advantage

TBCC does not use locks, so there is no risk of deadlocks occurring.
TBCC can be simpler to implement compared to some lock-based protocols because it avoids the complexities of lock management and deadlock resolution.

Disadvantages

TBCC may result in a higher number of transaction aborts, especially in systems with high contention, as transactions can frequently violate the timestamp order.
TBCC requires maintaining additional information (RTS and WTS) for each data item, leading to higher storage and computational overhead.
Certain transactions, especially those with earlier timestamps, may be repeatedly aborted if they conflict with many other transactions, leading to starvation.

Multiversion Concurrency Control (MVCC)

In this technique, the database maintains versions of the data to handle concurrency. When a transaction updates or adds data, the version of the data changes. This version is maintained in the database and used to manage concurrency.

There are some key concepts which use into MVCC

Versions

Data Item Versions: Every data item in the database can have multiple versions. Each version represents the state of the data item at a particular point in time.
Transaction Timestamps: Each transaction is assigned a unique timestamp or transaction ID (TxID) when it begins. This timestamp is used to identify which version of the data a transaction should see and modify.

Visibility Rules

Readers: A transaction can only see the version of a data item that was committed before the transaction began. This ensures that the transaction operates on a consistent snapshot of the database.
Writers: When a transaction updates a data item, it creates a new version of that data item rather than modifying the existing version. This new version is not visible to other transactions until the transaction commits.

Commit and Garbage Collection

When a transaction commits, its changes (new versions of data items) become visible to other transactions. Old versions that are no longer needed (i.e., versions that are not visible to any active transaction) can be garbage collected or deleted.

How MVCC Works

Scenario

Initial Balance: $1000
Transaction T1 (TS1): Reads the balance.
Transaction T2 (TS2): Updates the balance to $1200.
Transaction T3 (TS3): Reads the balance.
Transaction T4 (TS4): Updates the balance to $1500.

Step-by-step ordering

Initial State:
- The balance is $1000.
- One version exists in the database:
  - Balance: $1000, Timestamp: TS=0
Transaction T1 (TS1):
- T1 starts with a start timestamp TS1.
- T1 reads the balance. Since no other transactions have updated it yet, T1 sees the version of the balance with TS=0, which is $1000.
- T1 does not make any changes and continues with its operations.
Transaction T2 (TS2):
- T2 starts with a start timestamp TS2.
- T2 updates the balance to $1200.
- The database creates a new version of the balance with the value $1200 and tags it with T2’s start timestamp (TS2).
- The previous version (balance = $1000, TS=0) is still retained for transactions that started before T2.
Transaction T3 (TS3):
- T3 starts with a start timestamp TS3.
- T3 attempts to read the balance. Since T3’s start timestamp is greater than T2’s timestamp but T2 has not yet committed, T3 sees the most recent committed version of the balance, which is still $1000 (TS=0).
- T3 does not see the new version created by T2 because T2 has not committed yet.
Transaction T4 (TS4):
- T4 starts with a start timestamp TS4.
- T4 updates the balance to $1500.
- The database creates another new version of the balance with the value $1500 and tags it with T4’s start timestamp (TS4).
- The versions in the database are now:
  - Balance: $1000, TS=0
  - Balance: $1200, TS=TS2 (uncommitted)
  - Balance: $1500, TS=TS4 (uncommitted)
Commit Order:
- T2 Commits: When T2 commits, the version with $1200 becomes visible to subsequent transactions. The versions are now:
  - Balance: $1000, TS=0 (for older transactions)
  - Balance: $1200, TS=TS2 (newly committed)
  - Balance: $1500, TS=TS4 (uncommitted)
- T4 Commits: When T4 commits, its version with $1500 becomes visible. The versions are now:
  - Balance: $1000, TS=0 (for older transactions)
  - Balance: $1200, TS=TS2
  - Balance: $1500, TS=TS4 (newly committed)
Post-Commit State:
- If any new transaction starts after both T2 and T4 have committed, it will see the balance of $1500.

Benefits Of MVCC

Non-Blocking Reads: Both T1 and T3 read the balance without waiting for T2 and T4 to commit, avoiding delays.
Consistent Views: Each transaction operates on a consistent snapshot of the database. T1 and T3 see the initial balance, while T2 and T4 see updated values when they read after writing.
No Locks Needed: Transactions proceed without locking the data, reducing contention and allowing more transactions to proceed in parallel.

Disadvantages of MVCC

Increased Storage Overhead Keeping multiple versions of data items requires additional storage. Although garbage collection helps mitigate this, it still increases the complexity and resource usage of the database.

Complexity in Implementation The implementation of MVCC is more complex than traditional locking mechanisms, which can lead to higher maintenance and debugging costs.

Potential for Long-Running Transactions to Cause Issues Long-running transactions can see outdated data for extended periods, potentially leading to less timely or relevant reads.

Practical Examples

Lock Base Concurrency Control
- When multiple transactions frequently update the same set of data, lock-based concurrency control can effectively prevent conflicts.
- If the application requires strong consistency guarantees, locks ensure that only one transaction can modify a data item at a time.
- Where transactions involve complex operations that need to be executed atomically, locking ensures that other transactions cannot interfere until the transaction is complete.
Timestamp-Based Concurrency Control
- When transactions frequently read and write the same data, TBC ensures that transactions are executed in a logical order based on their timestamps, reducing the chances of conflicts.
- Where transactions must be processed in a strict order to maintain consistency. TBC ensures that the order of transactions reflects the order in which they arrive.
- Where transactions can be easily rolled back and retried if they conflict with others.
Multiversion Concurrency Control
- In applications where reads significantly outnumber writes, MVCC allows reads to proceed without blocking, improving overall performance.
- When applications need to ensure that transactions operate on a consistent snapshot of the database, MVCC allows transactions to see a consistent view of the data as it was when they started.
- Where multiple users interact with the database simultaneously, and the system needs to support high levels of concurrency without sacrificing performance.

Summary Of Use-Case

Lock-Based Concurrency Control: Best for scenarios with high write contention, strict consistency needs, and complex transactions.
Timestamp-Based Concurrency Control: Ideal for real-time systems, applications with high read-write conflicts, and scenarios requiring strict transactional order.
Multi-version Concurrency Control (MVCC): Suited for read-heavy workloads, systems needing snapshot isolation, and high-concurrency environments like OLTP systems.

Conclusion

We explored various concurrency control techniques, including Lock-Based Concurrency Control, Timestamp-Based Concurrency Control, and Multiversion Concurrency Control (MVCC). Detailed explanations and examples were provided to demonstrate how each method handles simultaneous transactions, particularly focusing on scenarios with multiple reads and writes.

Understanding the JWT

Drimil Mendapara — Thu, 08 Aug 2024 03:54:09 +0000

What Is JWT?

JWT stands for json web token, it’s open stander use to transmit information between parties as a JSON object. It is compact, URL-safe, and used extensively in web applications for authentication and information exchange.

JWTs are digitally signed using keys and secrets. We verify the JWT with these keys and the signature to authenticate the user. Most web systems use JWTs to authorize users to access certain resources.

Token Components

A JWT has three main components: the header, the payload, and the signature. When we create a token, we pass the header and payload, and then the token generates the signature.

Headre - The header of a JWT contains metadata about the token. It includes three values: alg, typ, and kid. The alg specifies the algorithm used to sign the token, typ indicates the token type, and kid is an optional parameter used to identify the key. Whether to include kid depends on your use case.

{
  "alg": "RS256", // allow [HS256,RS256,ES256]
  "typ": "JWT", // Specific Type Of token
  "kid": "12345" // Used to indicate which key was used to sign 
the JWT. This is particularly useful when multiple keys are in use
}

Payload - In Payload we specify some custom data mostly add user specific data into payload like user id and role.

{
  "sub": "1234567890",
  "name": "John Doe",
  "iat": 1516239022
}

Signature - The signature is generated by encoding the header and payload with a secret key (for HS256) or signing them with a private key (for RSA), and then hashing the result. This signature is used to verify the token.

How Token Is Created

As we discussed, a JWT has three components: the header, the payload, and the signature. We provide the header and payload, and the signature is generated from them. After combining all these components, we create the token.

// Header Encoding
Base64Url Encode({
  "alg": "RS256",
  "typ": "JWT"
}) → eyJhbGciOiAiUlMyNTYiLCAidHlwIjogIkpXVCJ9


// Payload Encoding
Base64Url Encode({
  "sub": "1234567890",
  "name": "John Doe",
  "iat": 1516239022
}) → eyJzdWIiOiAiMTIzNDU2Nzg5MCIsICJuYW1lIjogIkpvaG4gRG9lIiwgImlhdCI6IDE1MTYyMzkwMjJ9


// Concatenate Encoded header and payload
ConcatenatedHash =  Base64Url Encode(Header) + "." + Base64Url Encode(Payload)

//Create Signature
Hash = SHA-256(ConcatenatedHash)
Signature = RSA Sign(Hash with Private Key) or HS256 Sign(Hash with secrate)

// Create Token
Token = Base64UrlEncode(Header) +"."+ Base64UrlEncode(Payload) +"."+ Signature

So, the process to create a JWT is as follows: we encode the payload and headers, then generate the signature from them.

Verifying JWT Tokens

Earlier, we discussed how to create a JWT. Now, let's discuss how to verify a JWT. The verification process is essentially the reverse of token creation. First, we decrypt the token using a secret or public key. Then, we concatenate the header and payload to generate a signature. If the generated hash matches the signature, the token is valid; otherwise, it is not valid.

// Token we recive in this formate
Token = Base64UrlEncode(Header) +"."+ Base64UrlEncode(Payload) +"."+ Signature

// Decrypt Signature
TokenHash = RSA Decrypt(Hash with Public Key) or HS256 Sign(Hash with secrate)

// Generate Hash From Encoded Header and Payload
Hash = SHA-256(Base64UrlEncode(Header) +"."+ Base64UrlEncode(Payload))

// Compare Hash
if(TokenHash == Hash) "Valid"
else "Not Valid"

Benefits of Using JWT

Security - JWTs are digitally signed, ensuring the integrity and authenticity of the data
Compact - JWTs are small in size, making them efficient to transmit over the network.
Self-Contained - JWTs contain all the necessary information about the user, reducing the need to query the database multiple times.

JWT provides all the above benefits, making it a popular choice for most authentication mechanisms to authorize users. Additionally, JWT can be used with various authentication techniques, such as DPoP and others.

How to Use JWT in Your Code

To use JWT in code, we utilize the jsonwebtoken npm package. There are two methods for working with JWTs: the straightforward method using a secret key and the key pair method (using public and private keys).

Using Secret

import jwt from 'jsonwebtoken';

// Define the type for the payload
interface Payload {
  userId: number;
  username: string;
}

// Secret key for signing the JWT
const secretKey: string = 'your-very-secure-secret';

// Payload to be included in the JWT
const payload: Payload = {
  userId: 123,
  username: 'exampleUser'
};

// Sign the JWT
const token: string = jwt.sign(payload, secretKey, { expiresIn: '1h' });
console.log('Generated Token:', token);

import jwt from 'jsonwebtoken';

// Secret key for signing the JWT
const secretKey: string = 'your-very-secure-secret';

// Verify the JWT
try {
  const decoded = jwt.verify(token, secretKey) as Payload;
  console.log('Decoded Payload:', decoded);
} catch (err) {
  console.error('Token verification failed:', (err as Error).message);
}

Using KeyPair Method

import * as jwt from 'jsonwebtoken';
import { readFileSync } from 'fs';

// Load your RSA private key
const privateKey = readFileSync('private_key.pem', 'utf8');

// Define your payload
const payload = {
  sub: '1234567890',
  name: 'John Doe',
  iat: Math.floor(Date.now() / 1000) // Issued at
};

// Define JWT sign options
const signOptions: jwt.SignOptions = {
  algorithm: 'RS256',
  expiresIn: '1h' // Token expiration time
};

// Generate the JWT
const token = jwt.sign(payload, privateKey, signOptions);
console.log('Generated JWT:', token);

import * as jwt from 'jsonwebtoken';
import { readFileSync } from 'fs';

// Load your RSA public key
const publicKey = readFileSync('public_key.pem', 'utf8');

// Define JWT verify options
const verifyOptions: jwt.VerifyOptions = {
  algorithms: ['RS256'] // Specify the algorithm used
};

try {
  // Verify the JWT
  const decoded = jwt.verify(token, publicKey, verifyOptions) as jwt.JwtPayload;

  console.log('Decoded Payload:', decoded);
} catch (error) {
  console.error('Error verifying token:', error);
}

Conclusion

In summary, JSON Web Tokens (JWTs) securely transmit information between parties using a compact format. RSA signing and verification involve using a private key for signing and a public key for verification. The TypeScript examples illustrate generating a JWT with a private RSA key and verifying it with a public RSA key, ensuring secure token-based authentication and data integrity.