<div id="readability-page-1" class="page"><article>
    <section id="post-body">
        <h2 id="final-project-wiki">Final project wiki</h2>

<h2 id="objective">Objective</h2>
<p>There are several performance bottlenecks in the lock manager of Innodb storage engine, which is the default in <a href="https://mariadb.org/">mariadb</a> 10.2. 
Innodb’s lock manager is the first bottleneck, aiming to improve the performance of mariadb by making this part scalable.</p>

<p><img src="https://mariadb.org/wp-content/uploads/2015/10/mariadb-usa-inc.png" alt="mariaDB"></p>

<p><strong>This project is divided into two major milestones.</strong></p>

<ul>
  <li><a href="Project4#milestone-1">Milestone 1</a>: Resolve performance bottlenecks of read-only transaction (due date: Dec 6, 2017)</li>
  <li><a href="Project4#milestone-2">Milestone 2</a>: Resolve performance bottlenecks of read/write transaction (due date: Dec 24, 2017)</li>
</ul>

<h2 id="analysis-of-lock-manager">Analysis of lock manager</h2>

<h2 id="milestone-1">Milestone 1</h2>

<p>Milestone 1 resolve performance bottlenecks of read-only transaction. Describe the process through how resolve the bottleneck below.</p>

<p><strong><em>Implementation of milestone 1 can not guarantee the correctness of the write operation. Therefore, when you run a test using <code>sysbench</code>, prepare process is safe to run before changes to this project.</em></strong></p>

<h2 id="the-reality-of-the-bottleneck">The reality of the bottleneck</h2>

<p>See <em>Image 2, Perf record of base model</em> and <em>Image 3, Perf record of enhanced model</em>  in bottom of page.</p>

<p>You can check rate of <code>PolicyMutex</code> close to 50%. However, it can not be seen in the improved version..</p>

<h2 id="process">Process</h2>

<p>The Process of read operation is as follow. <em>(The innobase on the left and right is my implementation.)</em></p>

<p><img src="https://github.com/MaybeS/ITE4065/blob/master/project4/images/design2.png?raw=true" alt="lock_mutex"></p>

<p><em>Figure 1. Innobase workload structure</em></p>

<h2 id="solution">Solution</h2>

<p>In order to solve the performance degradation caused by global lock, the lock for the record is managed as a lock-free linked list.</p>

<p><strong>My solution is separated by macros. See block of <code>#ifdef ITE4065</code> to <code>#endif</code>.</strong></p>

<h3 id="lock-insertion">Lock Insertion</h3>

<p>Requests coming in by read-only workload call <code>lock_rec_lock</code> via <code>lock_clust_rec_read_check_and_lock</code> function(see Figure 1). The original design is to hold the lock before <code>lock_rec_lock</code> and release it after acquire lock. However, to avoid that locking, change the root to point <code>lock_rec_lock</code> to the lock insert in the lock-free list.</p>

<p><em>Optional: implemented a <a href="https://gist.github.com/MaybeS/7835ac602ed5c7bbb5758f652b250982">generic lock-free linked list</a> for testing.</em></p>

<p>In the modified implementation, it is executed according to the following function call.</p>

<ul>
  <li><code>lock_clust_rec_read_check_and_lock</code></li>
  <li><code>lock_rec_lock</code></li>
  <li><code>lock_rec_lock_fast</code></li>
  <li><code>RecLock::create</code></li>
  <li><code>RecLock::lock_alloc</code>, <code>RecLock::lock_add</code></li>
  <li><code>lock_rec_insert_to_tail</code></li>
</ul>

<p>First of all, <code>RecLock::lock_alloc</code> uses <code>ut_malloc_nokey</code> to allocate and initialize memory for <code>lock_t*</code>.
In <code>RecLock::lock_add</code>, call <code>lock_rec_insert_to_tail</code> to append lock to lock-free list and add to trx_locks.
<code>lock_rec_insert_to_tail</code> is main implementation of latch-free design, using lock-free list to append new lock to tail of list. This process is handled using <code>__sync_lock_test_and_set</code> changes the hash of the previous node to point to current node. In case of tail of list is null, this means head is empty, so change head to point to current node. Order is guaranteed even if tail changes are requested by multiple threads because test_and_set(<code>__sync_lock_test_and_set</code>) is atomic operation and serialize contention.</p>

<h3 id="lock-deletion">Lock Deletion</h3>

<p>When a commit query comes in, the locks released by the transaction are released. If release lock immediately, Other threads that hold the lock can cause problems especially race. So, using <strong>logical deletion</strong> and <strong>physical deletion</strong> separately.</p>

<p><strong>logical deletion</strong> is changing state of lock to false which owner of the lock wants to release. And searching node in list of lock to detach logically deleted lock from list. If find the marked(logically deleted) node, using compare_and_swap(<code>__sync_bool_compare_and_swap</code>) to change node’s hash pointing to next. So, other thread can not read the marked node even if contention. If compare_and_swap is successed, change next node’s stamp to global timestamp. <em>global timestamp guarantee that bigger than running transactions stamp.</em></p>

