I'm curious about the technology behind exchanges.
How do they instantly generate/allocate new receiving addresses?
There is nothing special about it, its similiar database like everywhere else (banks, gambling sites etc).
Handling bitcoin addresses, here is more to say, every exchange or bitcoin related website need to address this issue by itself.
Most use cold wallet address to amass client funds and hot wallet for current operations. All clients funds going to hot wallet up to certain point for example 500 BTC then rest is located in more secure cold wallet address.