S3: AmazonS3Exception: Please reduce your request rate/Timeout waiting for connection from pool exception when running load tests

Hi, I'm running load tests against a library which essentially interacts with S3 to put and get objects. It works well until 3000-3500TPS but beyond that it starts throwing the following exceptions.

Seeing throttling exceptions "Caused by: com.amazonaws.services.s3.model.AmazonS3Exception: Please reduce your request rate. (Service: Amazon S3; Status Code: 503; Error Code: SlowDown; Request ID: GTAPGZK7E9KQQX3V; S3 Extended Request ID: O8XMzbmn0G51h01gogNrm0zHRkyGbGnhVJs+6WdvyTnAQ62kV/K7Au4wdz5z69WuhEFyaoXc4gqasaFEd8mSvA==; Proxy: null)" with 0 retries,

Caused by: com.amazonaws.services.s3.model.AmazonS3Exception: Please reduce your request rate. (Service: Amazon S3; Status Code: 503; Error Code: SlowDown; Request ID: GTAPGZK7E9KQQX3V; S3 Extended Request ID: O8XMzbmn0G51h01gogNrm0zHRkyGbGnhVJs+6WdvyTnAQ62kV/K7Au4wdz5z69WuhEFyaoXc4gqasaFEd8mSvA==; Proxy: null)

and Timeout waiting for connection from pool with a adaptive backoff retry strategy with max retries of 5. Majority of them are "Timeout waiting for connection from pool":

com.amazonaws.SdkClientException: Unable to execute HTTP request: Timeout waiting for connection from pool
com.amazonaws.SdkClientException: Unable to execute HTTP request: Remote host terminated the handshake
com.amazonaws.SdkClientException: Unable to execute HTTP request: The target server failed to respond

I have gone through multiple articles and ensured that

1. All objects are closed explicitly or used try with resources blocks.
2. I'm incrementally increasing the TPS to ensure there is enough warm up period. Started with 500TPS for 5mins, and 1000TPS for 5mins and increased 1000TPS for every 5mins until 8000TPS. It starts failing at about 4000TPS.
3. Partition prefix is unique for objects, so the TPS per partition isn't exceeded the limits.

final String message = UUID.randomUUID().toString();
final String key = String.format("%s/%s/%s.%s", getPartitionPrefix(message), message, message, "kms");

    private String getPartitionPrefix(final String uniqueMessageId) {
        try
        {
            final byte[] hashBytes =
                    MessageDigest.getInstance("MD5").digest(uniqueMessageId.getBytes("UTF-8"));
            final String hashString = Base64.getEncoder()
                    .encodeToString(hashBytes).substring(0, PARTITION_CHARS);
            // If the partition prefix is "soap", S3 interprets the request as an attempt
            // to hit the S3 soap API and returns an error (HTTP 405)
            // So mapping "soap" to another bucket. 
            if(SOAP.equals(hashString))
            {
                return ALTERNATE_PARTIION_NAME_FOR_SOAP;
            }
            return hashString;
        }
        catch (final NoSuchAlgorithmException | UnsupportedEncodingException e)
        {
            throw new RuntimeException(e.getClass() + ": " + e.getMessage(), e);
        }
    }

4. This is how my S3 Client is built:

AmazonS3ClientBuilder.standard()
                            .withCredentials(
                                    CredentialsModule.getCredentialProvider(clientId, CBEV2_S3_WRITE_ROLE_ARN_MAP.get(clientId))
                            )
                            .withClientConfiguration(new ClientConfiguration()
                                    .withConnectionTimeout(1000)
                                    .withSocketTimeout(4000)
                                    .withMaxConnections(8000)
                                    .withProtocol(Protocol.HTTPS)
                                    .withCacheResponseMetadata(false)
                                    .withTcpKeepAlive(true)
                                    .withRetryPolicy(RetryPolicy.builder()
                                            .withMaxErrorRetry(5)
                                            .withRetryMode(RetryMode.ADAPTIVE)
                                            .withBackoffStrategy(PredefinedRetryPolicies
                                                    .getDefaultBackoffStrategy(RetryMode.ADAPTIVE))
                                            .build()))
                            // Allow global bucket access as buckets are not guaranteed to be in the same region as the endpoint.
                            .withForceGlobalBucketAccessEnabled(true)
                            .build();

I have tried a range of max connections starting from 100-100,000.

5. I'm running load tests with a TPSGenerator multihost (about 58hosts are working for 4000TPS, which I believe is quite overprovisioned to support it)