Mysql – Load balancing – Multiple servers, different locations

Jeff, I disagree, load balancing does not imply redundancy, it's quite the opposite in fact. The more servers you have, the more likely you'll have a failure at a given instant. That's why redundancy IS mandatory when doing load balancing, but unfortunately there are a lot of solutions which only provide load balancing without performing any health check, resulting in a less reliable service.

DNS roundrobin is excellent to increase capacity, by distributing the load across multiple points (potentially geographically distributed). But it does not provide fail-over. You must first describe what type of failure you are trying to cover. A server failure must be covered locally using a standard IP address takeover mechanism (VRRP, CARP, ...). A switch failure is covered by resilient links on the server to two switches. A WAN link failure can be covered by a multi-link setup between you and your provider, using either a routing protocol or a layer2 solution (eg: multi-link PPP). A site failure should be covered by BGP : your IP addresses are replicated over multiple sites and you announce them to the net only where they are available.

From your question, it seems that you only need to provide a server fail-over solution, which is the easiest solution since it does not involve any hardware nor contract with any ISP. You just have to setup the appropriate software on your server for that, and it's by far the cheapest and most reliable solution.

You asked "what if an haproxy machine fails ?". It's the same. All people I know who use haproxy for load balancing and high availability have two machines and run either ucarp, keepalived or heartbeat on them to ensure that one of them is always available.

Hoping this helps!

Assuming that all your back-end machines are "active" and able to respond to requests all you really need is a load balancer front-end.

A good load balancer will be able to keep track of the number of connections going to each host and dynamically distribute new connections to avoid swamping one of the back-end systems (by "good" I mean "expensive", like Cisco Content Switches/Content Switch Service Modules). Price goes hand in hand with features here: Content switches are pretty high up on the solutions tier.

I've got no experience with HAProxy, but it sounds like it can do least-connection load balancing like content switches, so this would probably be a good choice (and at a much more attractive price point). I'm not sure if HAProxy can do source-tracking (send all connections from the same IP to the same back-end) though.

A few steps down down the pf firewall (or the pfsense customized distribution) can do load balancing (random or round-robin, I don't believe they can do "weighted least connections" as a balancing option like the content switches). Source tracking is implemented in pf, though you may have to play with how long that information is retained to avoid problems with connections getting moved from one server to another.
If you're already using pf/pfsense as your firewall this is a no-cost option: We use this in my current deployment with good results, but our connections aren't as long-lived as yours.