Load Balancing multiple databases in a multi-tenant setup We have a multi-tenant setup where each client of ours runs a DB that is identical to every other client. We were using Mysql sofar and with CentOS 7.x ,switched to MariaDB.

If we want to distribute the load so that requests for Databases 1-500 go to Node-A, request for Databases 501-1000 go to Node-B, would that be possible through some out of the box solution like haproxy? I looked into their documentation but the "balance" options seem to be about distributing the load based on pre-defined headers/values rather than my use-case above. Would it be possible to add a custom "balance" algorithm that will send the requests to the corresponding nodes?  

The other approach I was considering was to use a local key-value store that contains the information about which clients are in which Node and switching to those based on the request. I also want to have master-slave replication for these, but have already handled that through a proxy in my application.

Our application runs on PHP(Symfony Framework) with Mysql, if that matters.

How would you design a system that will have few thousand databases and be able to spread the load?
You can use Galera for multi-master replication. If you could move individual clients to specific nodes you will not run into locking issues.  It also has automatic recover of failed nodes.
http://galeracluster.com/