- developers - lists.mariadb.org

Re: [Maria-developers] e92037989f7: MDEV-21117: refine the server binlog-based recovery for semisync
by Sergei Golubchik 01 Jun '21

01 Jun '21

Hi, Andrei! On Jun 01, Andrei Elkin wrote: > >>>> > >>>> It's actually turns out not to be easy. A sequence of execution events > >>>> > >>>> E1.prepare(trx), E2.prepare(trx), E1.commit(trx), *crash* > >>>> > >>>> does not make E1 such as Innodb committed persistently in file. > >>>> At recovery in E1 trx may be found in prepared state, unless > >>>> before the crash I'd do something like Binlog CheckPoint (BCP) > >>>> notification request and wait of it. > >>> > The committed state is done asynchronously (by virtue of MDEV-232 that > implements a part of BCP). Oh. Indeed. Sorry, I've missed that. Still a prepare of another transaction can force this commit to disk, as far as I understand. So what about this: you stop the thread on a debug sync after the first commit then another connection starts committing in InnoDB, it stops on a debug sync after the prepare - before anything is written into binlog then you crash. looks like it'll create the case you need > >> No doubt it's technically possible to wait for the flushing and > >> crash, but still does not look easy. > >> Consider if we defer this sort of mtr test to MDEV-18959? > > Sujatha just contributed `74a13b4de2` with an mtr test that crashes > after the asynchronous fsync is done to the partially (2 engine case) > committed state. ... > Aslo now that `74a13b4de2` provides with a method to crash after the > "commmit" fsync we might also employ it for RQG. No, this is very different. This is a crash happening where Sujatha expects it to happen, there's no value in that now, it's needed for regression testing, to make sure the recovery won't be broken in the future. But it makes no sense to keep testing now how recovery works in case of a crash happening at exactly the place where Sujatha wanted it to happen and after she verified that crash at that exactly line does not break the recovery. The whole point of RQG tests is to try crashes where you did not expect them to happen. Adding DBUG_EXECUTE_IF() doesn't help this goal at all. Regards, Sergei VP of MariaDB Server Engineering and security(a)mariadb.org

1 0

Re: [Maria-developers] e92037989f7: MDEV-21117: refine the server binlog-based recovery for semisync
by Sergei Golubchik 31 May '21

31 May '21

Hi, Andrei! On May 27, Andrei Elkin wrote: >>> >>> I had a rather sobering followup, slipped communicating to you >>> though, sorry. >>> >>> It's actually turns out not to be easy. A sequence of execution events >>> >>> E1.prepare(trx), E2.prepare(trx), E1.commit(trx), *crash* >>> >>> does not make E1 such as Innodb committed persistently in file. At >>> recovery in E1 trx may be found in prepared state, unless before the >>> crash I'd do something like Binlog CheckPoint (BCP) notification request >>> and wait of it. >> >> I don't understand, what a binlog checkpoint has to do with it? > > So E1=Innodb. > In the above case in order to create partially committed trx > Innodb.commit(trx) > must be followed with flushing trx to disk, which is typically > asynchronous. > > I mentioned BCP 'cos it ensures a trx (actually the last in a binlog > file) is flushed. With --innodb-flush-log-at-trx-commit=1 it should be perfectly synnchronous, should it not? > >> In this just a selected engine would be requested, unlike in BCP > >> event case that is generated when both (in this case) have > >> persistently committed. (That is we even can't involve BCP event to > >> wait for, and the involvement would require some simulation as > >> well). > >> > >> So I propose to keep the current method leaving the "honest" crash > >> to RQG that Alice has been training the patch with. > > > > Alice was loading the server with transactions and doing `kill -9` > > at some point. Many interesting cases that we discuss (for example, > > the one above) happen in a very small time window, so I don't know > > whether random killing could provide an adequate test coverage. > > No doubt it's technically possible to wait for the flushing and crash, > but still does not look easy. > Consider if we defer this sort of mtr test to MDEV-18959? But we've spent numerous hours and emails discussing and you've spend countless days and weeks implementing various tricky corner cases are are and won't be ever tested. Here's an idea of how to test it. We're only interested in crashes during commit. So * when starting a commit - atomically increment some in_commit counter * on leaving the commit - decrement it * on signal (some unused one) - crash the server if in_commit > 0 * after the crash - get the stack traces from the core to see where in the commit did it crash. I've attached a small patch to illustrate this idea. Hopefully, it'll cover everything, but if not, then after analyzing stack traces we'll see where it did not crash, and move atomic increment/decrements to be around this area only. > >> >> diff --git a/sql/handler.h b/sql/handler.h > >> >> --- a/sql/handler.h > >> >> +++ b/sql/handler.h > >> >> @@ -873,6 +874,15 @@ typedef struct xid_t XID; > >> >> /* The 'buf' has to have space for at least SQL_XIDSIZE bytes. */ > >> >> uint get_sql_xid(XID *xid, char *buf); > >> >> > >> >> +/* struct for semisync slave binlog truncate recovery */ > >> >> +struct xid_recovery_member > >> >> +{ > >> >> + my_xid xid; > >> >> + uint in_engine_prepare; // number of engines that have xid prepared > >> >> + bool decided_to_commit; > >> >> + std::pair<uint, my_off_t> binlog_coord; // semisync recovery binlog offset > >> > > >> > wouldn't it be clearer to have a struct with named members? > >> > >> I am not sure if there's a need for naming. But we do need > >> comparison that std::pair provides for granted. > >> > >> I could consider (a) new typedef(s) to represent the binlog id and > >> offset in the file to make it more readable. > >> > >> You say? > >> > >> > in fact, I'm somewhat surprised there's no such struct for binlog coords > >> > already. > >> > >> I had started that back at HB implementation actually, but that struct > >> did not attact much of attention. > > > > > I'd still suggest a structure, like > > > > struct binlog_coords_t { > > uint binlog_num; > > my_off_t offset; > > }; > > Well, with this, like I said about std:pair, we'd also have to have > bool operator < (const binlog_coords_t) like bool operator <(const binlog_coords_t c) { return binlog_num < c.binlog_num || binlog_num == c.binlog_num && offset < c.offset; } > I seriously rate refuse to reuse as a deadly sin of programming. > (Unlike normal sins it may be soften by realization though :-)). > > Let's waive it away, right :-)? > > Hoping on that `72a59e4b068` already defined the following: ... > +/* > + Compound binlog-id and byte offset of transaction's first event > + in a sequence (e.g the recovery sequence) of binlog files. > + Binlog_offset(0,0) is the minimum value to mean > + the first byte of the first binlog file. > +*/ > +typedef std::pair<Binlog_file_id, my_off_t> Binlog_offset; This is better than writing std::pair<uint, my_off_t> everywhere. Not as clear as a binlog_coords_t from above, but _perhaps_ it'll do, let's see how it'll be used. Regards, Sergei VP of MariaDB Server Engineering and security(a)mariadb.org

