Adding a SQL implementation of the backing store for previews opt outs

components/previews/core/previews_opt_out_store_sql.cc

Index: components/previews/core/previews_opt_out_store_sql.cc
diff --git a/components/previews/core/previews_opt_out_store_sql.cc b/components/previews/core/previews_opt_out_store_sql.cc
new file mode 100644
index 0000000000000000000000000000000000000000..384b161f74cd3e5565e58928757a4e8aef4aa8b7
--- /dev/null
+++ b/components/previews/core/previews_opt_out_store_sql.cc
@@ -0,0 +1,193 @@
+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "components/previews/core/previews_opt_out_store_sql.h"
+
+#include "base/bind.h"
+#include "base/bind_helpers.h"
+#include "base/files/file_util.h"
+#include "base/location.h"
+#include "base/memory/ptr_util.h"
+#include "base/sequenced_task_runner.h"
+#include "base/threading/thread_task_runner_handle.h"
+#include "components/previews/core/previews_black_list_item.h"
+#include "components/previews/core/previews_experiments.h"
+#include "sql/connection.h"
+#include "sql/statement.h"
+#include "sql/transaction.h"
+
+namespace previews {
+
+namespace {
+
+// This is a macro instead of a const, so it can be used inline in other SQL
+// statements below.
+#define PREVIEWS_TABLE_NAME "previews_v1"
+
+// New columns should be added at the end of the list in order to avoid
+// complicated table upgrade.
+const char kPreviewsColumns[] =
+    "(host_name VARCHAR NOT NULL DEFAULT '',"
+    " time INTEGER NOT NULL,"
+    " opt_out INTEGER NOT NULL,"
+    " type INTEGER NOT NULL)";

[Scott Hess - ex-Googler, 2016/10/06 17:24:28]

Any unique key?  Otherwise it's just a bag of data.

Are there _any_ circumstances where you'd want to insert NULL into host_name and
have it fill with ''.  That doesn't make sense to me.

[RyanSturm, 2016/10/06 20:05:39]

Besides adding a unique key just to add a unique key, I can't really think of a
good reason to have one.

This is bag of data that will be at most 32 (entries per host) * # number of
hosts. While we only return 100 hosts to the in-memory map the current plan is
to have it be unbounded in the DB, but it might be useful to keep that limit in
the DB as well. I will add you on the code review for that CL.

Good point about "". 

[Scott Hess - ex-Googler, 2016/10/07 00:08:46]

I'm not really sure what "unbounded in the db" means in this case.  It feels
like intentionally building a latent N^2 path, which is probably not what you
wanted me to think :-).

I'm not going to require you to add keys if you don't need keys, but if you
don't use keys, then you're committing to do full-table-scans for all sorts of
things.  That might be reasonable if the database is going to remain small, but
then you need to have systems in place to keep it small.  It's hard to tell
where things are going, though, since this intentionally has no updates
implemented.  You may be hoping to avoid going there to make things easier on
yourself, but I can assure you from harsh experience that once you've got data
on user disks, some changes become _way_ more annoying to accomplish.

[RyanSturm, 2016/10/07 20:07:05]

Good point. The deleting query I wrote seem like they could be inefficient. Let
me know if you see a good way to use keys to make them more efficient. The basic
idea is that when a new entry comes in, if there are already 32 entries for the
host, the oldest one is evicted. Here are the queries:

" DELETE FROM " PREVIEWS_TABLE_NAME
" WHERE host_name == ? AND"
" time NOT IN (SELECT time FROM " PREVIEWS_TABLE_NAME
" where host_name == ?"
" ORDER BY time DESC"
" LIMIT ?)";

"INSERT INTO " PREVIEWS_TABLE_NAME
" (host_name, time, opt_out, type)"
" VALUES "
" (?, ?, ?, ?)";


"DELETE FROM " PREVIEWS_TABLE_NAME " WHERE time > ? and time < ?"

I now plan to also add a query that keeps the total entry count below 3200 based
on entry time. Thoughts on that as well?

[Scott Hess - ex-Googler, 2016/10/08 00:04:21]

How often will a new entry come in?

If it's frequent, this could probably be a bit horrible.  An index on host_name
would help for grouping things, but the table data wouldn't show locality.  I
think an index on (host_name,time) would allow this query to calculate the set
of rows to delete using only the index, and then send off specific deletes,
which I think is as good as you'll do.

Better might be to notice when things are being deleted in memory and then
delete by id.  That would imply having a unique id, though, which might not be
reasonable to add for only this, and you might not have a place to carry that
data in your store abstraction.  [I mean like "id INTEGER PRIMARY KEY", which
would be a 64-bit value assigned by SQLite that uniquely identifies every row. 
It's an alias for the rowid which is the b-tree key SQLite uses internally, so
it's index-alike.]

One possibility I've seen is to use the 64-bit timestamp as the INTEGER PRIMARY
KEY.
Is this something that would be infrequent?  Like only at startup (or a short
delay after startup)?  An index on (host_name,time) will not satisfy this kind
of time query directly, but I'm not sure if it's worth an entire index.  If it
only happens at startup, and you're already doing most of a full table scan, it
might be easier to accumulate ids to delete.
The total count for the entire database?  In that case you're talking about a db
with maybe 300k of data, right?  In that case it maybe doesn't matter much about
adding multiple indices, and it will put a cap on growth.

[RyanSturm, 2016/10/10 18:50:35]

It's a per navigation under certain conditions (2G slow network right now), so
not super frequently, but common enough for a user.
Right now, the store abstraction won't carry these ID's in memory as there is a
policy of only remembering x of the last preview navigations to the host (where
x varies by field trial and will probably be below 32).
That seems like it would help with the "clear black list" query below, so it
seems worth it.
This is pretty infrequent. It happens when a user clears history, so probably
less than once per session for most users.
Considering the size of the DB, I think I will add the unique key for timestamp
and leave it at that.

[Scott Hess - ex-Googler, 2016/10/10 19:57:45]

OK, then a mixed bag, I guess.  The dominant cost when the sub-select is not
empty is going to be the transaction overhead, locking and fsync type things. 
But if the sub-select is empty, then the cost is locking (basically free given
set_exclusive_locking), plus the overhead to calculate the sub-select.  With no
indexing, that overhead is a full table scan, which basically going to read all
the data into memory, which is not preferred for a DELETE.

I think it may make sense to have a (host_name, time) index.  The main reason
I'm reluctant to go there is because the index would basically double the
database size.  But trading database size for memory usage probably is
worthwhile.  I think you'd probably want something like:

CREATE TABLE previews_v1 (
  host_name VARCHAR NOT NULL,
  time INTEGER NOT NULL,
  opt_out INTEGER NOT NULL,
  type INTEGER NOT NULL,
  PRIMARY KEY(host_name, time DESC, opt_out, type)
)

With this, the DELETE above would be efficient in the sub-select and then only
delete the rows necessary.  SELECT with ORDER BY host_name, time DESC can read
from the index and rely on that ordering being efficient without taking up
additional memory.  INSERT will be somewhat more expensive, having to update two
pages instead of one.  The history-clearing DELETE will lose out, but I don't
think optimizing it is worth de-optimizing the other statements.

[I'm going to log a bug about this WRT https://www.sqlite.org/withoutrowid.html
and sql::Recovery.  I think WITHOUT ROWID would be a excellent fit for this case
because it collapses the index and table together, but sql::Recovery does not
support such tables at this time.  Maybe I can go out and fix it, then adapt it
back to this case.]
Does the in-memory abstraction know when the DELETE would not even be necessary?
 Like if there are 10 host_name entries in memory, will it be able to
short-circuit and not send the DELETE to the store?  That could be pretty
relevant, because it might mean the DELETE load would be substantially reduced. 
Unfortunately it's probably impossible to figure out good estimates for how much
that would help (I'd not want to code in an expensive DELETE for heavy users).
Just in case ... when you say "clears history", do you mean a Chrome-level
history clear, or do you mean clearing just the history for this feature?  If
this is tied to Chrome-level history clearing, then IMHO there's so much going
on that optimizing your history-clearing at the expensive of more-common
operations is probably pointless.

[RyanSturm, 2016/10/10 20:16:57]

Makes sense to me.
 
Unfortunately, when a host is evicted from the map and then re-added later, it
might not have enough information to determine that, so there are cases where
this is possible, but they might not be generic enough to consider sending this
signal for. For all intents and purposes, the map will only hold 4 navigations
per host and the DB holds 32, so we really might not save that much with this
approach anyway.
Chrome level clear history.

+
+struct TableInfo {
+  const char* table_name;
+  const char* columns;
+};
+
+// This is the order the columns are in within the table and within queries that
+// return columns from the table.
+enum : int {
+  OP_HOST_NAME = 0,
+  OP_TIME,
+  OP_OPT_OUT,
+  OP_TYPE,
+};
+
+const TableInfo kPreviewsTable{PREVIEWS_TABLE_NAME, kPreviewsColumns};
+
+bool CreateTable(sql::Connection* db, const TableInfo& table_info) {
+  std::string sql("CREATE TABLE ");
+  sql += table_info.table_name;
+  sql += table_info.columns;
+  return db->Execute(sql.c_str());
+}
+
+void CreateSchema(sql::Connection* db) {
+  sql::Transaction transaction(db);
+  if (!transaction.Begin())
+    return;
+
+  if (!db->DoesTableExist(kPreviewsTable.table_name)) {
+    if (!CreateTable(db, kPreviewsTable))
+      return;
+  }
+
+  transaction.Commit();
+}
+
+void InitDatabase(sql::Connection* db, base::FilePath path) {
+  db->set_page_size(4096);
+  db->set_cache_size(250);

[Scott Hess - ex-Googler, 2016/10/06 17:24:28]

How big is all this data going to be?  Like average case and at the 90th
percentile might be good things to know.

[RyanSturm, 2016/10/06 20:05:39]

I added a pretty verbose comment. Comments on it would be appreciated.

+  db->set_histogram_tag("PreviewsOptOut");
+  db->set_exclusive_locking();
+
+  base::File::Error err;
+  if (!base::CreateDirectoryAndGetError(path.DirName(), &err)) {
+    return;
+  }
+  if (!db->Open(path)) {
+    return;
+  }
+  db->Preload();
+
+  CreateSchema(db);
+}

[Scott Hess - ex-Googler, 2016/10/06 17:24:28]

So if all of this fails, you're just going to give up?  How will the situation
ever change?

[RyanSturm, 2016/10/06 20:05:39]

If it fails for this session, I don't plan for it to fix itself. The next time
the user profile is instantiated it will retry. Any ideas on a better solution?

[Scott Hess - ex-Googler, 2016/10/07 00:08:45]

It's persistent on disk, so most failures will be persistent.  If the schema is
broken, it will remain broken, if the database is corrupt, it will remain
corrupt.

There are systems for detecting and responding to errors. 
DatabaseErrorCallback() in components/omnibox/browser/shortcuts_database.cc is
probably the closest to where I'm trying to go with that.  The incidence of
corruption is pretty low, call it 1%/year, but when multiplied by our userbase
is can means many millions, and it accumulates over time (if nothing fixes it).

Another option is nuke-from-orbit.  Like an error callback calling
sql::Connection::RazeAndClose(). 
net/extras/sqlite/sqlite_persistent_cookie_store.cc does this (though I see the
RazeAndClose part is still TODO, sigh).

[RyanSturm, 2016/10/07 20:07:06]

I've gone ahead and used The DatabaseErrorCallback() approach. I don't
understand how the db gets reopened in after the recover call in 
components/omnibox/browser/shortcuts_database.cc. Is it just left to fail the db
calls after an error until a new session? I'm fine with that approach, but I'm
not sure if that is exactly what is happening.

[Scott Hess - ex-Googler, 2016/10/08 00:04:21]

Things are wired so that all future calls fail.

There's not really a clean way to re-open the database handle.  Since the
contents of the database may have changed, you'd have to tear down all of the
state the client derived from the database, and recreate it.  Clients tend not
to be written with that in mind, and it's also maybe impossible anyhow.

As-is, what happens is that changes are lost until a restart, which is weird,
but not generally locally remarkable.  The alternative without recovery is
generally that changes are lost forever, and a restart doesn't help.

[RyanSturm, 2016/10/10 18:50:35]

Acknowledged.

+
+void LoadBlackListFromDataBase(
+    sql::Connection* db,
+    scoped_refptr<base::SingleThreadTaskRunner> runner,
+    LoadBlackListCallback callback) {
+  // Gets the table sorted by host and time. Limits the number of hosts using
+  // most recent opt_out time as the limiting function.
+  const char kSql[] =
+      "SELECT full_table.host_name, full_table.time, full_table.opt_out"
+      " FROM " PREVIEWS_TABLE_NAME
+      " full_table INNER JOIN"
+      " (SELECT host_name,"
+      " MAX(CASE WHEN opt_out > 0 THEN time ELSE 0 END) AS max_opt_out_time,"
+      " MAX(time) AS max_time FROM " PREVIEWS_TABLE_NAME
+      " GROUP BY host_name"
+      " ORDER BY max_opt_out_time DESC, max_time DESC"
+      " LIMIT ?) max_host_table"
+      " ON max_host_table.host_name == full_table.host_name";

[Scott Hess - ex-Googler, 2016/10/06 17:24:28]

This is going to cause multiple full table scans.  How big is this table going
to be?  Would it be materially less efficient to just do a single scan and
filter at the C++ level?

In terms of memory usage, this is asking SQLite to maintain a hashtable of
strings to implement the GROUP BY, and that table is going to have to carry
opt-out and time state.

[RyanSturm, 2016/10/06 20:05:39]

Thanks.  C++ sounds like the way to go.

+
+  sql::Statement statement(db->GetCachedStatement(SQL_FROM_HERE, kSql));
+  statement.BindInt(0, static_cast<int>(params::MaxInMemoryHostsInBlackList()));
+  std::unique_ptr<BlackListItemMap> black_list_item_map(new BlackListItemMap());
+  // Add the host name, the visit time, and opt out history to
+  // |black_list_item_map|.
+  while (statement.Step()) {
+    std::string host_name = statement.ColumnString(OP_HOST_NAME);
+    BlackListItemMap::iterator iter = black_list_item_map->find(host_name);
+    PreviewsBlackListItem* black_list_item;
+    if (iter == black_list_item_map->end()) {
+      black_list_item = new PreviewsBlackListItem(
+          params::MaxStoredHistoryLengthForBlackList(),
+          params::BlackListOptOutThreshold(), params::BlackListDuration());
+      black_list_item_map->operator[](host_name) =
+          base::WrapUnique(black_list_item);

[Scott Hess - ex-Googler, 2016/10/06 17:24:28]

Took me a second to parse this one because of the manual operator[] call.  Maybe
(*black_list_item_map)[host_name] =?  Or
black_list_item_map->insert(std::make_pair(host_name,
WrapUnique(black_list_item))?

[RyanSturm, 2016/10/06 20:05:39]

I've moved to using a static in PreviewsBlackList; let me know if this syntax
bothers you there, and I can fix it.

+    } else {
+      black_list_item = iter->second.get();
+    }
+    // Allows the internal logic of PreviewsBlackListItem to determine how to
+    // evict entries when there are more than
+    // |StoredHistoryLengthForBlackList()| for the host.
+    black_list_item->AddPreviewNavigation(
+        statement.ColumnBool(OP_OPT_OUT),
+        base::Time::FromInternalValue(statement.ColumnInt64(OP_TIME)));
+  }
+
+  runner->PostTask(FROM_HERE,
+                   base::Bind(callback, base::Passed(&black_list_item_map)));
+}
+
+// Synchronous implementation, this is run on the background thread
+// and actually does the work to access SQL.
+void LoadBlackListSync(sql::Connection* db,
+                       const base::FilePath& path,
+                       bool needs_initialization,
+                       scoped_refptr<base::SingleThreadTaskRunner> runner,
+                       LoadBlackListCallback callback) {
+  if (needs_initialization) {

[Scott Hess - ex-Googler, 2016/10/06 17:24:28]

Any reason you're using this odd flag-passing rather than just testing
db->is_open()?

[RyanSturm, 2016/10/06 20:05:39]

Done.

+    InitDatabase(db, path);
+  }
+
+  if (!db->is_open() || !db->DoesTableExist(kPreviewsTable.table_name)) {
+    std::unique_ptr<BlackListItemMap> black_list_item_map(
+        new BlackListItemMap());
+    runner->PostTask(FROM_HERE,
+                     base::Bind(callback, base::Passed(&black_list_item_map)));
+  }
+
+  LoadBlackListFromDataBase(db, runner, callback);

[Scott Hess - ex-Googler, 2016/10/06 17:24:28]

I think that if you implemented LoadBlackListFromDatabase() to return
unique_ptr<BLIM>, with a single post back to the callback here, it would work
fine.  The sql:: layer would throw some error messages and fail some DCHECKS,
but the case of "The database was not opened or failed to initialize" is
expected to _never_ happen, so that is reasonable.

WRT the DCHECKS, there is support for expecting errors in testing, so if that's
why you're doing these checks, let me know and I can give you pointers.

[RyanSturm, 2016/10/06 20:05:39]

I think I understand what you are saying, so let me know if the new approach
looks good.

[Scott Hess - ex-Googler, 2016/10/07 00:08:45]

I was thinking more like having LoadBlackListFromDatabase() as a standalone
helper which converts sql into a unique_ptr<BlackListItemMap>, then with
LoadBlackListSync() a wrapper which knows about initializing databases and
calling callbacks.  But it's six of one, half a dozen of the other.

[RyanSturm, 2016/10/07 20:07:06]

Acknowledged.

+}
+
+}  // namespace
+
+PreviewsOptOutStoreSQL::PreviewsOptOutStoreSQL(
+    scoped_refptr<base::SingleThreadTaskRunner> io_task_runner,
+    scoped_refptr<base::SequencedTaskRunner> background_task_runner,
+    const base::FilePath& path)
+    : io_task_runner_(io_task_runner),
+      background_task_runner_(background_task_runner),
+      db_file_path_(path.AppendASCII("Previews.db")),
+      initialized_(false) {}
+
+PreviewsOptOutStoreSQL::~PreviewsOptOutStoreSQL() {
+  DCHECK(io_task_runner_->BelongsToCurrentThread());
+  if (db_.get()) {
+    background_task_runner_->DeleteSoon(FROM_HERE, db_.release());
+  }
+}

[Scott Hess - ex-Googler, 2016/10/06 17:24:28]

Is there any protection against an outstanding LoadBlackListSync() in progress
at this point?

[RyanSturm, 2016/10/06 20:05:39]

My understanding of task runners is that the LoadBlackListSync call will
complete before the Delete happens on that thread.

[Scott Hess - ex-Googler, 2016/10/07 00:08:45]

Yeah.  I found it - the LoadBlackList() callback targets a weak pointer, so if
there's an outstanding LoadBlackListSync(), the response will just drain.

[RyanSturm, 2016/10/07 20:07:05]

Acknowledged.

+
+void PreviewsOptOutStoreSQL::AddPreviewNavigation(bool opt_out,
+                                                  const std::string& host_name,
+                                                  PreviewsType type,
+                                                  base::Time now) {}
+
+void PreviewsOptOutStoreSQL::LoadBlackList(LoadBlackListCallback callback) {
+  DCHECK(io_task_runner_->BelongsToCurrentThread());
+  if (!db_)
+    db_.reset(new sql::Connection());
+  background_task_runner_->PostTask(
+      FROM_HERE,
+      base::Bind(&LoadBlackListSync, db_.get(), db_file_path_, !initialized_,
+                 base::ThreadTaskRunnerHandle::Get(), callback));
+  initialized_ = true;
+}
+
+}  // namespace previews