The payload comprises the actual table columns and their values for the row.<\/p>\n
I\u2019ve left out most of the header fields to focus on the two directly involved in row visibility. Both Begin Timestamp (Begin-T<\/b>s) and End Timestamp (End-Ts<\/b>) are monotonically increasing database-wide numbers that serialize the time at which transactions that create and delete rows commit their work.\u00a0 I\u2019ll refer to row versions only by their transaction serial numbers: <Begin-T<\/b>s, End-Ts<\/b>>; the payload does not play a role in visibility.<\/p>\n
We\u2019ll soon see where these numbers come from, but for now let\u2019s try an example.\u00a0 I\u2019ll also use the terms row<\/i> and row version<\/i> interchangeably throughout.<\/p>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <10, \u221e<\/span>><\/p>\n \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <31, 240><\/p>\n The upper row was inserted by a transaction that committed at timestamp 10, and the infinity symbol for the end timestamp means that no transaction has deleted this row; this row version is currently in the table.\u00a0 The lower row was inserted by a transaction that committed at a later point in time\u2014at transaction serial time 31\u2014and was deleted by a transaction having commit timestamp 240.<\/p>\n The payload in an in-memory row can never change.\u00a0 To update column values, the End-Ts<\/b> for the current row version (remember, End-Ts<\/b> is \u221e<\/span>) is marked with the transaction\u2019s commit timestamp, and a new row with the updated payload columns is inserted with Begin-T<\/b>s having the same commit timestamp and infinity for the End-Ts<\/b>.\u00a0 These two operations are done in one atomic step.<\/p>\n \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <31467, \u221e<\/span>><\/p>\n \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <20000, 31467><\/p>\n \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <10, 20000><\/p>\n In this sample, if all three rows have the same primary key\u2014which, in in-memory tables, are immutable \u2014then the lowest row would be the row\u2019s insertion, and those above it resulted from two updates in separate transactions committing at timestamps 20000 and 31467 respectively. \u00a0If the keys are different, then the bottom row was inserted by an early transaction, then deleted by a later transaction, which also inserted the middle row, and the top row was inserted by a transaction with the latest commit timestamp, and this transaction also deleted the middle row.<\/p>\n The samples imply that although the in-memory OLTP engine works with INSERT<\/b>, UPDATE<\/b>, and DELETE<\/b> modification statements, they reduce to operations insert <C-Ts, \u221e<\/span>><\/b> and (logical) delete <original C-Ts, C-Ts><\/b>, where C-Ts is the commit timestamp of the transaction doing the work.<\/p>\n Timestamps Begin-T<\/b>s and End-Ts<\/b> are gotten from a counter of type bigint<\/b> known as the Global Transaction Timestamp (GTTs).\u00a0 Its value at any moment was the one given to the latest transaction that issued a commit.\u00a0 (For implicit and explicit transactions, the COMMIT TRAN<\/b> statement is part of the code, and for single-statement autocommit and atomic block statements used with natively compiled procedures, it is written in automatically.)<\/p>\n Here are its rules:<\/p>\n We now have enough information to understand row visibility.span style=”mso-spacerun:yes”>\u00a0 The <Begin-T<\/b>s, End-Ts<\/b>> pair is the validity interval.\u00a0 A transaction may access a row version if its position in the transaction serial order is at least as great as that of the transaction that created the row, and less than the transaction that deleted it, if any; i.e. its order falls within the validity interval of the row:<\/p>\n Begin-T<\/b>s <= logical read time < End-Ts<\/b>.\u00a0<\/p>\n In the three-row sample above, validity intervals for all row versions are disjoint, so a transaction with logical read time of at least 10 could see exactly one of the rows.\u00a0 By contrast, given intervals <50, 80><\/b>, <60, \u221e<\/span>><\/b>, a transaction with logical read time from 60 to 79 could see both rows (and the versions can\u2019t share the same primary key).<\/p>\n These concepts are sufficient for row visibility\u2014but only in a static database.\u00a0 In-memory OLTP is meant to increase performance in (highly) transactional systems, though, so let\u2019s look at behavior of transactions running together.<\/p>\n For the examples, rows x <\/b>and y <\/b>have these begin<\/b> and end<\/b> timestamps in their current versions before the transactions start:<\/p>\n \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 X: <10, \u221e<\/span>><\/p>\n \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Y: <676, \u221e<\/span>><\/p>\n I\u2019ll use a modified schedule representation to show interleaving of operations:<\/p>\n When transaction i–txn-i<\/b> for short\u2014commits, say it gets timestamp 12345; these are the new row versions:<\/p>\n \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 X: <10, 12345><\/p>\n \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 —————–<\/p>\n \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Y: <12345, \u221e<\/span>><\/p>\n \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 <676, 12345><\/p>\n If no other transactions commit between the time txn-i <\/b>commits and txn-k <\/b>starts, the latter will get the logical read time 12345; else it will be greater.\u00a0 In either case, by the formula txn-k <\/b>reads the newly inserted y <\/b>row version having interval <12345, \u221e<\/span>><\/b> and x <\/b>is not visible.<\/p>\n Now let\u2019s interleave the transactions\u2019 operations:<\/p>\n If txn-i<\/b> gets the same commit timestamp, then this time the logical read time for txn-k<\/b> must be less than 12345.\u00a0 In this case, for the y <\/b>row it reads the deleted version, <676, 12345>.<\/b>\u00a0 It had already read the x <\/b>version whose header values were <10, \u221e<\/span>>.\u00a0 <\/b>If it were to re-read the row later, it would access the same version, now with interval <10, 12345>.<\/b>\u00a0 Which is also correct:<\/p>\n All rows [re-]read by a transaction remain consistent as of a single point in time\u2014at transaction start.\u00a0 Providing consistent read sets (snapshots) is the rationale for row versioning.<\/p>\n Now imagine that in either schedule txn-k<\/b> reads both x <\/b>and y <\/b>before txn-i<\/b> commits; for example:<\/p>\n Because txn-i<\/b> doesn\u2019t have a commit timestamp while it inserts and deletes rows, affected Begin-T<\/b>s and End-Ts<\/b> values are unknown when txn-k<\/b> reads the rows, which it can do immediately in an optimistic, non-blocking system.\u00a0 The basic row visibility formula cannot be applied.<\/p>\n Even the original schedules can have this problem.\u00a0 Though txn-i<\/b> does have the commit timestamp, there is a lag time, as we\u2019ll see, before the in-memory OLTP engine can write commit timestamps to headers.\u00a0 In this case, if we imagine txn-i<\/b> affecting thousands of rows, txn-k<\/b> can read some headers with complete interval values and some having unknown values.\u00a0 To make it worse, txn-i<\/b> can issue a rollback or be aborted in a post-commit phase.<\/p>\n When validity intervals are incomplete, how does a reader know which schedule is in effect and what action to take?<\/p>\n When a transaction starts, it gets the timestamp value of the last transaction issuing a commit from the GTTs counter, which is its logical read time.\u00a0 It also gets, from the in-memory OLTP engine, a unique, serial transaction identifier.\u00a0 For a transaction k<\/b>, I\u2019ll refer to it as txn-k<\/b> ID.\u00a0\u00a0\u00a0 The identifier counter is of type bigint<\/b>, incrementing for each new transaction involving in-memory structures.\u00a0 Unlike the GTTs, it isn\u2019t persisted between instance startups (because there is no need to identify non-existent transactions).<\/p>\n Our second puzzle piece is the lifecycle of an MVCC transaction.\u00a0 At the 30,000 feet elevation, imagine it as having three phases:<\/p>\n The Active phase starts with the transaction, and ends when the COMMIT (or ROLLBACK) command is reached.<\/p>\n As each insert and delete operation is performed during the Active phase, affected rows immediately receive the transaction\u2019s unique identifier in the appropriate header timestamp fields, along with a bit flag signaling that the value is an identifier not a timestamp.\u00a0 This is a significant placeholder as we\u2019ll see\u2014the unknown from the previous section\u2014that will later be replaced by the commit timestamp upon successful completion.<\/p>\n For row x <10, \u221e<\/span>><\/b> consider this schedule and timeline for reader txn-k<\/b> and writer txn-i<\/b>:<\/p>\n The timeline is meant to show txn-k<\/b> starting before txn-i<\/b>, at the same time, or later but before txn-i<\/b> reaches the COMMIT command.\u00a0 Here are the versions of x <\/b> after update:<\/p>\n \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <txn-i<\/b> ID, \u221e<\/span>><\/p>\n \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <10, txn-i<\/b> iD><\/p>\n If txn-i<\/b> successfully commits, then its commit timestamp must be greater than the logical read time for txn-k<\/b>.\u00a0 Therefore, in each read, txn-k<\/b> accesses the same original row version: first with interval <10, \u221e<\/span>>,<\/b> then <10, txn-i ID><\/b>, then <10, C-Ts><\/b> if the commit timestamp replaces the transaction identifier in time, or <10, txn-i ID<\/b>> again if not.\u00a0 Were txn-i<\/b> to rollback or fail, internal code will reset the End-Ts<\/b> to \u221e<\/span><\/b> in the original row.\u00a0 In either case, reader txn-k<\/b> is unaffected by concurrently running writer txn-i<\/b>.<\/p>\n Let\u2019s add this rule to our basic visibility rule:<\/p>\n For txn-k<\/b> and txn-i<\/b>: txn-k<\/b> can read <C-Ts, txn-i ID><\/b> when C-Ts <= txn-k<\/b>\u2019s logical read time and their Active phases overlap.<\/p>\n Then this must also be true:<\/p>\n \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 txn-k<\/b> cannot read <txn-i ID, \u221e<\/span>> <\/b>when their Active phases overlap.<\/p>\n Logical read time for txn-k<\/b> must be before the newly inserted row\u2019s validity interval when txn-i<\/b> commits.\u00a0 If the writer rolls back or fails for any reason, row <txn-i ID, \u221e<\/span>> <\/b>will be inaccessible\u2014marked for garbage collection.<\/p>\n Now let\u2019s consider row visibility when readers start during writers\u2019 Validate<\/b> phase.\u00a0 We adjust the concurrency timeline thus:<\/p>\n Reader txn-k<\/b> starts on or after txn-i<\/b>\u2019s commit statement but before its final resolution point, and ends anytime afterward.\u00a0 Before we can examine visibility, though, we need a little understanding of the Validate<\/b> phase.<\/p>\n The in-memory OLTP engine performs these actions during validation: check for transaction isolation level violations; wait for \u2018commit dependencies\u2019 to clear\u2014which I\u2019ll explain in a moment; and write modifications to the log upon successful outcome (depending on table durability; not covered).\u00a0\u00a0 But any of these steps can fail, although rarely.\u00a0 In this case the engine rolls back the transaction and marks it ABORTED; else, it marks it COMMITTED.\u00a0 Therefore, when txn-k<\/b> reads a row version inserted by txn-i<\/b> before txn-i<\/b> reaches the final committed\/aborted point, although the commit timestamp is available, the row\u2019s status is unknown and the reader takes a commit dependency on the writer.<\/p>\n If the writer aborts, the reader has essentially done an unsuccessful dirty read.\u00a0 Row versions with validity interval <C-Ts, txn-i ID><\/b> and logical read time for txn-k >= C-Ts<\/b> should have been visible but weren\u2019t because the engine will put back the infinity value where the transaction ID is.\u00a0 When the engine rolls back txn-i<\/b> it must also roll back txn-k<\/b>.\u00a0 It will also make rows with intervals <txn-i ID, \u221e<\/span>> <\/b>invisible to readers by marking them for garbage collection.<\/p>\n Rows visible to txn-k<\/b> instead have intervals <txn-i ID, \u221e<\/span>><\/b> because txn-k<\/b>\u2019s logical read time is >= txn-i<\/b>\u2019s commit timestamp and the engine optimistically assumes txn-i<\/b> will be committed.\u00a0 After txn-i<\/b> is marked committed, the commit dependency that reader txn-k<\/b> had on it is released.\u00a0 If txn-k<\/b> is in its own Validate<\/b> phase before txn-i<\/b> resolves, it may wait, however briefly, for the commit dependency to clear.<\/p>\n To make a rule of this:<\/p>\n For txn-k<\/b> and txn-i<\/b>: txn-k<\/b> can read <txn-i<\/b> ID, \u221e<\/span>> with commit dependency when it starts during txn-i<\/b>\u2019s Validate phase<\/p>\n Certainly:<\/p>\n \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 txn-k<\/b> cannot read <C-Ts, txn-i<\/b> ID> when it starts during txn-i<\/b>\u2019s Validate phase\u00a0\u00a0\u00a0<\/p>\n Commit dependencies form chains of two or more transactions; think of it as directed acyclic graphs.\u00a0 The acyclic part means no deadlocking.\u00a0 There is no deadlocking in in-memory OLTP.\u00a0 Period.<\/p>\n In the final phase, reader txn-k<\/b> starts on or after Txn-i<\/b>\u2019s Validate phase finishes with the COMMITTED or ABORTED result, and ends anytime afterward.\u00a0<\/p>\n The way I\u2019ve structured the lifecycle of a transaction, resolution begins when the transaction is committed or aborted, and (if committed) it can start releasing commit dependencies held by readers.\u00a0 It may be more common to think of the release of commit dependencies as ending the validation phase; I\u2019ve placed it here to show that a reader transaction starting in my Resolve<\/b> phase doesn\u2019t take out a commit dependency on the writer because the writer\u2019s outcome is known and was made permanent.\u00a0 Only the order of operations is important: first write to log, then mark transaction as committed, then release commit dependencies.<\/p>\n For txn-k<\/b> and txn-i<\/b>: txn-k<\/b> can read <txn-i ID, \u221e<\/span>> <\/b>when it starts during txn-i<\/b>\u2019s Resolve phase and txn-i<\/b>\u2019s state is committed<\/p>\n Also:<\/p>\n txn-k<\/b> can read <C-Ts, txn-i ID><\/b> when it starts during txn-i<\/b>\u2019s Resolve phase and txn-k<\/b>\u2019s logical read time >= C-Ts and txn-i<\/b>\u2019s state is aborted<\/p>\n After releasing commit dependencies, the engine replaces the transaction IDs in row header fields with commit timestamps and clears the transaction ID bit flags. \u00a0(You may know this final operation as being in the post-processing or commit processing phase.)<\/p>\n This model is sufficient to ensure that transactions always read the right row versions, and when failure happens, that the in-memory OLTP engine can take corrective action.\u00a0 To fulfill the implementation, the third puzzle piece is no surprise: the engine must have metadata to track logical read times, commit timestamps and transaction states.\u00a0 The data is in a table known as the global transaction table (GTTbl<\/b>), and we can access it through a dynamic management view (DMV), sys.dm_db_xtp_transaction<\/b>s.\u00a0 Table 1 shows sample readout with most columns elided:<\/p>\n The column meanings are as follows:<\/p>\n When a transaction comes to a row that otherwise meets the constraint conditions of its query or modification statement and has a transaction ID in either of the Begin-T<\/b>s or End-Ts<\/b> header fields, it finds the row writer\u2019s transaction in the GTTbl<\/b> by matching the transaction ID to the unique xtp_transaction<\/b> column.\u00a0 It then compares this transaction\u2019s end_tsn to its own logical read time and takes into account the state column in deciding if the row is visible.\u00a0 The decision, of course, is based upon the rules we\u2019ve developed.<\/p>\n For example, referring back to Schedule 4 and discussion, txn-k<\/b>\u2019s first read[x] <\/b>accesses row version <10, \u221e<\/span>><\/b> without need of the GTTbl<\/b>.\u00a0 After txn-i<\/b> updates x, the second read[x]<\/b> finds versions <10, txn-i iD><\/b> and <txn-i ID, \u221e<\/span>><\/b> and so matches the ID to the corresponding xtp_transaction<\/b> column in the GTTbl<\/b> to get txn-i<\/b>\u2019s row.\u00a0 Because the state_desc<\/b> column shows ACTIVE, read[x]<\/b> yields the (same) <10, txn-i iD><\/b> version. When txn-i<\/b> commits and txn-k<\/b> does the third read, there is a timing issue: either of the row interval IDs may not yet have been replaced with the C-Ts.\u00a0 In this case, txn-i<\/b>\u2019s state_desc<\/b> is VALIDATING<\/b> or COMMITTED<\/b> (or ABORTED<\/b>) and so the engine can use the end_tsn<\/b> to pick the (same) visible row version.<\/p>\n We\u2019ve seen how begin and end timestamps in row metadata define the row\u2019s validity interval and allow for row versioning.\u00a0 This along with transaction logical read times define visibility.\u00a0 However, by examining schedules we saw that validity intervals can be incomplete.\u00a0 The solution I used to deduce visibility centered on a three-part model of transaction processing.\u00a0 Finally, we saw a DMV that showed how SQL Server tracks transaction metadata to make the MVCC work.<\/p>\n This article was all conceptual; no T-SQL were harmed during its production.\u00a0 For row visibility explained with T-SQL samples and further information, see references next.<\/p>\n Delaney, K., SQL Server Internals: In-Memory OLTP Inside the SQL Server 2014 Hekaton Engine<\/span><\/i>, Simple Talk Publishing, Cambridge, 2014, 215 p.<\/p>\n Korotkevich, D., Expert SQL Server In-Memory OLTP Revolutionizing OLTP Performance in SQL Server<\/span><\/i>, APress, New York, 2015, 248 p.<\/p>\n Miranda, M., 2016, In-Memory OLTP \u2013 Part 3 Row Structure and Indexes, Simple Talk<\/i>, https:\/\/www.simple-talk.com\/sql\/database-administration\/in-memory-oltp—row-structure-and-indexes\/<\/a> (August 16, 2016)<\/p>\n\n
A Timing Issue<\/h3>\n
<\/span><\/p>\n
<\/span><\/p>\n
<\/span><\/p>\n
Two Puzzle Pieces<\/h3>\n
<\/span><\/p>\n
The Active Phase<\/h4>\n
<\/span><\/p>\n
The Validate Phase<\/h4>\n
<\/span><\/p>\n
The Resolve Phase<\/h4>\n
<\/span><\/p>\n
The Third Interlocking Puzzle Piece<\/h3>\n
<\/span><\/p>\n
\n
Final Word<\/h3>\n
References<\/h3>\n