1 0

[Maria-developers] Using JSON_TABLE to create JSON columns?
by Sergey Petrunia 31 May '21

31 May '21

Hi Alexey and everyone, I was looking at whether it's possible use JSON_TABLE to extract portions of JSON document. Apparently it is possible in MySQL with JSON datatype: Q1: select * from json_table('[{"color": "blue", "price": { "high": 10, "low": 5}}, {"color": "red", "price": { "high": 20, "low": 8}}]', '$[*]' columns(color varchar(100) path '$.color', price json path '$.price' ) ) as T; +-------+------------------------+ | color | price | +-------+------------------------+ | blue | {"low": 5, "high": 10} | | red | {"low": 8, "high": 20} | +-------+------------------------+ Note that if one uses any datatype other than JSON, they get NULLs: Q2: select * from json_table('[{"color": "blue", "price": { "high": 10, "low": 5}}, {"color": "red", "price": { "high": 20, "low": 8}}]', '$[*]' columns(color varchar(100) path '$.color', price text path '$.price' ) ) as T; +-------+-------+ | color | price | +-------+-------+ | blue | NULL | | red | NULL | +-------+-------+ Oracle-the-database doesn't yet(*) have a JSON datatype. So I can only run Q2 and then I get NULLs in the price column. MariaDB accepts JSON as datatype so query Q1 is accepted. However the logic in MDEV-17399 code doesn't have support for dumping a portion of JSON document, so one gets empty strings in the price column. Should we support Q1 with JSON output in the price column? If yes, should we do it within the scope of MDEV-17399 or create another task for this? (*) I see this: https://docs.oracle.com/en/database/oracle/oracle-database/20/newft/new-jso… BR Sergei -- Sergei Petrunia, Software Developer MariaDB Corporation | Skype: sergefp | Blog: http://s.petrunia.net/blog

3 2

[Maria-developers] GSoC Student Introduction for MDEV-24676
by Владислав Какурин 31 May '21

31 May '21

Hello, my name is Vladislav Kakurin, and this year I'm a GSOC 2021 participant for MariaDB. I will work on concurrent ring-buffer for improvement of IO_CACHE (https://jira.mariadb.org/browse/MDEV-24676) I hope I will succeed in this matter, as well as become a part of the MariaDB community

1 0

[Maria-developers] GSoC Student Introduction for MDEV-21130
by Michael Okoko 27 May '21

27 May '21

