Lotus Notes was first. Distributed, replicated key value store.

Actually I'm not right: http://blog.knuthaugen.no/2010/03/a-brief-history-of-nosql.h...