WL#9837: Group Replication: Transaction savepoint support

This worklog goal is to improve Group Replication by adding support to SAVEPOINT.

The SAVEPOINT statement sets a named transaction savepoint with a name of
identifier. If the current transaction has a savepoint with the same name, the
old savepoint is deleted and a new one is set.

The ROLLBACK TO identifier command reverts the state of the transaction back to what
was when executed the command SAVEPOINT identifier.

The RELEASE SAVEPOINT statement removes the named savepoint from the set of
savepoints of the current transaction. No commit or rollback occurs. It returns
an error if the savepoint does not exist.

FR1: SAVEPOINT identifier statement must be supported by Group Replication

FR2: ROLLBACK [WORK] TO [SAVEPOINT] identifier statement must be supported by
     Group Replication

FR3: RELEASE SAVEPOINT identifier statement must be supported by Group
     Replication

FR4: COMMIT command must clear all created SAVEPOINT identifiers.

FR5: ROLLBACK command must clear all created SAVEPOINT identifiers.

FR6: TRIGGER will create a new empty savepoint level, without any identifier
     and restore previous level after executed

FR6: FUNCTION will create a new empty savepoint level, without any identifier

OVERVIEW
========

On this worklog we will implement support for SAVEPOINT command.

All the SAVEPOINT handling is done before COMMIT, this process is done on the
server that received the query before sending to group and consequent
certification step.

DEFINITIONS
===========

Before going into details lets first present the terms that will be
used on this design.

 write set: set of hashes that identify unequivocally the updated
rows by the transaction. Please see High-Level Specification of
WL#6834 for further details.

 savepoint map: a associative container that stores the identifier of SAVEPOINT
as key and the size of write set, when the SAVEPOINT command was executed as value.

 savepoint list: a list of savepoint map, representing the levels that are created
when executing a TRIGGER or a FUNCTION.

TRANSACTION PATH
================

Using examples to better explain the changes and with representations of
write set and savepoint map between the statements.

The table that we will use on test:

  CREATE TABLE t1 (a INT PRIMARY KEY);

The full transaction:

BEGIN;
INSERT INTO t1 VALUES(1);
SAVEPOINT S1;
INSERT INTO t1 VALUES(2);
ROLLBACK TO S1;
RELEASE S1;
COMMIT;

These examples do not use TRIGGER or FUNCTION, thence the savepoint list it is
always empty.

The initial state of write set and savepoint map, after BEGIN statment:

  +-------------------------------+
  |            write set          |
  +-------+-------+-------+-------+
  | index |       |       |       |
  +-------+-------+-------+-------+
  | value |       |       |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |          savepoint map        |
  +-------+-------+-------+-------+
  |  key  |       |       |       |
  +-------+-------+-------+-------+
  | value |       |       |       |
  +-------+-------+-------+-------+

The statement INSERT INTO t1 VALUES(1) will add a new hash and put it on
first position of write set vector.

  +-------------------------------+
  |            write set          |
  +-------+-------+-------+-------+
  | index |   0   |       |       |
  +-------+-------+-------+-------+
  | value | hash1 |       |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |          savepoint map        |
  +-------+-------+-------+-------+
  |  key  |       |       |       |
  +-------+-------+-------+-------+
  | value |       |       |       |
  +-------+-------+-------+-------+

On the SAVEPOINT command the identifier is used as a key on savepoint map with
the current write set size as value. With this information we know what are the
statements that need do be removed from the vector when executed an ROLLBACK
TO.

To the savepoint map is added the key "S1" with value of 1, the size of the
write set vector.

  +-------------------------------+
  |            write set          |
  +-------+-------+-------+-------+
  | index |   0   |       |       |
  +-------+-------+-------+-------+
  | value | hash1 |       |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |          savepoint map        |
  +-------+-------+-------+-------+
  |  key  |  S1   |       |       |
  +-------+-------+-------+-------+
  | value |   1   |       |       |
  +-------+-------+-------+-------+

The transaction continues and has one more INSERT that will add a new entry to
the write set vector, and write set will have a size of 2.

INSERT INTO t1 VALUES(2);

  +-------------------------------+
  |            write set          |
  +-------+-------+-------+-------+
  | index |   0   |   1   |       |
  +-------+-------+-------+-------+
  | value | hash1 | hash2 |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |          savepoint map        |
  +-------+-------+-------+-------+
  |  key  |  S1   |       |       |
  +-------+-------+-------+-------+
  | value |   1   |       |       |
  +-------+-------+-------+-------+

