Implementing Software Transactional Memory (STM) in Python

Software Transactional Memory (STM) provides a concurrency control mechanism that allows multiple threads to access shared memory concurrently while ensuring atomicity, consistency, isolation, and durability (ACID) properties. This challenge asks you to implement a simplified version of STM in Python, enabling safe concurrent modifications to shared data structures. Implementing STM can significantly simplify concurrent programming by abstracting away the complexities of locks and semaphores.

Problem Description

You are tasked with creating a basic STM system in Python. The system should allow multiple threads to read and modify shared data. Modifications are grouped into transactions. A transaction is considered atomic: either all changes within the transaction are applied, or none are. The system must ensure that concurrent transactions do not interfere with each other, preventing data corruption.

The core components of your STM implementation should include:

1. Transaction Manager: This component manages the lifecycle of transactions. It should provide methods to begin a transaction, commit a transaction, and abort a transaction.
2. Versioned Data: Shared data should be stored in a way that allows for version tracking. Each data item should have a version number. When a transaction modifies a data item, a new version is created.
3. Conflict Detection: Before committing a transaction, the system must check for conflicts. A conflict occurs if another transaction has modified a data item that the current transaction also read or wrote.
4. Rollback: If a conflict is detected, the current transaction must be aborted, and its changes discarded.

Key Requirements:

• The STM system should support reading and writing to a dictionary of shared data.
• Transactions should be executed within a context manager (using with statement).
• The system should detect conflicts between concurrent transactions.
• If a conflict is detected, the transaction should be aborted, and an exception should be raised.
• The system should provide a mechanism to retry a failed transaction.

Expected Behavior:

• When a transaction begins, it should acquire a transaction ID.
• When a transaction reads a data item, it should store the item's version number.
• When a transaction writes a data item, it should create a new version of the item and update the version number.
• Before committing a transaction, the system should check if any of the data items read or written by the transaction have been modified by another transaction since the transaction began.
• If a conflict is detected, the transaction should be aborted, and a TransactionAbortedError exception should be raised.
• If no conflict is detected, the transaction should be committed, and the changes should be applied to the shared data.

Edge Cases to Consider:

• Concurrent transactions attempting to modify the same data item.
• Transactions reading the same data item but writing different values.
• Transactions attempting to commit after another transaction has already committed.
• Handling exceptions within a transaction.

Examples

Example 1:

Input: Two threads. Thread 1 reads 'x' from shared_data, then writes 'x' with a new value. Thread 2 reads 'x' before Thread 1 writes, then attempts to write 'x' with a different new value.
Output: Thread 1 commits successfully. Thread 2 raises TransactionAbortedError.
Explanation: Thread 1's write creates a new version of 'x'. Thread 2 detects the version change and aborts its transaction.

Example 2:

Input: Two threads. Thread 1 reads 'x' and 'y'. Thread 2 reads 'x' and writes 'y'. Thread 1 attempts to write 'x'.
Output: Thread 2 commits successfully. Thread 1 raises TransactionAbortedError.
Explanation: Thread 2 modifies 'y', which is not read by Thread 1, so Thread 2 commits. Thread 1 attempts to write 'x' after Thread 2 has modified a different value, causing Thread 1 to abort.

Example 3: (Edge Case - Nested Transactions)

Input: A thread starts a transaction, then within that transaction starts another transaction. The inner transaction attempts to modify a value. The outer transaction then attempts to commit.
Output: The inner transaction should commit successfully, and the outer transaction should also commit successfully.
Explanation:  Nested transactions should be supported, with the outer transaction committing after the inner transaction completes.

Constraints

• The shared data must be stored in a Python dictionary.
• The version numbers must be integers.
• Transactions must be executed within a context manager.
• The system must handle concurrent transactions safely.
• The implementation should be reasonably efficient (avoiding unnecessary overhead). While absolute performance isn't the primary focus, avoid extremely inefficient data structures or algorithms.
• The TransactionAbortedError exception must be custom-defined.

Notes

• This is a simplified STM implementation. Real-world STM systems are significantly more complex.
• Consider using a dictionary to store the version numbers of the data items.
• Think about how to efficiently detect conflicts between transactions.
• The retry mechanism is not required for this challenge, but it's a common feature of STM systems.
• Focus on correctness and clarity of the code. Good error handling and documentation are important.
• The context manager implementation is crucial for ease of use. Ensure the __enter__ and __exit__ methods are implemented correctly.