Из вашего описания кажется, что какое-то хранилище значений ключей будет лучше для вас, сравнивая реляционные БД.
Сами данные кажутся нереляционными.Кажется правильным использовать что-то вроде Cassandra.
Я думаю, что типичной структурой данных для хранения этих данных будет семейство столбцов с Key как Row-key и Columns в качестве значения.
Данные будут выглядеть (нотация JSON):
MyDATA (CF){
[
{key1:[{val1-1:'', timestamp}, {val1-2:'', timestamp}, .., {val1-500:'', timestamp}]},
{key2:[{val2-1:'', timestamp}, {val2-2:'', timestamp}, .., {val2-500:'', timestamp}]},
...
...
]
}
Надеюсь, это поможет.