How Linux servers update their kernel without rebooting

Yes, they do a "reboot", but could do a kexec_load system call to preload the new kernel.

There is the possibility of patching the running kernel as well, redhat kpatch for example. All the things which do this that I am aware of can not change the data structures.

Of course lisp machines used to be able to patch their running kernels in the last century.

A kernel change should get a reboot. You can install the kernel, and in some cases you can insert and remove modules of different kernels, but I would not advise it.

A server could be rebooted and service would be unaffected if the server is part of a cluster. You can create firewall/router clusters too, such that there is no single point of failure (SPOF). To do this you use what is called a Virtual IP (VIP) that is shared across more than one system.

If you want to experiment with this idea you can use QEMU or VirtualBox and others to create virtual networks.