Redis Sorted Sets are, similarly to Redis Sets, non repeating collections of Strings. The difference is that every member of a Sorted Set is associated with score, that is used in order to take the sorted set ordered, from the smallest to the greatest score. While members are unique, scores may be repeated.
Borrowing the idea from Redis, Drupal's key value store should introduce sorted sets.
The current need for this comes via the workflow initiative where we would like to store data in a key/value store but want to be able to order them or do range queries. We'd call it a sequence index and store entity activity, so that when we do content replication we can replicate in the order that activity took place.
We already have this in contrib (http://www.drupal.org/project/key_value) and hope it's just a simple case of moving to core.
Write a patch
User interface changes
An additional key value store
Data model changes
An extra database table for the new store