Instance messaging service

A non-transitory computer-readable storage medium including instructions that, upon execution, cause a computer system to:

• store a message in a network storage of a distributed computing environment;
• the message received from a first host server computer of a first plurality of host server computers and addressed to a target virtual machine instance (VMI);
• communicate a notification of the message to a second plurality of host server computers associated with a plurality of virtual machine instances (VMIs) running within the distributed computing environment, without communicating at least a portion of the message;
• and
• upon determining that a second host server computer of the second plurality of host server computers is associated with the target MI, forwarding the received message to the target VMI;
• and
• store at a local cache within the second host server computer, a time the notification was received at the second host server computer and an identification of the message associated with the notification.

A system, comprising:

• a plurality of server computers coupled together through a network to form a distributed computing environment, at least a first portion of the server computers for executing virtual machine instances, and at least a second portion of the server computers for executing one or more services of the distributed computing environment;
• an instance messaging service communicatively coupled to the plurality of server computers and to a network storage device, the instance messaging service operable to:
• store a message received from the one or more services in the network storage device, the message identifying at least one of the virtual machine instances as a receiving instance;
• in response to a request for undelivered messages from the receiving instance, determine that a message queue contains a notification of the received message;
• and
• deliver the message from the network storage device to the receiving instance.