Do I send a command to move right every frame?
Sure. Why not? As long as the player is moving right, of course. If that's spamming the server too much, you could of course just send the command to move right and the command to stop moving right, but you're risking some troubling behavior if you miss the "stop moving" command. You could compromise between those two approaches. Send the command to move right periodically and send the stop command. Have the server keep moving right as long as it's received the command recently and stop when asked to stop OR when it hasn't received a keep moving right in a while.
How does the server correctly calculate this movement as it does not know the deltaTime of the client?
The server shouldn't care about the internal delta framerate of the client. It SHOULD care about the time that a command is sent to it. If your game is sufficiently deterministic to allow for client-side prediction, then the relative frame-rates shouldn't matter. To be deterministic, for example, the server would need to know something like, what is the speed of this character. Here's what I mean:
The idea is the server has its own delta time. Here's an example, using minutes instead of milliseconds to make the concept more clear. Say I'm supposed to go 60 miles and hour. That's the same thing as 1 mile per minute. Lets say we were moving the car based on an elapsed time that varies. So we might get something like the following:
10 minutes. (Multiply 10 (minutes) by 1 (mile) means we move the car 10).
8 minutes. (Another 8 minutes have passed, so we move the car 8).
12 minutes. (12 minutes * 1 mile, add another 12).
So our total is 30 miles. Now on the server side, it might not be polling at the same times, but it's going to move the car the same amount if it's always multiplying the speed by the delta. So for example, say the server only polled every 15 minutes:
- 15 minutes (Multiply 15 (minutes) by 1 (mile) and we're at 15.)
- 15 minutes (do it again, we're at 30.)
Both the server and the client know the car has moved 30 miles, although they don't know the various delta frame rate of the other (and they don't need to know). Hope this example made it make sense.
Implementation Strategy
Based on the comments below, I'd like to suggest the following strategy to implement client-side prediction: Start by not having any. Let the server handle where the location of the player. Send your commands, right left, etc., have the server calculate the position and then have the server reply back with the player's new location. On the client side, use the player location to set the location of the player. This will work, but it'll create some lag that you won't like. Now, attempt to do some client-side prediction. Update the client position with where you think the player should be before it hears back from the server. When it hears back from the server the actual location, update the player to actually be in that location (i.e., let the server "win" when they disagree). Now you can work toward letting your prediction code do a better of predicting correctly so that the end product results in minimum correction "jumping".
In short, right now some of your questions suggest you're struggling a bit with the basic set-up of having the server calculate player location. So break this down into steps, get that working first, and then work on the prediction code happening.