commit dd45b8a9df356d7675c0de7e30aa9403c967461d
Author: GAO Xiaoxin <dennis.gao@greatopensource.com>
Date:   Wed May 25 17:34:22 2022 +0800

    Bug #106918 master and slave may get serious in-consistence after add auto-increment as pk
    
    In mysql8.0 Hash_slave_rows use std::unordered_multimap to store the binlog_event_row hash values.
    
    ----------------------------------
    Bug reason
    ----------------------------------
    
    For some duplicate rows, such as (1,1),(1,1),(1,1), which have the same hash key, will be added into the some bucket in inverse order.
    
    For example, there are three rows update events:
    row1: before_image:(1,1), after_image:(1,5)
    row2: before_image:(1,1), after_image:(1,6)
    row3: before_image:(1,1), after_image:(1,7)
    
    The above three rows in the hash bucket are in inverse order:
    
    row3->row2->row1
    
    When we use m_hash.find(key), we will get the iterator poin to row3 as the start point.
    
    In Rows_log_event::do_scan_and_update, the innodb row (1,1) will firt match row3 by using m_hash.get; then row2 and finial row1.
    
    So in the slave, the update row execute sequence is inverse comparing to the master.
    
    After the replication, the slave will get the following select output:
    (1,7)
    (1,6)
    (1,5)
    
    While the master's select output is:
    (1,5)
    (1,6)
    (1,7)
    
    The row sequence is different between master and slave.
    If the master exeucte "alter table t add column id int auto_increment primary key;" in this case, the data will be in-consistence between master and slave.
    
    ------------------------------------
    How to fix
    ------------------------------------
    
    Use std::multimap to store the binlog_event_row hash values, rather than std::unordered_multimap.
    std::multimap will store the data in the same sequence as they insert sequence.

diff --git a/include/map_helpers.h b/include/map_helpers.h
index 8d5629a..a4fc2ec 100644
--- a/include/map_helpers.h
+++ b/include/map_helpers.h
@@ -30,6 +30,7 @@
 #include <unordered_map>
 #include <unordered_set>
 #include <utility>
+#include <functional>
 
 #include "m_ctype.h"
 #include "my_inttypes.h"
@@ -199,6 +200,24 @@ class malloc_unordered_multimap
             Malloc_allocator<>(psi_key)) {}
 };
 
+template <class Key, class Value, class Compare = std::less<Key>>
+class malloc_multimap
+    : public std::multimap<
+          Key, Value, Compare,
+          Malloc_allocator<std::pair<const Key, Value>>> {
+ public:
+  /*
+    In theory, we should be allowed to send in the allocator only, but GCC 4.8
+    is missing several multimap constructors, so let's give in
+    everything.
+  */
+  malloc_multimap(PSI_memory_key psi_key)
+      : std::multimap<Key, Value, Compare,
+                                Malloc_allocator<std::pair<const Key, Value>>>(
+            Compare(), Malloc_allocator<>(psi_key)) {}
+};
+
+
 /**
   std::unordered_map, but with my_malloc and collation-aware comparison.
 */
diff --git a/sql/rpl_utility.h b/sql/rpl_utility.h
index ea1daf6..a01bf6b 100644
--- a/sql/rpl_utility.h
+++ b/sql/rpl_utility.h
@@ -31,6 +31,7 @@
 #include <algorithm>
 #include <string>
 #include <unordered_map>
+#include <map>
 
 #include "field_types.h"  // enum_field_types
 #include "my_dbug.h"
@@ -90,7 +91,7 @@ struct HASH_ROW_PREAMBLE {
     The search state used to iterate over multiple entries for a
     given key.
    */
-  malloc_unordered_multimap<
+  malloc_multimap<
       uint, std::unique_ptr<HASH_ROW_ENTRY, hash_slave_rows_free_entry>>::
       const_iterator search_state;
 
@@ -216,7 +217,7 @@ class Hash_slave_rows {
   /**
      The hashtable itself.
    */
-  malloc_unordered_multimap<
+  malloc_multimap<
       uint, std::unique_ptr<HASH_ROW_ENTRY, hash_slave_rows_free_entry>>
       m_hash{key_memory_HASH_ROW_ENTRY};