Buenas,
Sinceramente, 3500000 clientes es una cifra muy importante como para tratar el tema en un foro.
4 segundos es una barbaridad.
Hay muchisimos factores que influyen y el cuello de botella puede estar en cualquier parte (red, servidor, maquina, base de datos...). Es un tema a tratar profesionalmente.
Los test que has hecho no sirven. Son solo parciales y unitarios, no de integracion. Hay que probar desde el exterior y haciendo llamadas reales que procesen informacion. Hay montones de herramientas que te pueden servir para ello. Puedes hacer un test gratuito aqui:
https://loadimpact.com/
Eso si, para testear y monitorizar bien ese volumen seguramente no te saldra gratis.
Por otro lado lo que hay que tener en cuenta es el 'pico' de usuarios/peticiones, ya que el patron de uso variara en funcion de la franja horaria. Tu sistema deberia soportar al menos el doble del pico de usuarios/peticiones.
Tu solucion debe ser extra-escalable.
Una vez en funcionamiento hay que motitorizar-escalar-monitorizar-escalar.......
3500000 usuarios, madre mia....
Un saludo y suerte