Implement IndexedDB.

[Ms2ger]

(Just filing as a placeholder.)

[farodin91]

I like to work on it. Some Questions before a start to work. Can help me someone, who work on it in firefox? I need to create many WebIDLs, is possible to create a folder like "indexed". To add all files inside this folder, for example http://mxr.mozilla.org/mozilla-central/source/dom/

[Manishearth]

cc @nox

Note that this is a pretty large project.

To start, you'll need to pick a backend and write Rust bindings for it. We were thinking SQLite4 or a LevelDB fork, probably the former.

[jdm]

@farodin91 We don't support subdirectories in dom/ yet; I don't think it's worth blocking on that.

[Manishearth]

@jdm Technically we just need to use reexports and it will work fine.

[nox]

@Manishearth SQLite 4 suffers from a complete lack of bindings and my days are unfortunately made of 24 hours like everyone. :(

[farodin91]

@Manishearth I can start with building an rust api for SQLite 4.

[jdm]

That sounds valuable :)

[farodin91]

I like to write a binding in rust for SQLite. Any prefer which lib to use for it?

[Manishearth]

There is only one SQLite 4 :smile:

https://sqlite.org/src4/tree?ci=trunk

https://sqlite.org/src4/doc/trunk/www/index.wiki

[farodin91]

This is my first time to create an rust binding. Is there a small example for it

[jdm]

https://doc.rust-lang.org/book/ffi.html is a good start.

[nox]

Please note that SQLite resides in a Fossil repository. I had started writing bindings for them, but it's very primitive for now. I can push that somewhere this week if you want.

[farodin91]

I create an repo for this. I can start to work on it this week. Thank you.

[farodin91]

@nox Any update on pushing the in my repo?

[nox]

Sorry things were a bit hectic for me this week.

[farodin91]

No problem

[farodin91]

I start work on it https://github.com/farodin91/sqlite-rs. But currently my build script doesn't work to build sqlite4 on linux. I have no idea.

[farodin91]

Any update to pushing in my repo?

[farodin91]

@nox Any updates? It is also possible to use LevelDB with lib https://github.com/skade/leveldb.

[KiChjang]

I'm picking this up. Will start by writing SQLite 4 Rust bindings.

[amarant]

It seems there is no commit in SQLite 4 since 2015-08-15 and never had an official release, doesn't levelDB seems more mature (already used for indexeddb in Chrome) ?

[Manishearth]

That might just be because they intend SQLite 4 to be stable. SQLite is under active development, see https://www.sqlite.org/src/timeline . That might be SQLite 3, but I think the codebase is mostly shared.

[KiChjang]

@Manishearth What was the reason for choosing SQLite4 over SQLite3? If we are to choose SQLite3 instead, we can use existing crates that have already generated bindings for it.

[Manishearth]

4 is a kv store, 3 isn't. It's not just a version number.

We need a NoSQL db for IDB. Ironically, SQLite 4, is more or less NoSQL.

[KiChjang]

Here's what I discovered - someone has already written Python bindings for the SQLite 4 backend LSM DB. I wonder if I should do the same, instead of writing bindings directly to SQLite 4?

[jdm]

"Need" is a strong word, given an existing implementation in Gecko that uses sqlite3.

[KiChjang]

Per the conversation at IRC, it looks like there's only 2 viable alternatives:

• SQLite3; or
• LevelDB

SQLite4 is determined to be not mature enough for implementation now.

[KiChjang]

Spec link: http://w3c.github.io/IndexedDB/

[nox]

I'm going to use SQLite3.

For database storage, we have two ways:

• We can do like Gecko, and create a SQLite database per IndexedDB database.
  • 👍 We can open the database with any SQLite tool and we have everything at once.
  • 👎 We will never have concurrent transactions when one of them is a write transaction.
    
    
• We can create one SQLite database per IndexedDB object store.
  • 👍 By using ATTACH, we can lock on a per-object store basis and still do transactions that encompass multiple object stores.
  • 👎 It becomes a bit harder to see everything from an IndexedDB database at once with SQLite tools.
    
    

For indices, we also have two ways, the old Gecko way and a very fancy way that I would like to experiment with:

• We can do like Gecko, and have SQLite tables for IndexedDB indices. In Gecko elements from all object stores are stored in a single table and all the entries in all indices are also stored in two tables, one with a PK for unique indices, and another one for non-unique indices.
  • 👍 We can open the database with any SQLite tool and we have everything at once.
  • 👎 It duplicates a lot of data for each index.
    
    