<p>Since timestamp can be used in all transactions, it is managed by <code>trx_sys</code> and incremented by fetch_and_add(<code>__sync_fetch_and_add</code>) every time each commit.</p>

<h3 id="garbage-collection">Garbage Collection</h3>

<p>Even if performed logically deletion to lock, can’t guarantee all of other threads not holding the deleted lock. That is why using <strong>logical deletion</strong> and <strong>physical deletion</strong> separately. Logical deletion just marking the node to say “This node will be released!” and detach node from lock list, attach to garbage collection list. In attach to garbage collection list using compare_and_set prevent race condition.</p>

<p><strong>physical deletion</strong> is performed by the victim thread. Victim find timestamp which has minimum timestamp in running transactions and release lock iterating garbage collection list which timestamp is lower than minimum timestamp. Victim can wait with spinning if tail is changed while changing pointer of node. Especially tail is not pointing current node and next node’s hash is null it’s mean other thread change tail before changing pointer. <em>check gc_hash and <code>lock0lock.cc:3281</code> on <code>lock_t</code></em>.</p>

<p>This implementation is not very good for performance, As the number of nodes to be deleted increases, the victim thread waits for garbage collection to increase significantly. This can be solved by creating a special thread for garbage collection.  However, I have not implemented it because can not specifically determine the execution or end time of a specific thread in the current situation without affecting other tasks,.</p>

<h3 id="object-pool">Object Pool</h3>

<p>There is several implementation for object pool, but this is not fully implemented.
The implemented lock allocation will be used to steal the lock from  garbage collector that the transaction is ended when a new lock allocation is requested. The timestamp value confirms that the transaction has ended.</p>

<p>This object pool has not unrestricted size and it has an inefficient aspect in that <strong>deletion must occur before the allocation</strong>.</p>

<h2 id="milestone-2">Milestone 2</h2>

<p>Most processes that are compatible with Milestone 1’s operation will operate the same latch-free. The write operation is called through the <code>lock_clust_rec_modify_check_and_lock</code> function, and the <code>lock_rec_lock</code> is called again, so the read operation in Milestone 1 is designed as latch-free and the write operation is executed with the same latch-free logic.<em>(See Figure 1)</em></p>

<p><strong>I ran the sysbench test to write to it, but it was not a problem.</strong></p>

<p>But this is not clear and I am expecting that someday it’ll get an error. (but not now… and this makes me difficult to debug.)</p>

<h2 id="design">Design</h2>

<p><img src="https://github.com/MaybeS/ITE4065/blob/master/project4/images/design.png?raw=true" alt="design"></p>

<p><em>Figure 2. Whole design</em></p>

<h2 id="problem">Problem</h2>

<p>There are some problem in this design. In my design it takes a very long time because one victim performs all the physical deletions. 
Furthermore, the latch-free design is not using <code>innobase</code> allocation method, so it is not properly monitored. This can cause a big problem for the whole system. The most important issue is that if you try to force <code>mysqld</code> to shut down before all of the physical deletes are done, mysql will detect that the memory has not been emptied and may cause an error.</p>

<p>This problem can be solved by putting an exception in the assertion process of mysql before shutdown or using supported utility to allocation in latch-free design.</p>

<p><strong>So when you test this project yourself, you should give a lot of time after test and before exiting mysql.</strong></p>
<h2 id="results">Results</h2>

<p>Test on Linux System using sysbench</p>

<p>Ubuntu 14.04.5 LTS</p>

<ul>
  <li>Intel(R) Xeon(R) CPU E5-2650 v2 @ 2.60GHz (with 32vCPU)</li>
  <li>Intel(R) Xeon(R) CPU E5-2680 v2 @ 2.80GHz (with 32vCPU)</li>
  <li>Intel(R) Xeon(R) CPU E5-2666 v3 @ 2.60GHz (with 36 vCPU)</li>
</ul>

<p>Sysbench 1.0.10</p>

<p>you can check the original result log on <code>project4/results</code>.</p>

<p><img src="https://github.com/MaybeS/ITE4065/blob/master/project4/results/result.png?raw=true" alt="test result"></p>

<p><em>Image 1, Test result</em></p>

<p>And you can compare perf log between base and enhanced model.</p>

<p><img src="https://github.com/MaybeS/ITE4065/blob/master/project4/images/perf_base.png?raw=true" alt="perf_base"></p>

<p><em>Image 2, Perf record of base model</em></p>

<p><img src="https://github.com/MaybeS/ITE4065/blob/master/project4/images/perf_enhanced.png?raw=true" alt="perf_enhanced"></p>

<p><em>Image 3, Perf record of enhanced model</em></p>

    </section>
</article></div>

ITE4065

댓글