[Webkit-unassigned] [Bug 192736] HTTPS Upgrade: Use full sqlite upgrade list

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=192736

--- Comment #17 from Vivek Seth <v_seth at apple.com> ---
> Were any other formats for the database considered other than sqlite? 

I considered 3 formats so far: 

A. simple sqlite table 1 column with index on it (what is implemented now)
B. sqlite table with 2 columns: domain and 4 byte hash. The hash column is indexed.
C. a custom implementation of "Hierarchies of Indexes" (Kärkkäinen J., Srinivasa Rao S. (2003) Full-Text Indexes in External Memory). Basically the format reduces disk seeks by using a small binary search tree to index into other binary search trees.

All the options meet our performance threshold for devices with fast SSDs (iPhone, iPad, SSD Macs). They can all search a list of up to 10M domains in <1ms. Format A is the fastest, then B, then C.

For devices with slower disks (SSD macs and Apple Watch) format C is the fastest, then B, then A. 

In terms of disk-space overhead format C is the best (6 bytes per domain), then B (28 bytes per domain), then A (40 bytes per domain). 

I've implemented format A for now, but since we would like to support HDD macs, I may switch to format B in another patch. Format C needs significant testing before we can consider using it. 

Feel free to send me an email/meet me in-person if you would like to discuss in more detail. 

> Given that list seems to be immutable (at least from WebCore's perspective), something like a persistent on-disk trie might be more efficient here.

I'm not very familiar with on-disk tries. Are you thinking of something like what is described in "M. Mosharaf Kabir Chowdhury, N & Mostofa Akbar, Md & Kaykobad, Mohammad. (2007). DiskTrie: An Efficient Data Structure using Flash Memory for Mobile Devices." ? 

It seems like DiskTrie works best on disks with fast random access like SSDs. I'm not sure how well it would perform on HDD macs or Apple Watch. If you know of a open-source implementation I might be able to try it out. 

Even if its better, I think we should consider switching to it in a future patch.

-- 
You are receiving this mail because:
You are the assignee for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.webkit.org/pipermail/webkit-unassigned/attachments/20181219/d5f72eae/attachment.html>