 |
Faster cache invalidations
One of the issues with the current implementation of the MySQL query cache is that invalidation of cache entries takes a surprisingly long time which can cause the server to slow down noticeably during a few seconds. Such behaviour usually shows up in the log files and load graphs and can be the cause of some discomfort.
An investigation of the load distribution during a cache invalidation showed that my_hash_delete() was topping the list of time consumers. This raced a few questions on how the hash table was implemented. The hash distribution itself looked a bit unusual with a high concentration of access counts on element zero and a segmented into visual steps (although barely visible in this picture):
Second issue was that deleting elements from the hash involved linear searching in the hash table. Since we always performed a hash table look up before each delete, it should be possible to avoid this additional search by storing a reference from the hash entry to the hashed record or even make them part of the same structure.
As an experiment we replaced the hash table with a new one using a simple chained hashing model with the jenkins hash function. The distribution now felt more intuitive and it was easier to tackle the problem with removing individual hash entries. Doing the same with my_hash_* would involve patching code which a lot of other functionality was depending on.
Below are the two new hash functions. We built on the previous hash functions and the code is not exactly generic in nature. If it turns out to be a good change for the query cache maybe it can be generalized for other parts of the MySQL code.
Meta_record *qc_hash_insert(QC_Hash *info,Query_cache_block *record)
{
uchar *key= info->get_key((uchar *)record,&info->m_key_length, FALSE);
ulong idx= hash_func(key, info->m_key_length) & (info->m_hash_size - 1);
Hash_bucket *bucket= &info->m_hash_array[idx];
/*
Query_cache_block might be either a Query_cache_query
or a Query_cache table object. To find the right members
we use a function pointer stored in the cache meta data.
*/
Meta_record *mrec= info->get_meta_record(record);
if (!mrec)
return NULL;
mrec->init(record);
bucket->push_front(mrec);
return mrec;
}
Query_cache_block* qc_hash_search(QC_Hash *hash, uchar *key, size_t length)
{
/* Hash size assumed to be a power of 2 */
ulong idx= hash_func(key, length) & (hash->m_hash_size - 1);
Hash_bucket *bucket= &hash->m_hash_array[idx];
Hash_bucket::Iterator it(*bucket);
uint iteration_count= 0;
++hash->m_hash_search_ct;
while( Meta_record *mrec= it++ )
{
++iteration_count;
size_t rec_key_len;
uchar *rec_key= hash->get_key((uchar*)mrec->record,&rec_key_len, FALSE);
if (memcmp((const char*)rec_key,(const char*)key,length) == 0)
{
++mrec->access_count;
Meta_record *hottest_record= bucket->head();
if (mrec->access_count > hottest_record->access_count)
{
bucket->remove(mrec);
bucket->push_front(mrec);
}
hash->m_memcmp_ct+= iteration_count;
return mrec->record;
}
}
return NULL;
}
New hash distribution using Jenkins function:
It is not perfect, but certainly not bad either.
There is no new hash delete function. Instead there is a dettach() method on the Meta_record which unlinks the entry from the hash chain.
A test case gave me these number to compare with:
Using query_cache_size= 1073741824
1. Create test table and insert data.
Task completed in 115 seconds.
2. Starting monitor thread.
3. Initialize query cache.
4. Issue 1000000 SELECTs to populate query cache.
Task completed in 245 seconds.
Query cache status:
Qcache_free_blocks: 1
Qcache_free_memory: 49728032
Qcache_hits: 0
Qcache_inserts: 1000000
Qcache_lowmem_prunes: 0
Qcache_not_cached: 0
Qcache_queries_in_cache: 1000000
Qcache_total_blocks: 2000002
5. SELECT while query cache is invalidating.
5a. Flushing query cache by INSERT.
Press enter to continue.
Query cache invalidation + INSERT took 0.821174 seconds.
Original performance:
1. Create test table and insert data.
Task completed in 119 seconds.
2. Starting monitor thread.
3. Initialize query cache.
4. Issue 1000000 SELECTs to populate query cache.
Task completed in 217 seconds. <== Inserts are faster
Query cache status:
Qcache_free_blocks: 1
Qcache_free_memory: 41351648
Qcache_hits: 0
Qcache_inserts: 1000000
Qcache_lowmem_prunes: 0
Qcache_not_cached: 0
Qcache_queries_in_cache: 1000000
Qcache_total_blocks: 2000002
5. SELECT while query cache is invalidating.
5a. Flushing query cache by INSERT.
Press enter to continue.
Query cache invalidation + INSERT took 3.272828 seconds.<= invalidation is 3X slower
Ok, so now we have a degradation of cache insert performance instead. The reason seems to be the new hash search. However, from 217 to 245 seconds is about 13% increase which would correspond to a actual cost increase per query of 28*10^-6 seconds (and hash search is called twice for each query). I'm sure that if I look carefully on how I did the new hash search I might find where I lost these extra milliseconds.
On the other hand, executing random SELECT statements to retrieve cached data now seems to be a little bit more effective as well:
Original code:
Start 5 threads performing 500000 SELECTs each.
Thread 1 mean time: 0.001079 s.
Thread 2 mean time: 0.001075 s.
Thread 3 mean time: 0.001077 s.
Thread 4 mean time: 0.001076 s.
Thread 5 mean time: 0.001077 s.
Total mean time: 0.001077 s.
New code:
Start 5 threads performing 500000 SELECTs each.
Thread 1 mean time: 0.000743 s.
Thread 2 mean time: 0.000737 s.
Thread 3 mean time: 0.000733 s.
Thread 4 mean time: 0.000742 s.
Thread 5 mean time: 0.000740 s.
Total mean time: 0.000739 s.
Reducing the time of a cache invalidation is unfortunately only part of the issues with the query cache since it still scales badly over the growing numbers of CPU cores. There are a lot of suggestions on how that can be accomplished by I'm told the general business interest of evolving the query cache concept is pretty small.
Posts
