MySQL consuming memory, seeking advice on how to configure it

Memory can help you by caching and thus reducing I/O.

However, that won't reduce CPU usage which is your problem. This is an unusual bottleneck, as CPUs are insanely fast for most database work and I/O tends to be the bottleneck.

In your case, it is even more inusual, because you have 16-cores and VPSs tend not to have great I/O performance. First of all, make sure that you are CPU bound. vmstat should help here.If you have high numbers on the wa column, you are probably I/O bound; high numbers on the us column could indicate that you are really CPU bound.

If you are CPU bound, analyze what queries are you executing and why they take long to complete. You are either executing a lot of queries/s or they include complex calculations (i.e. aggregates, functions, etc.). The solution for the former is usually caching on the frontend, which means executing less queries. The latter is solved by simplifying your queries (if possible- you might have queries which are needlessly complex) and calculating stuff once and reusing it (say you have lots of aggregate queries; create a table with the aggregation results and query that instead of running aggregates continuously). The most efficient way to research about this is by logging which queries you are running and analyzing the log- tools exist which do this neatly.

If you are I/O bound, then you can tune memory usage, although the OS cache is often working correctly. Take a look at free:

$ free
             total       used       free     shared    buffers     cached
Mem:       6122892    5903564     219328          0     257020    3119240
-/+ buffers/cache:    2527304    3595588
Swap:     11956220      65980   11890240

The first line of numbers accounts for memory usage including OS caches, the second doesn't; by comparing both you can see how OS caching is working. Also, vmstat will already tell you how much I/O you are performing (bi, bo columns). Often, the key to solving I/O problems is query tuning and indexing; indexing prevents full table scans (i.e. reading the entire table to get a limited set of data, which causes excessive and unnecessary I/O). Again, logging queries is most effective here- running EXPLAIN on the queries will tell you which operations the database is performing to execute the query, which often leads you to understanding inefficiencies in the query (and altering the query to solve them) or finding out about needed indexes.

The formulas that tuning scripts like mysqltuner use to estimate potential memory usage are bunk. These posts explain why and give some examples of things that could be causing the memory usage pattern you're seeing:

How much memory can MySQL use in the worst case?

MySQL Server Memory Usage

This post talks about isolating the problem by running tests:

Troubleshooting MySQL Memory Usage

The simplest explanation is that there is a query with large memory overhead, which should be identifiable by running the query in isolation and observing its impact on memory usage.

As the post says, memory usage issues are one of the more annoying problems to have in MySQL, and the lack of instrumentation features that other RDBMS have really shows here and makes this type of problem difficult to diagnose.