1. An article of manufacture including program code which, when executed by a machine, causes the machine to implement a messaging service method, the method comprising: incorporating messages into cached link lists, said messages not yet acknowledged as having been received by one or more consumers to whom said messages were sent, a separate link list existing for each of a plurality of different message priority levels, messages within a same link list ordered in said same link list in the same order in which said messages where received by said messaging service, at least one of said link lists containing an element that represents one or more messages that are persisted but are not cached in any of said cached link lists.