The ROLLBACK TO will remove information from current element of write set
vector until the size of vector when SAVEPOINT was defined.

It will only remove the insert of value 2, the SAVEPOINT S1 continue to
exist.
ROLLBACK TO S1;

  +-------------------------------+
  |            write set          |
  +-------+-------+-------+-------+
  | index |   0   |       |       |
  +-------+-------+-------+-------+
  | value | hash1 |       |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |          savepoint map        |
  +-------+-------+-------+-------+
  |  key  |  S1   |       |       |
  +-------+-------+-------+-------+
  | value |   1   |       |       |
  +-------+-------+-------+-------+

The RELEASE S1 command release the SAVEPOINT from the transaction and we
remove the information from the savepoint map.
The RELEASE command isn't necessary on the end of transaction, all information
about SAVEPOINTs is removed. The statement was executed to point the process of
removing SAVEPOINT identifier from savepoint map.

  +-------------------------------+
  |            write set          |
  +-------+-------+-------+-------+
  | index |   0   |       |       |
  +-------+-------+-------+-------+
  | value | hash1 |       |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |          savepoint map        |
  +-------+-------+-------+-------+
  |  key  |       |       |       |
  +-------+-------+-------+-------+
  | value |       |       |       |
  +-------+-------+-------+-------+

After the COMMIT statment all information, write set and savepoint map are cleared:

  +-------------------------------+
  |            write set          |
  +-------+-------+-------+-------+
  | index |       |       |       |
  +-------+-------+-------+-------+
  | value |       |       |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |          savepoint map        |
  +-------+-------+-------+-------+
  |  key  |       |       |       |
  +-------+-------+-------+-------+
  | value |       |       |       |
  +-------+-------+-------+-------+


Another example:

BEGIN;
INSERT INTO t1 VALUES(3);
SAVEPOINT S1;
INSERT INTO t1 VALUES(4);
SAVEPOINT S2;
INSERT INTO t1 VALUES(5);
ROLLBACK TO S1;
COMMIT;

On this example the difference is the ROLLBACK TO S1 that is previous to the
last SAVEPOINT inserted.

After executing the statement INSERT INTO t1 VALUES(5) the state of write set
and savepoint map is:


  +-------------------------------+
  |            write set          |
  +-------+-------+-------+-------+
  | index |   0   |   1   |  2    |
  +-------+-------+-------+-------+
  | value | hash3 | hash4 | hash5 |
  +-------+-------+-------+-------+

  +-------------------------------+
  |          savepoint map        |
  +-------+-------+-------+-------+
  |  key  |  S1   |  S2   |       |
  +-------+-------+-------+-------+
  | value |   1   |   2   |       |
  +-------+-------+-------+-------+

So before executing the ROLLBACK TO the write set has a size 3, corresponding
to each insert made and the SAVEPOINT map has two pairs key, value: S1,1 and
S2,2.

When executing the ROLLBACK TO S1 all elements after first element on write set
are removed.

To prevent leaving references to SAVEPOINT that were removed, when executing a
ROLLBACK the map with information of SAVEPOINT is iterated to remove all
SAVEPOINTs more recent to the SAVEPOINT that is being executed the ROLLBACK, in
this case the SAVEPOINT S2 will be removed.

  +-------------------------------+
  |            write set          |
  +-------+-------+-------+-------+
  | index |   0   |       |       |
  +-------+-------+-------+-------+
  | value | hash3 |       |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |          savepoint map        |
  +-------+-------+-------+-------+
  |  key  |  S1   |       |       |
  +-------+-------+-------+-------+
  | value |   1   |       |       |
  +-------+-------+-------+-------+

After the COMMIT statment all information, write set and savepoint map are cleared:

  +-------------------------------+
  |            write set          |
  +-------+-------+-------+-------+
  | index |       |       |       |
  +-------+-------+-------+-------+
  | value |       |       |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |          savepoint map        |
  +-------+-------+-------+-------+
  |  key  |       |       |       |
  +-------+-------+-------+-------+
  | value |       |       |       |
  +-------+-------+-------+-------+


An example using TRIGGER to better demonstrate the concept of SAVEPOINT levels
and the state of savepoint list.

Using the following SQL code as example:

DELIMITER |;

CREATE TRIGGER t1_tr1 BEFORE INSERT ON t1 FOR EACH ROW
BEGIN
  INSERT INTO t1 VALUES (NEW.c1 + 100);
  SAVEPOINT S1;
  INSERT INTO t1 VALUES (100);
  ROLLBACK TO S1
END|

DELIMITER ;|