Hi, I'm Michael Okoko, a GSOC 2021 mentee for MariaDB and I'd be working on switching the on-disk storage format for MariaDB histograms to JSON ( https://jira.mariadb.org/browse/MDEV-21130) I'm looking forward to working with everyone in the community and contributing more to the MariaDB during and after GSOC.

1 0

Re: [Maria-developers] e92037989f7: MDEV-21117: refine the server binlog-based recovery for semisync
by Sergei Golubchik 26 May '21

26 May '21

Hi, Andrei! On Apr 27, Andrei Elkin wrote: > >> +--let $case = B: one engine has committed its transaction branch > >> +# Hold off after one engine has committed. > >> +--let $shutdown_timeout=0 > >> +--let $debug_sync_action = "commit_after_run_commit_ordered SIGNAL con1_ready WAIT_FOR signal_no_signal" > >> +# Both debug_sync and debug-dbug are required to make sure Engines remember the commit state > >> +# debug_sync alone will not help. > >> +--let $restart_parameters = --rpl-semi-sync-slave-enabled=1 --debug-dbug=d,binlog_truncate_partial_commit > > > > in the first review I wrote > > > > this seems to be a rather crude way of faking a partially committed > > transaction. better to crash after the first engine has committed, > > that'd be much more natural. > > > > and you replied > > > > This simulation aimed at (allows for) more complicated recovery time > > event sequences. > > In this case, indeed, crashing by demand is about of the same efforts. > > I can convert to that. > > > > [x] > > I had a rather sobering followup, slipped communicating to you though, sorry. > > It's actually turns out not to be easy. A sequence of execution events > > E1.prepare(trx), E2.prepare(trx), E1.commit(trx), *crash* > > does not make E1 such as Innodb committed persistently in file. At > recovery in E1 trx may be found in prepared state, unless before the > crash I'd do something like Binlog CheckPoint (BCP) notification request > and wait of it. I don't understand, what a binlog checkpoint has to do with it? > In this just a selected engine would be requested, unlike in BCP event > case that is generated when both (in this case) have persistently committed. > (That is we even can't involve BCP event to wait for, and the involvement > would require some simulation as well). > > So I propose to keep the current method leaving the "honest" crash to > RQG that Alice has been training the patch with. Alice was loading the server with transactions and doing `kill -9` at some point. Many interesting cases that we discuss (for example, the one above) happen in a very small time window, so I don't know whether random killing could provide an adequate test coverage. > >> diff --git a/mysql-test/suite/rpl/t/rpl_semi_sync_fail_over.test b/mysql-test/suite/rpl/t/rpl_semi_sync_fail_over.test > >> --- /dev/null > >> +++ b/mysql-test/suite/rpl/t/rpl_semi_sync_fail_over.test > >> @@ -0,0 +1,143 @@ > >> + > >> +--source include/have_innodb.inc > >> +--source include/have_debug_sync.inc > >> +--source include/have_binlog_format_row.inc > >> +--let $rpl_topology=1->2 > >> +--source include/rpl_init.inc > > > > why not to source master-slave.inc if you're using a standard master-slave > > topology anyway? > > Using numbers it's easier to manipulate with failover operatations. > Besides it's truly uncomfortable both read and write > when `master` would be serving the slave role as it happens in the test :-). I believe I already replied to that earlier. master-slave.inc creates server_1 and server_2 connections all right. > >> diff --git a/sql/handler.h b/sql/handler.h > >> --- a/sql/handler.h > >> +++ b/sql/handler.h > >> @@ -873,6 +874,15 @@ typedef struct xid_t XID; > >> /* The 'buf' has to have space for at least SQL_XIDSIZE bytes. */ > >> uint get_sql_xid(XID *xid, char *buf); > >> > >> +/* struct for semisync slave binlog truncate recovery */ > >> +struct xid_recovery_member > >> +{ > >> + my_xid xid; > >> + uint in_engine_prepare; // number of engines that have xid prepared > >> + bool decided_to_commit; > >> + std::pair<uint, my_off_t> binlog_coord; // semisync recovery binlog offset > > > > wouldn't it be clearer to have a struct with named members? > > I am not sure if there's a need for naming. But we do need > comparison that std::pair provides for granted. > > I could consider (a) new typedef(s) to represent the binlog id and > offset in the file to make it more readable. > > You say? > > > in fact, I'm somewhat surprised there's no such struct for binlog coords > > already. > > I had started that back at HB implementation actually, but that struct > did not attact much of attention. I'd still suggest a structure, like struct binlog_coords_t { uint binlog_num; my_off_t offset; }; > > > >> +}; > >> + > >> /* for recover() handlerton call */ > >> #define MIN_XID_LIST_SIZE 128 > >> #define MAX_XID_LIST_SIZE (1024*128) > >> @@ -4820,7 +4830,8 @@ int ha_commit_one_phase(THD *thd, bool all); > >> int ha_commit_trans(THD *thd, bool all); > >> int ha_rollback_trans(THD *thd, bool all); > >> int ha_prepare(THD *thd); > >> -int ha_recover(HASH *commit_list); > >> +int ha_recover(HASH *commit_list, MEM_ROOT *mem_root= NULL); > >> +uint ha_recover_complete(HASH *commit_list, std::pair<uint, my_off_t> *coord= NULL); > > > > is coord a truncation position? > > So NULL is for the normal recovery. > Non-NULL is an estimate of the 1st to rollback. > Trx with lesser offsets are to commit, greater of equal - to rollback. > > Why it's only an estimate is 'cos the function also handles > no-truncation cases, it then passes as `coord` the last committed > trx's coordinate. > The last committed can't be decided to rollback because of higher precedence of > > xid_recovery_member::decided_to_commit > > which is `true` under current circumstance, in > > +static bool xarecover_decide(xid_recovery_member* member, > + xid_t x, std::pair<uint, my_off_t> *coord_ptr) > +{ > + return > + member->decided_to_commit ? true : > + !coord_ptr ? false : > + (member->binlog_coord < *coord_ptr > > I did not reflect the subtlety of the above in function header comments. > To be done, if you're sastified here. yes, please, reflect it. thanks :) > >> diff --git a/sql/log_event.h b/sql/log_event.h > >> --- a/sql/log_event.h > >> +++ b/sql/log_event.h > >> @@ -482,6 +482,16 @@ class String; > >> */ > >> #define LOG_EVENT_IGNORABLE_F 0x80 > >> > >> +/** > >> + @def LOG_EVENT_ACCEPT_OWN_F > >> + > >> + Flag sets by the semisync slave for accepting > >> + the same server_id ("own") events which the slave must not have > >> + in its state. Typically such events were never committed by > >> + their originator (this server) and discared at its semisync-slave recovery. > >> +*/ > >> +#define LOG_EVENT_ACCEPT_OWN_F 0x4000 > > > > may be, add an assert on all received events that such a flag is not set? > > it can only be set on events in relay log. > > There's no place the flag gets logged. It'd be way too fool-proof in my > opinion :-)! > Or if you have a case I'll do. too fool-proof is when you do a=1; assert(a == 1); if you write a binlog event to disk, another thread reads it and sends over the network to another server, which also writes it to disk first, then another thread reads it again and executes - I don't think it's "too" to check that the event doesn't have this flag. Also, I personally value a lot a documentation role of asserts. Assert, like DBUG_ASSERT(ev->flags & LOG_EVENT_ACCEPT_OWN_F == 0); is basically saying /* LOG_EVENT_ACCEPT_OWN_F must be not set here */ but it's a self-fulfilling comment, it documents the code and at the same time guarantees that the documentation is up-to-date. > >> @@ -3357,6 +3367,12 @@ class Gtid_log_event: public Log_event > >> uint64 commit_id; > >> uint32 domain_id; > >> uchar flags2; > >> + uint flags_extra; // more flags area placed after the regular flags2's one > >> + /* > >> + Extra to a "base" engine recoverable engines participating > >> + in the transaction. Zero, when the base engine only is present. > > > > what's a "base engine"? > > The 1st ha_info one that is not binlog. why not to say "number of participating engines minus one" ? this won't puzzle anyone with a new concept of a "base engine" > > > >> + */ > >> + uint8 extra_engines; > >> > >> /* Flags2. */ > >> > >> diff --git a/sql/handler.cc b/sql/handler.cc > >> --- a/sql/handler.cc > >> +++ b/sql/handler.cc > >> @@ -1637,9 +1672,17 @@ commit_one_phase_2(THD *thd, bool all, THD_TRANS *trans, bool is_real_trans) > >> DEBUG_SYNC(thd, "commit_one_phase_2"); > >> if (ha_info) > >> { > >> + int err; > >> + > > >> + if (has_binlog_hton(ha_info) && > > > > can you replace has_binlog_hton() with, like, if trx cache is not empty or > > binlog enabled or something like that? > > I see you're driving at removing binlog ha_info from the list, are not > you? I'm not sure :) Yes, I'd like to get rid of binlog_hton, as we discussed. But here, perhaps, I just didn't like that you scan the list for something that most likely could be checked much easier. > I already made some experiments to have observed various complications > in the way of implementing an equivalent of > has_binlog_hton(). > The closest would be > non-empty cache. > > But `binlog_commit` may need invoking even in this case, as its branch > shows > > if (cache_mngr->trx_cache.empty()) > { > /* > we're here because cache_log was flushed in MYSQL_BIN_LOG::log_xid() > */ > cache_mngr->reset(false, true); > > > Overall, I'd stay with the current approach to defer its refinement to > time binlog_hton stops registering for transaction. > > Your comment? Okay. I just don't like scanning the list, aesthetically, when one can check a value in some fixed location or a variable. But it's not a performance concern, the list has usually only two elements and hardly ever can have more than three. So okay, let's stay with the current approach. > > @@ -1962,8 +2008,177 @@ struct xarecover_st > > >> sql_print_warning("%s transaction with xid %llu", > > > > may be not a sql_print_warning, but a sql_print_information? > > it's just an informational message > > [->] I presume, it means [x] > >> + member->decided_to_commit ? > >> + "Committed" : "Rolled back", (ulonglong) member->xid); > >> + } > >> + > >> + return false; > >> +} Regards, Sergei VP of MariaDB Server Engineering and security(a)mariadb.org

1 0

Re: [Maria-developers] 308c28e8a60: MDEV-15888 Implement FLUSH TABLES tbl_name [, tbl_name] ... WITH READ LOCK for views.
by Sergei Golubchik 23 May '21

23 May '21

Hi, Alexey! On Mar 21, Alexey Botchkov wrote: > revision-id: 308c28e8a60 (mariadb-10.5.2-393-g308c28e8a60) > parent(s): 786bc312b85 > author: Alexey Botchkov <holyfoot(a)mariadb.com> > committer: Alexey Botchkov <holyfoot(a)mariadb.com> > timestamp: 2021-02-09 00:59:55 +0400 > message: > > MDEV-15888 Implement FLUSH TABLES tbl_name [, tbl_name] ... WITH READ LOCK for views. > > Kind of 'naive' solution that surprisingly worked so trying to > understand why. > > diff --git a/mysql-test/main/flush-innodb.result b/mysql-test/main/flush-innodb.result > index 21e5bda7785..2c886e4f9fc 100644 > --- a/mysql-test/main/flush-innodb.result > +++ b/mysql-test/main/flush-innodb.result > @@ -60,7 +60,7 @@ DROP TABLE export; > CREATE VIEW v1 AS SELECT 1; > CREATE TEMPORARY TABLE t1 (a INT); > FLUSH TABLES v1 FOR EXPORT; > -ERROR HY000: 'test.v1' is not of type 'BASE TABLE' > +UNLOCK TABLES; good, but it only tests that there's no error. may be you need to add tests to verify that tables are actually locked? > FLUSH TABLES t1 FOR EXPORT; > ERROR 42S02: Table 'test.t1' doesn't exist > FLUSH TABLES non_existent FOR EXPORT; > diff --git a/sql/sql_reload.cc b/sql/sql_reload.cc > index 8f87d633d19..c146b7693c1 100644 > --- a/sql/sql_reload.cc > +++ b/sql/sql_reload.cc > @@ -543,6 +543,7 @@ bool flush_tables_with_read_lock(THD *thd, TABLE_LIST *all_tables) > > if (thd->lex->type & REFRESH_READ_LOCK) > { > +#ifdef MDEV15887 > /* > Acquire SNW locks on tables to be flushed. Don't acquire global > IX and database-scope IX locks on the tables as this will make > @@ -559,6 +560,7 @@ bool flush_tables_with_read_lock(THD *thd, TABLE_LIST *all_tables) > for (auto table_list= all_tables; table_list; > table_list= table_list->next_global) > table_list->mdl_request.ticket= NULL; > +#endif /*MDEV15887*/ what's that? btw, the number is MDEV15888 > } > > thd->variables.option_bits|= OPTION_TABLE_LOCK; Regards, Sergei VP of MariaDB Server Engineering and security(a)mariadb.org

2 1

Re: [Maria-developers] Request for a discusison: A fine-grained concurrent ring buffer mode for IO_CACHE
by Nikita Malyavin 22 May '21

22 May '21

Welcome to the thread, Andrei! For everybody: we just had a productive chat with Andrei, and I'd like to outline the results. Let's take a look at binlog_commit, or more exactly MYSQL_BIN_LOG::trx_group_commit_leader called from there (follow binlog_commit_flush_trx_cache -> THD::binlog_flush_pending_rows_event -> MYSQL_BIN_LOG::flush_and_set_pending_rows_event -> MYSQL_BIN_LOG::write_transaction_to_binlog call chain). The committing is currently strongly sequenced. The transactions are organized into groups, and when the latest transaction is acknowledged on the first commit phase, they all are being committed by leader in a chosen order. However, even here we can write the transactions in parallel, preserving the order. Andrei also claims, that the order can be potentially restored on the replication side. Anyway we technically can't send the transaction to the replication slave before the binlog flush&fsync, nevertheless the data will still be preserved in the volatile append cache. There was MDEV-20925 <https://jira.mariadb.org/browse/MDEV-20925> to store the transaction length in the event, but it unfortunately was rejected: > I will be closing this issue because we have COMMIT/ROLLBACK query log event > in the end of transaction , whose size is difficult to determine , > So current plan is to do MDEv-19687 without transaction length. The replication team decided to calculate the transaction sizes during receiving the data form the io, and then to store it in the hash, and no protocol modifications would be required then. I suggested to buffer the transaction separately, and then push it into the relay log in the data frame, storing the length. Then, we have MDEV-19687 <https://jira.mariadb.org/browse/MDEV-19687>, which was the supertask for MDEV-20925 <https://jira.mariadb.org/browse/MDEV-20925>. The aim is to parallelize the replication on the slave side. They are implementing their own parallel circular buffer with single-writer, multiple-reader use case: the parallel workers are going to pick out the transaction data, and resolve the commit order later. Sergei petrunya, you've been questioning: > I see SEQ_READ_APPEND is only used for Relay Log on the slave. Afaiu, the > relay > log has only only one producer, the network io thread. Andrei clarified, that there can actually be multiple sources. However they are just going to create a working queue for each source. =============================================================== To underline, the rationale is changed for this IO_CACHE improvement: * The replication relay log is not the use-case anymore, since a separate, much simplified circular buffer is going to be implemented (AFAIU, Sachin is in the middle of the progress of MDEV-19687 <https://jira.mariadb.org/browse/MDEV-19687>). * The binlog commit is instead a good case! Most likely I have forgotten about it, when I was writing the rationale. But anyway it wasn't clear for me, can the transactions be written in parallel there. On the reader side, the network replication sender should not block the committing process by reading from the binlog. Regards, Nikita

1 0

[Maria-developers] Request for a discusison: A fine-grained concurrent ring buffer mode for IO_CACHE
by Nikita Malyavin 19 May '21

19 May '21

Hello, dear MariaDB community! I am glad to present the design for IO_CACHE's SEQ_READ_APPEND mode concurrency improvements. Jira task is MDEV-24676. A student, Vladislav Kakurin, has applied to GSoC for this task, and has passed, so he will be engaged in implementing it this summer. The discussion is very important here, since I could make the mistakes, and Vladislav can miss them, but the success of the task completion may depend on it. We're hoping to succeed in implementing the multi-producer till GSoC end. So please don't hesitate to ask for clarifications. Note that reader/writer and producer/consumer pairs are used interchangeably in the text. The text is attached as PDF, but for the sake of convenient quoting it is additionally embodied in the email with shrinked markup and no illustrations. Sincerely, Nikita Malyavin Software Engineer of MariaDB ==================================================================== A fine-grained concurrent ring buffer mode for IO_CACHE 1. Rationale. --------------------------------------------------- Current implementation of IO_CACHE’s SEQ_READ_APPEND mode behaves coarsely grained on its write buffer: every read and every write is protected by append_buffer_lock. int _my_b_seq_read(IO_CACHE *info, ...) { lock_append_buffer(info); ... // read logic unlock_append_buffer(info); return Count ? 1 : 0; } int my_b_append(IO_CACHE *info, ...) { lock_append_buffer(info); ... // append logic unlock_append_buffer(info); return 0; } Despite the separate read buffer is read-only, and therefore is accessed wait-free, the write buffer can have a contention with medium-sized transactions. The design described hereafter is going to solve this issue, and an extension for a parallel multi-producer workflow is additionally provided. Furthermore, the API extension for multi-producer approach support is proposed, and the multi-consumerness is discussed. 2. The single-producer, single-consumer case. --------------------------------------------------- Idea. The memcpy operations of consumer and producer never overlap, therefore they can be freed of locks. Overflow and emptiness We cannot begin writing in the area still involved in reading. Therefore, reader should not update the pointers before it finishes reading. This means that we should lock in the beginning to atomically read the data, and in the end, to write the new reader data. The same for vice-versa, we cannot read from the area still involved into writing, therefore a read should finish with EMPTY error (currently _my_b_seq_read just returns 1) When we reach a “buffer is full” condition, we can flip the read and write (append) buffers, if we were reading from an append buffer. Otherwise, the append buffer is flushed. The algorithm. The following pseudocode will describe the single-consumer, single-producer approach. It is assumed that reading from the read buffer is handled in the usual way. io->total_size and io->read_buffer are considered to be accessed atomically. io_err_t read(IO_CACHE *io, uchar *buffer, size_t sz) { if (sz > io->total_size) return E_IO_EMPTY; uchar *read_buffer = io->read_buffer; if (io->read_pos points to read_buffer) sz_read = read_from_read_buffer(io, buffer, sz); buffer += sz_read; sz -= sz_read; io->total_size -= sz_read; if (sz == 0) return 0; // else copy from append buffer lock(io->append_buffer_lock); // copy the local variables uchar *read_pos = io->read_pos; uchar *read_buffer = io->read_buffer; uchar *append_start_pos = i->append_start_pos; uchar *append_size = io->append_size; uchar *append_pos = io->append_pos; // etc, if needed unlock(io->append_buffer_lock); read from append buffer; lock(io->append_buffer_lock); // update the variables io->append_size -= sz; io->append_start_pos += sz; if (i->append_start_pos >= io->append_buf + io->cache_size) io->append_start_pos -= io->cache_size; unlock(io->append_buffer_lock); io->total_size -= sz; } The first read()’s part tries to read from a read-only buffer. If it’s empty, it moves the effort to a volatile append buffer. All the metadata is copied in the first critical section, before the data copying, to the stack. It is updated back in the second critical section, after the data copying. io_err_t write(IO_CACHE *io, uchar *buffer, size_t sz) { lock(io->append_buffer_lock); if (append_buffer is full and io->total_size <= io->append_size) swap(io->append_buffer, io->read_buffer); else flush the append buffer if needed; write to disk directly, if the data is too large; uchar *write_pos = io->write_pos; unlock(io->append_buffer_lock); write to append buffer; lock(io->append_buffer_lock); io->write_pos = new_write_pos; unlock(io->append_buffer_lock); io->total_size += sz; } The important note here is that we access io->read_buffer in the reader’s thread without the lock (the accesses are marked bold). However this access happens only once in the beginning and is safe: Only writer changes read_buffer. The writer can change it only once during one read() if io->read_buffer is considered reads-only, then it will not flip again, and continue to be consistent, until io->total_size is changed: io->total_size -= sz_read; Then the lock happens. It should be fine to read from a flipped buffer on that stage. 3. Multi-producer concurrency --------------------------------------------------- Idea. Writes start from io->write_start, which is to update immediately. Reads are possible only until io->read_end, which is updated, as soon as writes are finished. Medium-grained approach io->write_start is updated immediately to allow parallel writes. However, we cannot update io->read_end immediately after this thread’s write ends, because earlier writes can still be in progress. We should wait for them i.e. we wait while (io->read_end != local_read_end) Algorithm (medium-grained). Medium-grained approach will modify write() function as follows (the changed lines and locks are bolded): io_err_t write(IO_CACHE *io, uchar *buffer, size_t sz) { lock(io->append_buffer_lock); if (buffer flip of flush is needed) wait until all the writes are finished; if (append_buffer is full && io->write_total_size <= io->append_size) swap(io->append_buffer, io->read_buffer); else flush the append buffer if needed; write to disk directly, if the data is too large; uchar *local_write_start = io->write_start; io->write_total_size += sz; io->write_start += sz; if (io->write_start > io->append_buffer + io->cache_size) io->write_start -= io->cache_size; unlock(io->append_buffer_lock); write to append buffer; lock(io->write_event_lock) while(local_write_start != io->read_end) cond_wait(io->write_event, io->write_event_lock); unlock(io->write_event_lock) lock(io->append_buffer_lock); io->read_end = new_read_end; unlock(io->append_buffer_lock); cond_signal(io->write_event); io->total_size += sz; } The read function should be modified mostly cosmetically. Fine graining. The writers are still waiting for each other’s finish. The approach described here defers waiting through helping pattern by introducing progress slots. Each time a writer begins progress it allocates a slot in the dedicated (fixed size) array. When the writer finishes its job, it checks whether it is the leftmost one (relative to its read_end value. If it is, it updates read_end for itself, and for all the consecutive writers already finished. The slot allocation will be controlled by a semaphore to prevent overflow. Therefore, only a fixed number of producers can work simultaneously. The slot array is made of elements of private cache_slot_t structure: struct cache_slot_t { bool vacant: 1; bool finished: 1; uint next: size_bits(uint) - 2; uint pos; } The slot is acquired whenever a write begins by searching an array cell with vacant=1. When it’s found, vacant = 0, finished = 0 is set. The last_slot variable holds the slot index for the latest write. slots[ last_slot].next is set to a new index, and last_slot itself is updated. The following example demonstrates how the slots work: +-------------------------------------------------------------+ | | write1 | write2 | write3 | | +-------------------------------------------------------------+ A B C D +-------------------------------------------------+ | vacant=0 | vacant=1 | vacant=0 | vacant=0 | | finished=0 | | finished=1 | finished=1 | | next=2 | | next=3 | next=? | | pos=A | | pos=B | pos=C | +-------------------------------------------------+ there were three writes currently running in parallel. write2 and write3 are finished, but write1 is still running. When it finishes, it will hop through slot.next while vacant==0 and finished==1 and pos != io->write_start. Therefore, read_end will be updated to C if no other write will begin in parallel. If another write begins in parallel before write1 finishes, it allocates slots[1] and sets pos=D. slots[3].next would be set to 1, and last_slot will be updated from 3 to 1. The slot run through expected complexity is O(1). The proof for acquisition is however not that obvious to prove the same, and no effort was spent for proving it (It’s only obvious that it’s O(slots)). 4. Arbitrary data sources support --------------------------------------------------- The widely spread use-case is pouring from another IO_CACHE source (like a statement or transaction cache). The operation may require several consecutive write() calls with an external lock: lock(write_lock); uchar buffer[SIZE]; while(cache_out is not empty) { read(ceche_out, buffer, SIZE); write(cache_in, buffer, SIZE); } unlock(write_lock); This case destroys all the parallel design described. However, let’s make api changes to allow blocks of predicted size be written in parallel: /** Allocates the slot of a requested size for a writer. Returns new slot id. */ slot_id_t append_allocate(IO_CAHCE*, size_t block_size); /** Frees the slot and propogates the data to be available for reading */ void append_commit(IO_CACHE*, slot_id_t); These two functions just decompose our write() function: append_allocate would include the first critical section and append_commit would include the second one. The use-case will be changed slightly: slot_id_t slot = append_allocate(cache_out, append_tell(cache_in)); uchar buffer[SIZE]; while(cache_out is not empty) { read(ceche_out, buffer, SIZE); write(cache_in, buffer, SIZE); } append_commit(cache_out, slot); 5. Multi-consumerness --------------------------------------------------- We currently have no cases with several readers working in parallel in SEQ_READ_APPEND mode. It is only used by the replication thread to read out the log, where it is delegated to a dedicated worker. The first problem is that parallel readout would require additional coordination -- the order of event application can be important. Another problem is that a variable-sized blocks require at least two consecutive reads if the structure is not known. If the length is stored, it can be read out with exactly two reads (first reads length, second reads the body). The slot allocation strategy can be applied, and api can be added similar to a new write api: /** lock the cache and allocate the read slot */ slot_id_t read_allocate_lock(IO_CACHE*); /** Allocate a read zone of the requested size and unlock the cache */ void read_allocate_unlock(IO_CACHE*, slot_id_t, size_t size); /** Finish reading; deallocate the read slot */ viod read_commit(IO_CACHE*, slot_id_t); Reading api needs one function more than writing api -- the allocation is split on two phases: locking phase (to compute the block length), and the actual requesting phase. This approach has several disadvantages: 1. The read buffer access is no longer lock-free 2. read_allocate_lock leaves the IO_CACHE in a locked state, which can be potentially misused. Additionally, two SX locks can be used (one for readers and one for writers) for extra parallelism.

2 2

[Maria-developers] Request for a discusison: A fine-grained concurrent ring buffer mode for IO_CACHE
by Nikita Malyavin 18 May '21

18 May '21

Hello, dear MariaDB community! I am glad to present the design for IO_CACHE's SEQ_READ_APPEND mode concurrency improvements. Jira task is MDEV-24676. A student, Vladislav Kakurin, has applied to GSoC for this task, and has passed, so he will be engaged in implementing it this summer. The discussion is very important here, since I could make the mistakes, and Vladislav can miss them, but the success of the task completion may depend on it. We're hoping to succeed in implementing the multi-producer till GSoC end. So please don't hesitate to ask for clarifications. Note that reader/writer and producer/consumer pairs are used interchangeably in the text. The text is attached as PDF, but for the sake of convenient quoting it is additionally embodied in the email with shrinked markup and no illustrations. Sincerely, Nikita Malyavin Software Engineer of MariaDB ==================================================================== A fine-grained concurrent ring buffer mode for IO_CACHE 1. Rationale. --------------------------------------------------- Current implementation of IO_CACHE’s SEQ_READ_APPEND mode behaves coarsely grained on its write buffer: every read and every write is protected by append_buffer_lock. int _my_b_seq_read(IO_CACHE *info, ...) { lock_append_buffer(info); ... // read logic unlock_append_buffer(info); return Count ? 1 : 0; } int my_b_append(IO_CACHE *info, ...) { lock_append_buffer(info); ... // append logic unlock_append_buffer(info); return 0; } Despite the separate read buffer is read-only, and therefore is accessed wait-free, the write buffer can have a contention with medium-sized transactions. The design described hereafter is going to solve this issue, and an extension for a parallel multi-producer workflow is additionally provided. Furthermore, the API extension for multi-producer approach support is proposed, and the multi-consumerness is discussed. 2. The single-producer, single-consumer case. --------------------------------------------------- Idea. The memcpy operations of consumer and producer never overlap, therefore they can be freed of locks. Overflow and emptiness We cannot begin writing in the area still involved in reading. Therefore, reader should not update the pointers before it finishes reading. This means that we should lock in the beginning to atomically read the data, and in the end, to write the new reader data. The same for vice-versa, we cannot read from the area still involved into writing, therefore a read should finish with EMPTY error (currently _my_b_seq_read just returns 1) When we reach a “buffer is full” condition, we can flip the read and write (append) buffers, if we were reading from an append buffer. Otherwise, the append buffer is flushed. The algorithm. The following pseudocode will describe the single-consumer, single-producer approach. It is assumed that reading from the read buffer is handled in the usual way. io->total_size and io->read_buffer are considered to be accessed atomically. io_err_t read(IO_CACHE *io, uchar *buffer, size_t sz) { if (sz > io->total_size) return E_IO_EMPTY; uchar *read_buffer = io->read_buffer; if (io->read_pos points to read_buffer) sz_read = read_from_read_buffer(io, buffer, sz); buffer += sz_read; sz -= sz_read; io->total_size -= sz_read; if (sz == 0) return 0; // else copy from append buffer lock(io->append_buffer_lock); // copy the local variables uchar *read_pos = io->read_pos; uchar *read_buffer = io->read_buffer; uchar *append_start_pos = i->append_start_pos; uchar *append_size = io->append_size; uchar *append_pos = io->append_pos; // etc, if needed unlock(io->append_buffer_lock); read from append buffer; lock(io->append_buffer_lock); // update the variables io->append_size -= sz; io->append_start_pos += sz; if (i->append_start_pos >= io->append_buf + io->cache_size) io->append_start_pos -= io->cache_size; unlock(io->append_buffer_lock); io->total_size -= sz; } The first read()’s part tries to read from a read-only buffer. If it’s empty, it moves the effort to a volatile append buffer. All the metadata is copied in the first critical section, before the data copying, to the stack. It is updated back in the second critical section, after the data copying. io_err_t write(IO_CACHE *io, uchar *buffer, size_t sz) { lock(io->append_buffer_lock); if (append_buffer is full and io->total_size <= io->append_size) swap(io->append_buffer, io->read_buffer); else flush the append buffer if needed; write to disk directly, if the data is too large; uchar *write_pos = io->write_pos; unlock(io->append_buffer_lock); write to append buffer; lock(io->append_buffer_lock); io->write_pos = new_write_pos; unlock(io->append_buffer_lock); io->total_size += sz; } The important note here is that we access io->read_buffer in the reader’s thread without the lock (the accesses are marked bold). However this access happens only once in the beginning and is safe: Only writer changes read_buffer. The writer can change it only once during one read() if io->read_buffer is considered reads-only, then it will not flip again, and continue to be consistent, until io->total_size is changed: io->total_size -= sz_read; Then the lock happens. It should be fine to read from a flipped buffer on that stage. 3. Multi-producer concurrency --------------------------------------------------- Idea. Writes start from io->write_start, which is to update immediately. Reads are possible only until io->read_end, which is updated, as soon as writes are finished. Medium-grained approach io->write_start is updated immediately to allow parallel writes. However, we cannot update io->read_end immediately after this thread’s write ends, because earlier writes can still be in progress. We should wait for them i.e. we wait while (io->read_end != local_read_end) Algorithm (medium-grained). Medium-grained approach will modify write() function as follows (the changed lines and locks are bolded): io_err_t write(IO_CACHE *io, uchar *buffer, size_t sz) { lock(io->append_buffer_lock); if (buffer flip of flush is needed) wait until all the writes are finished; if (append_buffer is full && io->write_total_size <= io->append_size) swap(io->append_buffer, io->read_buffer); else flush the append buffer if needed; write to disk directly, if the data is too large; uchar *local_write_start = io->write_start; io->write_total_size += sz; io->write_start += sz; if (io->write_start > io->append_buffer + io->cache_size) io->write_start -= io->cache_size; unlock(io->append_buffer_lock); write to append buffer; lock(io->write_event_lock) while(local_write_start != io->read_end) cond_wait(io->write_event, io->write_event_lock); unlock(io->write_event_lock) lock(io->append_buffer_lock); io->read_end = new_read_end; unlock(io->append_buffer_lock); cond_signal(io->write_event); io->total_size += sz; } The read function should be modified mostly cosmetically. Fine graining. The writers are still waiting for each other’s finish. The approach described here defers waiting through helping pattern by introducing progress slots. Each time a writer begins progress it allocates a slot in the dedicated (fixed size) array. When the writer finishes its job, it checks whether it is the leftmost one (relative to its read_end value. If it is, it updates read_end for itself, and for all the consecutive writers already finished. The slot allocation will be controlled by a semaphore to prevent overflow. Therefore, only a fixed number of producers can work simultaneously. The slot array is made of elements of private cache_slot_t structure: struct cache_slot_t { bool vacant: 1; bool finished: 1; uint next: size_bits(uint) - 2; uint pos; } The slot is acquired whenever a write begins by searching an array cell with vacant=1. When it’s found, vacant = 0, finished = 0 is set. The last_slot variable holds the slot index for the latest write. slots[ last_slot].next is set to a new index, and last_slot itself is updated. The following example demonstrates how the slots work: +-------------------------------------------------------------+ | | write1 | write2 | write3 | | +-------------------------------------------------------------+ A B C D +-------------------------------------------------+ | vacant=0 | vacant=1 | vacant=0 | vacant=0 | | finished=0 | | finished=1 | finished=1 | | next=2 | | next=3 | next=? | | pos=A | | pos=B | pos=C | +-------------------------------------------------+ there were three writes currently running in parallel. write2 and write3 are finished, but write1 is still running. When it finishes, it will hop through slot.next while vacant==0 and finished==1 and pos != io->write_start. Therefore, read_end will be updated to C if no other write will begin in parallel. If another write begins in parallel before write1 finishes, it allocates slots[1] and sets pos=D. slots[3].next would be set to 1, and last_slot will be updated from 3 to 1. The slot run through expected complexity is O(1). The proof for acquisition is however not that obvious to prove the same, and no effort was spent for proving it (It’s only obvious that it’s O(slots)). 4. Arbitrary data sources support --------------------------------------------------- The widely spread use-case is pouring from another IO_CACHE source (like a statement or transaction cache). The operation may require several consecutive write() calls with an external lock: lock(write_lock); uchar buffer[SIZE]; while(cache_out is not empty) { read(ceche_out, buffer, SIZE); write(cache_in, buffer, SIZE); } unlock(write_lock); This case destroys all the parallel design described. However, let’s make api changes to allow blocks of predicted size be written in parallel: /** Allocates the slot of a requested size for a writer. Returns new slot id. */ slot_id_t append_allocate(IO_CAHCE*, size_t block_size); /** Frees the slot and propogates the data to be available for reading */ void append_commit(IO_CACHE*, slot_id_t); These two functions just decompose our write() function: append_allocate would include the first critical section and append_commit would include the second one. The use-case will be changed slightly: slot_id_t slot = append_allocate(cache_out, append_tell(cache_in)); uchar buffer[SIZE]; while(cache_out is not empty) { read(ceche_out, buffer, SIZE); write(cache_in, buffer, SIZE); } append_commit(cache_out, slot); 5. Multi-consumerness --------------------------------------------------- We currently have no cases with several readers working in parallel in SEQ_READ_APPEND mode. It is only used by the replication thread to read out the log, where it is delegated to a dedicated worker. The first problem is that parallel readout would require additional coordination -- the order of event application can be important. Another problem is that a variable-sized blocks require at least two consecutive reads if the structure is not known. If the length is stored, it can be read out with exactly two reads (first reads length, second reads the body). The slot allocation strategy can be applied, and api can be added similar to a new write api: /** lock the cache and allocate the read slot */ slot_id_t read_allocate_lock(IO_CACHE*); /** Allocate a read zone of the requested size and unlock the cache */ void read_allocate_unlock(IO_CACHE*, slot_id_t, size_t size); /** Finish reading; deallocate the read slot */ viod read_commit(IO_CACHE*, slot_id_t); Reading api needs one function more than writing api -- the allocation is split on two phases: locking phase (to compute the block length), and the actual requesting phase. This approach has several disadvantages: 1. The read buffer access is no longer lock-free 2. read_allocate_lock leaves the IO_CACHE in a locked state, which can be potentially misused. Additionally, two SX locks can be used (one for readers and one for writers) for extra parallelism.

1 0