If tempdb runs out of space, do transactions that need version store space fail, or do they wait for space to be freed?
A transaction may get rolled back if the version store needs space and runs out. It won't wait for space in the version store, and really you wouldn't want it to wait.
Typically the version store is used by transactions with isolation levels that use optimistic locking (Snapshot isolation or read committed snapshot isolation for example). The intent in using these is usually to prevent readers from blocking writers in highly transactional databases, but if a writer has to wait for version store space to be freed it could cause extensive blocking of other writers and could conceivably become endlessly blocked. Instead, these transactions are rolled back.
The following errors arise from running out of tempdb space for the version store:
3959 - Version store is full. New version(s) could not be added. A transaction that needs to access the version store may be rolled back. Please refer to BOL on how to configure tempdb for versioning. 3966 - Transaction is rolled back when accessing version store. It was earlier marked as victim when the version store was shrunk due to insufficient space in tempdb. This transaction was marked as a victim earlier because it may need the row version(s) that have already been removed to make space in tempdb. Retry the transaction 3967 - Insufficient space in tempdb to hold row versions. Need to shrink the version store to free up some space in tempdb. Transaction (id=%I64d xsn=%I64d spid=%d elapsed_time=%d) has been marked as victim and it will be rolled back if it accesses the version store. If the problem persists, the likely cause is improperly sized tempdb or long-running transactions. Please refer to BOL on how to configure tempdb for versioning.
As described in the error message, 3967 indicates that the version store has run out of space in tempdb and a specific transaction has been marked as the victim. This transaction will be rolled back if it hits the version store. If the open transaction does not modify any additional rows, requiring rows to be added to the version store, then it isn't rolled back.
3966 indicates a marked transaction (from 3697) has tried to access the version store and was subsequently rolled back.
3959 indicates that tempdb doesn't have enough space to hold the version store but there hasn't been a transaction marked as a victim as yet (meaning tempdb is out of space but no transactions tried to access the version store). Existing transactions would be unaffected but new transactions that need the version store would be rolled back.