How to migrate from MySQL to MariaDB or Percona with minimum downtime?
In order to perform an upgrade with (almost) no downtime, you need to add some extra infrastructure for high availability. The most common way to perform that is with the help of MySQL built-in replication:


Setup a slave with a clone of the data of the original master. It is technically possible to setup a master-slave replication within the same node by creating a new separate instance on the same hardware. However, I would recommend -in a general case- to set it up on a separate node if possible. This is specially true if the server is very busy.
Put your slave down and perform the upgrade process offline, without stress (the master, your original mysql, is serving your application). Then you upgrade that to MySQL/Percona/MariaDB.
Restart your slave an prepare for switchover from the master to the slave (there are several ways to do that, but if it is not a stable thing, it can be done in places like the connector/driver configuration of your application). There are many things to do on this phase, like waiting for slave lag to become 0, validation testing and warming the slave's buffer pool, etc.
Set your master as read-only and wait for all changes to be applied to the slave server (if you have done enough preparations, this should be almost immediately). This is the only part that produces non-availability on the server. This is because the slave is not 100% synchronous with the master. If 1 second of unavailability is too much for you, there are alternatives for synchronous replication (like semi-sync and galera).
Set your slave as the "active server". Congratulations, you are now on production with 5.6
If you want your original slave to be the final production server, you can repeat steps 2-5 for the old master (which should be the new slave now)


There are many things to have into account here: an upgrade from 5.1 to 5.6 (even if you follow upstream MySQL, and with more reason if you change provider) does not guarantee that it will go smoothly. You will suffer configuration changes, query optimiser changes, SQL syntax changes. You may want to do both both load and validation tests. There are many tools for load testing from your own logs (mysqlslap, percona playback), but I would recommend at least pt-upgrade for compatibility testing. You may also want to watch closely the "What's new" MySQL documents to take advantage of the new features and its equivalent for MariaDB/Percona.

Even if you decide to perform the upgrade not using replication (doing a cold restart), it is still a very useful tool to test the new server version beforehand.

Regarding the upgrade itself, 5.1 -> 5.6 itself can be done in binary format (I would recommend transitioning through 5.5 for easier fix of errors), but if you do not have a lot of data I would recommend you alternatively thinking if a logical export/import is feasible to avoid later rebuilds. This is very dependent on your actual setup.

Final words: remember to perform a backup beforehand and execute mysql_upgrade afterwards.

Check a recent article of how GitHub did a datacenter migration doing a similar process.