Is it OK to shard mongodb without replica set

This is a bit light on details - you don't mention some vital information like what exactly is slow (is this access via a driver for example). Replication adds a little load to the primary, but in general is pretty lightweight.

What size instances are you running, and where (replicating across regions etc.)? You might be saturating your available bandwidth when you add the replication data to the mix. I would only expect that though if you were running a write heavy application or if perhaps you were doing slaveOK reads.

Finally, as a general guide to running MongoDB in AWS, check out this white paper:

http://d36cz9buwru1tt.cloudfront.net/AWS_NoSQL_MongoDB.pdf

And these notes in the official docs:

http://www.mongodb.org/display/DOCS/Amazon+EC2

1) why do u need 4 nodes for replica set? using even number of nodes in a replica set can be very problematic, since when a failover happens, there is an election between the nodes to decide which will become the primary, read this -> http://docs.mongodb.org/manual/core/replica-set-elections/

3 nodes are more than enough, 2 actual db nodes and 1 small arbitar that just helps in election

2) regarding shard cluster -> the minimum number of physical servers for a cluster with 2 shards with the minimum replica set per shard is 9(!), the split is as follows: shard 1(replica set): 2 data nodes + 1 arbitar(can be micro instance) shard 2(replica set): 2 data nodes + 1 arbitar (can be micro instance) 3 config servers (MUST!!) - these can be rather small machines - we use t1.micro instance on amazon AWS.

Each shard u want to add to the cluster will cost u 3 more physical nodes as above.

mongos -> these are client instances that your applcation mongo driver should interact with. U can deploy them as part of any web server, so you dont need a separate machine.

see this for more info - http://docs.mongodb.org/manual/core/sharded-cluster-architectures-production/