If I read the spec correctly, UrlShortener will not produce deterministic short urls. As such, they should be lazy created as needed afaik.
Overhead should be minimal, but one possible way (depending on the implementation) may be to add a basic ping limiter so that a single user cannot submit 100s of urls at the same time. Attackers may do that in attempt to poison the database and take all smaller keys, or in an effort to arrive at a specific short id (if it's based on auto-increment internally, to try and spell some word).