We started openredis in 2011, and we reached the 1k customers mark a year later. It's a Redis hosting service for EC2, also available as a Heroku add-on. Aside from the fact that the Heroku add-ons program could be considered some sort of marketing, we've never paid a single ad. For us, the key to getting customers was word of mouth. In 2014, at the three year anniversary, I wrote a blog post about how we got started: http://soveran.com/turning-three.html