Where to rate limit?

I want to rate limit my API to prevent from abuse. My setup for my API is currently:

1. Cloudflare with orange cloud on (to protect from DDoS), which forwards to my nginx reverse proxy
2. Nginx reverse proxy which forwards requests to the app server and caches GET requests. It does not block any requests.
3. The app server itself, which blocks HTTP requests from all IPs but the nginx reverse proxy.

Setting up rate limiting for cloudflare and nginx should be relatively easier, since all they need are some changes to the control panel. For my app server, however, I will need to use aerospike to track sessions (which would make my API not truly stateless) for a minute to block people who make requests too frequently and send back a 429.

However, I would let some users with the right tokens (pricing plans) bypass rate limiting, so I wouldn't know how to make it work on cloudflare.

So, my question is where should I setup rate limiting to make it most effective (non-circumventable), but fastest, and even if I should use cloudflare at all.