Understanding state as data store

I’m trying to get my head around using state as a data store, coming from sql and nosql I’m a bit confused (easily done!)

Say I had a todo app, where todo’s were stored in a sql db, to get a users todo list I’d query the db where user_id = the signed in user.

If I use a hashmap or trie, how would I query it to get the data for a specific user? Would I create a store for each user, using say the principal for the user as the name of the store? Or would I have one big store for all the users?

There are many approaches. In a basic scenario, I would just store each user in a hashmap keyed by some user-id and then create a number of other hashmaps which would index this users any way I need.

type UserId = u64;
type Year = u16;
type Name = String;

struct User {
  name: Name,
  year_of_birth: Year,
  ...
}

struct State {
  users: HashMap<UserId, User>,
  users_name_index: HashMap<Name, BTreeSet<UserId>>,
  users_year_of_birth_index: HashMap<Year, BTreeSet<UserId>>,
}
2 Likes

thanks senior. I think that makes sense - I’ll try it out…

For anyone stumbling across this with the same confusion as me, I found this helpful - data-structures/module-1.md at main · DFINITY-Education/data-structures · GitHub

1 Like

I’ve been taking heavy inspiration (borderline plagarism) from CanCan in terms of what data structures to use and how to model my app state with these data structures.


Basically, I’m using two fundamental data types: Maps (1-to-1 mappings) and Rels (many-to-many binary relations).

Maps are used to associate object IDs with object metadata, like user_id => user_profile.

Rels are used to associate object IDs with other object IDs, like user_id <=> video_id (i.e. what videos has this user watched? what users have watched this video?).

Maps can be implemented using HashMap or Trie—personally, I’m using Trie because it’s purely functional and can be stored in stable memory, whereas object-oriented data structures like HashMap cannot. Rels can similarly be implemented using two Maps.


So far, all of the above has just been data modeling, i.e. what tables and primary/foreign keys to use in SQL. Another important consideration is query performance, what indexes to create for each table. I’m thinking of augmenting each Map/Rel with additional data structures, one for each query I want to optimize. Haven’t decided on what exactly, but the overall setup will make it so that updating a user profile updates not only the user_id => user_profile Map but also a bunch of other “index” data structures, like RBTree.

7 Likes