WL#10955: server-side generated document-ids

Affects: Server-8.0   —   Status: Complete   —   Priority: Medium

Motivation
==========

The document-id generated by the client is using UUIDs which means different 
clients can generate completely different document-id sequences,
even if they might be sequential (monotonically incrementing) for a single client.

This poses an additional issue for InnoDB, because non-sequential primary keys 
cause performance.

InnoDB 
------

That document-id is used as PRIMARY KEY in the underlying table of the
document's collection.

InnoDB uses organizes

* rows in pages,
* pages as a tree
* sorted by row_id == PRIMARY KEY value.

To get the best insert performance, inserts should result in as little
page-splits and tree-reorgs as possible.

That's achieved by using monotonically increasing document-ids across
all clients.

Auto-increment ids have this property, but aren't globally unique which is
need to allow sharding the collection across multiple servers.

Goal
====

* Make inserts of documents take more or less constant time.
* Introduce a way to generate document-ids on the server-side in a monotonically increasing, globally unique way.
* Keep the globally unique property of document-ids
* Keep existing clients working that send a document-id
Functional Requirements
====

F1 - The _id of a document must behave as any other field of the document during queries, except that its value may not change once inserted

F2 - The _id field may be used as the primary key of the collection (via stored generated columns)

F3 - It must be possible for the user to provide a value for _id when a document is inserted to a collection

F4 - If an _id field value is not present in an inserted document, the server must generate an _id value

F5 - The _id value used for a document must be returned to the client as part of the document insert result message

F6 - If an _id must be unique in range of a cluster, user must able to guarantee that by setting unique_prefix to different values

F7 - User must receive and error when same ID is used second time, ID must bu unique in range of a table (collection)


Non-Functional Requirements
====

NF1 - The _id field must be sequential (always incrementing) for optimal InnoDB insertion performance (at least within a single server)

NF2 - Collation of the _id field must be BINARY for efficiency

NF3 - The sequential nature of _id values must be maintained across server restarts

NF4 - In a multi-primary replication environment, the generated _id values of a table should be unique across members to avoid primary key conflicts and minimize transaction certification 
failures.

NF5 - An Expect.Open()/Close() block of type EXPECT_DOCID_GENERATED should be accepted by the plugin with no side-effects to indicate to the client that the feature is supported.

Collection Table Format
=======================

The general structure of the collection table remains unchanged, except for the type of the generated _id column, which changes from VARCHAR(32) to VARBINARY(32).


_id Generation
==============

_id values are to be generated by default at the server side, using a custom DocID generator that fulfills the necessary requirements.

The DocID format is described below:

| unique_prefix | start_timestamp    |  serial                  |
|---------------|--------------------|--------------------------|
| 4 bytes       | 8 bytes            |  16 bytes                |

Where:

* serial is a per-instance auto-incremented integer serial number value, hex encoded
  * serial is in the range of 0 to 2**64-1
  * the initial value of serial is that given by the auto_increment_offset sysvar
  * the increment of the serial value is given by the auto_increment_increment sysvar
* start_timestamp is the timestamp of the startup time of the server instance, hex encoded
  * in the unlikely event that the value of serial overflows, the start_timestamp shall be incremented by 1 and the serial value then restarts at 0
* unique_prefix is a value assigned by InnoDB cluster to the instance, which is meant to make DocID unique across all replicasets from the same cluster.
   * unique_prefix has a range of 0 to 2**16-1
   * unique_prefix defaults to 0 if not set by InnoDB cluster or the user
   * the interface for assigning a value to unique_id is a sysvar called mysqlx_document_id_unique_prefix
   * hex encoded


This DocID format ensures that:

* The primary key value is monotonically incrementing for inserts originating at a single server instance, although the interval between id values will not be uniform within a table

* When multi-primary replication is in use, inserts to the same table from different members will not have conflicting primary key values; assuming auto_increment_* are configured properly.

* When sharding is introduced in InnoDB cluster, assuming unique_prefix is configured to a unique value per replicaset (or shard container), documents will be freely movable from a replicaset to another without conflicts.


_id Mechanics
==============

For the Mysqlx.Crud.Insert operation, documents without an _id are now allowed. If the document does not have an _id, the plugin generates one injects it to the document at insert time. Plugin can insert IDs only in case when document is send as X Protocol: string, octet, object. 

Because the structure of the table remains unchanged, no changes to behavior during queries are expected.

Plugin generates IDs in an sequence. When client application generates IDs on its own, then it must not use IDs that would make a collision with server sequence.


Protocol Changes
================

During the response sequence for the Mysqlx.Crud.Add operation, a SessionStateChanged notice, with param value GENERATED_DOCUMENT_ID is sent, with one value given (as a V_OCTETS) per document provided in the Add operation. The message format becomes the following:

    message SessionStateChanged {
      enum Parameter {
         CURRENT_SCHEMA = 1;
         ACCOUNT_EXPIRED = 2;
         GENERATED_INSERT_ID = 3;
         ROWS_AFFECTED = 4;
         ROWS_FOUND = 5;
         ROWS_MATCHED = 6;
         TRX_COMMITTED = 7;
         TRX_ROLLEDBACK = 9;
         PRODUCED_MESSAGE = 10;
         CLIENT_ID_ASSIGNED = 11;
         GENERATED_DOCUMENT_IDS = 12;  // <- new
         // .. more to be added
      }
      required Parameter param = 1;
      repeated Mysqlx.Datatypes.Scalar value = 2; <- optional changed to repeated
    }

An expectation with key EXPECT_DOCID_GENERATED = 3; is added. The expectation has no effect, other than not returning an error for unknown expectation.
Its purpose is to allow clients to know that DocIds generation is supported by the server they're connected to.


Configuration
=============

A new global and dynamic sysvar called mysqlx_document_id_unique_prefix is introduced. 
This sysvar has an integer type (32bit), with range of 0 to 65535. 
The default value is 0.

The sysvar must be persitable (that is, SET PERSIST mysqlx_document_id_unique_prefix must work, so the value is preserved across restarts).