BEGIN
SAVEPOINT S1; [1]
INSERT INTO t1 VALUES(1);
ROLLBACK TO S1;
INSERT INTO t1 VALUES(2);
COMMIT;

To better illustrate the savepoint list functionality it will be added a name
to savepoint map, then it will used to represent the savepoint map when is
stored on savepoint list.

The initial state of write set, savepoint map and savepoint list, after BEGIN
statment:

  +-------------------------------+
  |            write set          |
  +-------+-------+-------+-------+
  | index |       |       |       |
  +-------+-------+-------+-------+
  | value |       |       |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |       savepoint map - L0      |
  +-------+-------+-------+-------+
  |  key  |       |       |       |
  +-------+-------+-------+-------+
  | value |       |       |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |          savepoint list       |
  +-------+-------+-------+-------+
  | value |       |       |       |
  +-------+-------+-------+-------+

On the SAVEPOINT [1] command the identifier is used as a key on savepoint map with
the current write set size as value.

  +-------------------------------+
  |            write set          |
  +-------+-------+-------+-------+
  | index |       |       |       |
  +-------+-------+-------+-------+
  | value |       |       |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |       savepoint map - L0      |
  +-------+-------+-------+-------+
  |  key  |   S1  |       |       |
  +-------+-------+-------+-------+
  | value |   0   |       |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |          savepoint list       |
  +-------+-------+-------+-------+
  | value |       |       |       |
  +-------+-------+-------+-------+

Before the execution of INSERT INTO t1 VALUES(1) it launched the trigger
t1_tr1, this will create a new level and execute the statement presents on the
trigger.

So entering on trigger the new level is created and the state of variables is
set to:

  +-------------------------------+
  |            write set          |
  +-------+-------+-------+-------+
  | index |       |       |       |
  +-------+-------+-------+-------+
  | value |       |       |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |       savepoint map - L1      |
  +-------+-------+-------+-------+
  |  key  |       |       |       |
  +-------+-------+-------+-------+
  | value |       |       |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |          savepoint list       |
  +-------+-------+-------+-------+
  | value |  L0   |       |       |
  +-------+-------+-------+-------+

The statements present on trigger:

  INSERT INTO t1 VALUES (NEW.c1 + 100);
  SAVEPOINT S1;
  INSERT INTO t1 VALUES (100);
  ROLLBACK TO S1

Will set the current state:

  +-------------------------------+
  |            write set          |
  +-------+-------+-------+-------+
  | index |   0   |       |       |
  +-------+-------+-------+-------+
  | value |  101  |       |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |       savepoint map - L1      |
  +-------+-------+-------+-------+
  |  key  |  S1   |       |       |
  +-------+-------+-------+-------+
  | value |   1   |       |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |          savepoint list       |
  +-------+-------+-------+-------+
  | value |  L0   |       |       |
  +-------+-------+-------+-------+

After trigger is executed the savepoint map need to return where is was before
entered on trigger. So when start to execute INSERT INTO t1 VALUES(1) the state
is:

  +-------------------------------+
  |            write set          |
  +-------+-------+-------+-------+
  | index |   0   |       |       |
  +-------+-------+-------+-------+
  | value |hash101|       |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |       savepoint map - L0      |
  +-------+-------+-------+-------+
  |  key  |  S1   |       |       |
  +-------+-------+-------+-------+
  | value |  0    |       |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |          savepoint list       |
  +-------+-------+-------+-------+
  | value |       |       |       |
  +-------+-------+-------+-------+

And after execute INSERT INTO t1 VALUES(1) the state is:

  +-------------------------------+
  |            write set          |
  +-------+-------+-------+-------+
  | index |   0   |   1   |       |
  +-------+-------+-------+-------+
  | value |hash101| hash1 |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |       savepoint map - L0      |
  +-------+-------+-------+-------+
  |  key  |  S1   |       |       |
  +-------+-------+-------+-------+
  | value |  0    |       |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |          savepoint list       |
  +-------+-------+-------+-------+
  | value |       |       |       |
  +-------+-------+-------+-------+

After executing the ROLLBACK TO S1:

  +-------------------------------+
  |            write set          |
  +-------+-------+-------+-------+
  | index |       |       |       |
  +-------+-------+-------+-------+
  | value |       |       |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |       savepoint map - L0      |
  +-------+-------+-------+-------+
  |  key  |  S1   |       |       |
  +-------+-------+-------+-------+
  | value |  0    |       |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |          savepoint list       |
  +-------+-------+-------+-------+
  | value |       |       |       |
  +-------+-------+-------+-------+