• We can do like the json1 SQLite extension and implement and document a "Serialised Structure Clone" binary subtype in SQLite, and then implement a function to extract a key path from this format (similar to the json function in json1). We can then use that method to create an index on an expression for each IndexedDB index we want. We can make that function return NULL when the key path is not found, and use a partial index to ignore such values.
  • 👍 It is quite cool as a show case of what fancy things we do.
  • 👍 We can enforce that the things we put in that database are actually serialised structure clones.
  • 👍 It makes IndexedDB indices piggyback SQLite indices.
  • 👎 It requires custom pluggable code into SQLite and these APIs aren't bound in the existing SQLite crates.
    
    

Some interesting links:

• http://searchfox.org/mozilla-central/source/dom/indexedDB/ActorsParent.cpp#1049
• https://www.icloud.com/keynote/0BQLoCXOuQI02OBl2ekjGq6OA
• https://www.sqlite.org/c3ref/result_subtype.html
• https://www.sqlite.org/loadext.html
• https://www.sqlite.org/c3ref/create_function.html

[nox]

This would also require a reimplementation of the serialised structured clone format described here (or something similar to it that we can store and introspect directly from SQLite).

[nox]

We can't use ATTACH for my first idea because its documentation states that it's not really robust when faced with crashes.

[nox]

There are various things necessary on the Servo side, at least these three things:

• Port https://dxr.mozilla.org/mozilla-central/source/dom/indexedDB/Key.cpp to Rust code.
• Be able to know whether JS code failed from a queued task.
• Be able to know whether any event handler propagated an exception when firing an event.

[ferjm]

Blocks #13942

[tigercosmos]

hi @nox, do you know if the issue has advanced any further? Thanks!

[jdm]

It has not.

[rasviitanen]

I am looking for a new task, and I thought this one was interessting. I have a few questions before I am comfortable claiming this issue.

As I understand it, IndexedDB should be implemented using a WAL to favor performance. This decision was taken in Gecko, and is seen in Chrome/IE. See change here. Despite the new 3.0 specification states it to be durable.

Since SQLite4 never got released, and SQLite3 not being the obvious choice, perhaps RocksDB is a valid option?

It is wildly used, and seems to fit indexeddb and servo quite well, i.e. fast and concurrent; embedded KV store. https://rocksdb.org/ https://rocksdb.org/docs/support/faq.html

It also has great rust bindings through rust-rocksdb used by e.g. TiDB. This would make it a lot easier to get a working IndexedDB.

Thoughts?

[jdm]

Seems like it's worth a shot!

[rasviitanen]

@highfive: assign me

[highfive]

Hey @rasviitanen! Thanks for your interest in working on this issue. It's now assigned to you!

[asutherland]

Just to provide some context on SQLite and other storage choices as they're being used in Gecko/Firefox:

Re: SQLite

• SQLite 4 was an experiment and the fancy bits (WITHOUT ROWID in particular, which allows for tables to be effectively maintain the lexical row ordering directly without indirecting through primary keys) are now in SQLite 3.
• Firefox is overhauling how we implement storage as it relates to PrivateBrowsing. Previously implementations had to be in-memory only and data would never touch disk. We're now moving to store data on disk in an encrypted form with the keys never persisted. We delete the storage at the end of the private browsing session. In the event of a crash, the data is encrypted and then only subject to analysis of what's on disk. SQLite's VFS layer makes this not too difficult, and SQLite's page-centric storage model potentially helps with the analysis-at-rest concern. (I haven't thought too much about how that would compare with log-structured-merge independent files on disk.)
• Mozilla Corporation is a SQLite consortium member which gets us insanely professional levels of support in terms of investigations of problems we're experiencing involving SQLite, guidance, etc. They take writing safe C seriously and have an incredibly comprehensive test corpus.

Re: other options:

• https://github.com/mozilla/rkv has been landed in Gecko as a rust layer on top of the LMDB engine. I think rkv/LMDB sounded more promising than it's turned out to be, especially with there being limitations like 512-byte key limits, but it sounds like the Browser Architecture Group team may be serious about keeping this around.

Re: selfish concerns on my part ;)

• The existing Gecko IndexedDB implementation is a lot of fairly grungy C++ and we will be looking longer term to replace it with a rust implementation. It's not clear that Gecko could justify the increase in binary size of the RocksDB engine, so selfishly it would be nice if Servo used a databse implementation compatible with what Gecko is already using.
  • I think there may be in-tree https://github.com/jgallagher/rusqlite users already? But honestly, based on a quick skim of diesel, its ORM-ish mapping potentially seems like it allows for less accidental mismatches when binding statements.
• That said, the Gecko implementation may have some architectural considerations that don't make sense for an initial servo IndexedDB implementation. Specifically, with fisssion potentially consolidating origins into a single process (but potentially also not), we may want to shift where we store the canonical state and perform caching. Especially for API's like https://github.com/WICG/kv-storage that build on IndexedDB and can potentially very performance-conscious as they're competing against localStorage.