Hi Manuel
I agree with David on going for AWS from day 1 - I've been using AWS the last 8 months designing a very large scale system that can auto scale using ELB, Route53, EC2 instance, doing load testing, using metrics from AWS and so much more options, ranging from Redis, to Posgtres, Mongo, to Docker, S3 ...te list of options you get using AWS on a technology stack is scary! Not to mention options like DNS routing for lowest latency, DR-sites, power outages, replication, backups, ext - and you can start small using a t1.micro EC2 linux ubuntu instance for running mosquitto on it and also run HAProxy ...one key thing if you want to use AWS's ELB in future or just try out - remeber that your mqtt ping time must be 60sec or below, or the AWS elb will drop your packets....
If you go to AWS, you get Redis and memcache aslo @price, but for basic learning you can run Redis on EC2 servers
So well worth checking out what the ROI will be using an AWS server
You can also scale up from smaller EC2 instances - so start small and move up to bigger servers - only "learning" part here will be to find the best match instance for you solution - things like advance networking vs memory, vs cpu all play a role later in finding the correct server
Then you have to think about tweaking kernels levels - your stock std linux kernel will not handle much concurrent connections without some lower level changes...things like file handles, tcp-frame buffer ..
^_^ IN SHORT - try AWS as well