The procedure for the last INSERT statement is equal to what was explained
previously and the result before COMMIT is:

  +-------------------------------+
  |            write set          |
  +-------+-------+-------+-------+
  | index |  0    |   1   |       |
  +-------+-------+-------+-------+
  | value |hash102| hash2 |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |       savepoint map - L0      |
  +-------+-------+-------+-------+
  |  key  |  S1   |       |       |
  +-------+-------+-------+-------+
  | value |  0    |       |       |
  +-------+-------+-------+-------+

  +-------------------------------+
  |          savepoint list       |
  +-------+-------+-------+-------+
  | value |       |       |       |
  +-------+-------+-------+-------+

All information is cleared after processing the COMMIT or ROLLBACK statements.

The workflow for using FUNCTION is the same, the level is created when the

SUMMARY OF CHANGES
==================

Server core changes
-------------------

  1. Add to class RPL transaction context a std::map, savepoint_map, that
     contains information related to SAVEPOINTs. The key on map is the
     identifier and the value is the size of write set when command

  2. We will use the write_set vector from class RPL transaction context as a
     timeline to the commands executed and remove items when a ROLLBACK is
     used.

  3. Methods will be added to be executed when processing the SAVEPOINT related
     commands:

     * add_savepoint: when SAVEPOINT identifier is processed, it will add the
       current size of vector to savepoint_map with identifier as key

     * del_savepoint: when RELEASE SAVEPOINT identifier is processed, it will
       remove the identifier from the savepoint_map

     * rollback_to_savepoint: when a ROLLBACK TO identifier is processed, we
       use the identifier to return the size of write_set when SAVEPOINT was
       executed. All the elements from write_set inserted after that savepoint
       will be removed. After that the savepoint_map will be iterated to remove
       all SAVEPOINTs added after the identifer on ROLLBACK.

  4. On COMMIT/ROLLBACK commands all information is cleaned. The write_set is
     being cleared when called Rpl_transaction_write_set_ctx::clear_write_set()
     and will be added a savepoint.clear() to clear all information related to
     SAVEPOINT commands.

  5. When executing Trigger or Functions it's needed to create a new level of
     SAVEPOINT to don't overwrite the already created. To do this it was added
     to class RPL transaction context a std::list, savepoint_list. It will be
     added two methods to make the reset and restore:

     * reset_savepoint_list: make a backup of savepoint_map on savepoint_list
       and clean it to create a new SAVEPOINT identifier level

     * restore_savepoint_list: restore last level and remove it from
       savepoint_list

Class diagram
-------------

The class diagram for Rpl_transaction_write_set_ctx after modifications:

class Rpl_transaction_write_set_ctx {
public:
  Rpl_transaction_write_set_ctx()
  virtual ~Rpl_transaction_write_set_ctx()
  void add_write_set(uint64 hash);
  std::vector *get_write_set();
  void clear_write_set();
  void add_savepoint(THD *thd, char* name);              /*  new method  */
  void del_savepoint(THD *thd, char* name);              /*  new method  */
  void rollback_to_savepoint(THD *thd, char* name);      /*  new method  */
  void restore_savepoint_list(THD *thd);                 /*  new method  */
  void reset_savepoint_list(THD *thd);                   /*  new method  */
private:
  std::vector write_set;
  std::map savepoint;                 /* new variable */
  std::list> savepoint_list; /* new variable */

}

Sequence diagram
----------------

The methods will be called from transcion.cc where the SAVEPOINT commands are
processed by the server, a simple sequence diagram:

sql/transaction.cc
    trans_savepoint()
      |- server code ...
      `- add_savepoint() @ sql/rpl_transaction_write_set_ctx.cc

sql/transaction.cc
    trans_release_savepoint
      |- server code ...
      `- del_savepoint() @ sql/rpl_transaction_write_set_ctx.cc

sql/transaction.cc
    trans_rollback_to_savepoint
      |- server code ...
      `- rollback_to_savepoint @ sql/rpl_transaction_write_set_ctx.cc

To support the creation and restore of levels when processing TRIGGER and
FUNCTION it where added calls on sql_class.cc:

sql/sql_class.cc
    reset_sub_statement_state()
      |- server code ...
      `- reset_savepoint_list() @ sql/rpl_transaction_write_set_ctx.cc

sql/sql_class.cc
    restore_sub_statement_state()
      |- server code ...
      `- restore_savepoint_list() @ sql/rpl_transaction_write_set_ctx.cc

The methods that give support for SAVEPOINT on Group Replication will be added
after server error handling, avoiding problems like ROLLBACK TO identifiers