The increasing popularity of Internet of Things (IoT) services causes tremendous growth of the amount of produced data. These data must be effectively stored and retrieved by the IoT service providers. The solution is to access the data through application programming interfaces. The paper focuses on the problem of designing an effective data storage service for IoT, which will be available through the universal application programming interface. We propose and analyze eight variants of the distributed data storage service that differ in the database structure, that is, the hierarchical structure based on Data-Oriented Network Architecture or the flat structure based on distributed hash table, the type of stored records, and the memory management algorithm that decides about using cache or base memory. The proposed solutions have been evaluated in the comprehensive simulation studies. The obtained results confirmed the effectiveness of the preferred solution with Dynamic Routing Records stored in the cache memory.