How does stateless token authentication work?

Question

Algorithms

Can someone explain to me in detail how stateless token authentication works in REST applications?
As I understand it now:
1. The client sends his login and password.
2. The server generates a token and gives it to the client.
3. The client stores the token and sends it along with every request.
4. The server validates the token and, if the validation is successful, gives access to protected resources.
Questions:
1. Do I need to store tokens on the server side? If so, where is the best place to store it? DB? Won't performance suffer with frequent requests from many users?
2. How is token validation carried out? If tokens are stored, just compare?
3. What to do if the user has changed the password? Issuing a new token and overwriting it in the database?
4. With each request, will we also have to read the token from the database? Or cache the token and control it (for example, when changing the password or other changes related to authorization)?
Please share your experience and knowledge with me, otherwise I have reached a dead end. Thank you in advance

Answer 1

It's very easy to think of tokens as a session, but a token is not a session, so don't get confused.
Tokens are used just to move away from the classic session/password scheme.
in order:
1) look, you have a service, for example, it consists of 10 servers that are responsible for different parts of the functionality, since the functionality is commercial, you need to check each request from the user whether he has the rights for this request.
you are forced to make a single validation server, and from each of your servers, for each request, request verification of the user and his rights on the validation server.
in such a situation, the validation server for your service becomes a bottleneck, and interferes with horizontal scalability.
and absolutely no difference you validate the user by password, ip, or token, session, the scheme is the same, the performance is also the same (which is why it makes no sense to change user verification instead of password to verification by ip, or token, or session, so it is more clear why using IP in this scheme is just a stupid idea).
therefore, there is a task to move away from this scheme, for the possibility of simple horizontal scaling, for this you take information about the user (for example, his id, rights, etc.) and encrypt this data, and transfer it to the user in the form of a token.
2) Each of your servers has a quick decryption algorithm that checks tokens on the fly, and from it receives the necessary information about the rights and user ID (validates the user, without a bottleneck), the tokens themselves are temporary, they also sew in information about the time of his actions, usually in the region of a couple of hours / days, after which you regenerate the token again (the key for regenerating and receiving a new token is also sewn into the token, ensuring the continuity of the token regeneration process).
3. What to do if the user has changed the password?
nothing - the token gives the user the right to log in, and it does not matter what the user's password is.

Answer 2

1. It is necessary, as a rule, to store something like user_id | token | additional fields.
2. As an option, you can save / check the ip address or some other parameters. If you look at the api of social networks - there the token is issued for a rather short time with the possibility of updating the time.
3. Delete all tokens associated with this user, issue a new one.
4. Read from the database, this operation will not create a heavy load.