Good news and bad news.
The good news, the server can be setup in moments to do this properly, and is seamless for the user experience. In the long term Google will update its indexes to all point to the new URLs. However, there have been some issues in the short and media term.
Google does not update its indexes as fast as it potentially could. There are reasons for this behavior, in the old days people could redirect pages and get them updated rapidly and could, "black hats did," redirect pages to manipulate search results. So search engines responded by slowing down the process of updating their index on a redirect.
This is not a complete list built over time, maybe other scenarios can be added in additional answers.
- If the bot reads the old content first then reads the new content and indexes it as the canonical everything goes well and to plan.
- If the bot reads the new page and sees it as duplicate content [the bot/algo not a person or penalty], the process in the short term for that URL does not go to plan. It will resolve itself in the long term but may effect SEO in the tween period.
- As updates and links to the new location [in the tween period while old url is the canonical], are not as effective, as it is of little importance not being the canonical, hence we are not getting fresh content benefits ... I consider this a negative SEO effect. ... but may help, [attract the interest of the bot], and speed up the process of Google in identifying the new "important" url.
- In your case if the users are posting products, google may not be as aggressive in adding this content if these postings are not from what google considers the canonical. However if the material is not changing this is not relevant.
The old url is still indexed and the new location receives all traffic but.
Links from the new page seen as duplicate are not going to be as effective as if they were links from the original content.
It may take time ... Google focuses its bot on content which it has an interest in; IE it may want content which is newly trending ... and material from the back of the library which may be of extreme value, collect dust.
We are at the mercy of the bot for how it finds content, and when it finds content, and when it updates its index. We can offer the bot sitemaps and Schema content, but ultimately we are powerless.
What Google could do
If Google would be kind enough to add to webmaster tools the ability to tell them the correct canonical for the original content and used it. Our the quality of our lives would improve. And in your case if they allowed a wildcard to identify the canonical it would be even better.
IE old url: https://www.example.com/*/user -> https://www.example.com/new/user in webmaster tools. Please Google, please.
Getting canonical ASAP solves the problem, if fresh content is added to the new URL. Submit a request to the old URL main page (to pick up the redirect), new URL page (to index the new URL and discover the changes) and the new content.
Five million URLs would also be a good test case to determine more exactly the process of getting a new canonical.