Add one-time randomization support for FieldTrial, and the ability to

base/metrics/field_trial.h

 // Copyright (c) 2011 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.
 
 // FieldTrial is a class for handling details of statistical experiments
 // performed by actual users in the field (i.e., in a shipped or beta product).
 // All code is called exclusively on the UI thread currently.
 //
 // The simplest example is an experiment to see whether one of two options
 // produces "better" results across our user population.  In that scenario, UMA
 // data is uploaded to aggregate the test results, and this FieldTrial class
 // manages the state of each such experiment (state == which option was
 // pseudo-randomly selected).
 //
 // States are typically generated randomly, either based on a one time
-// randomization (generated randomly once, and then persistently reused in the
-// client during each future run of the program), or by a startup randomization
-// (generated each time the application starts up, but held constant during the
-// duration of the process), or by continuous randomization across a run (where
-// the state can be recalculated again and again, many times during a process).
-// Only startup randomization is implemented thus far.
+// randomization (which will yield the same results, in terms of selecting
+// the client for a field trial or not, for every run of the program on a
+// given machine), or by a startup randomization (generated each time the
+// application starts up, but held constant during the duration of the
+// process), or by continuous randomization across a run (where the state
+// can be recalculated again and again, many times during a process).
+// Continuous randomization is not yet implemented.
 
 //------------------------------------------------------------------------------
 // Example:  Suppose we have an experiment involving memory, such as determining
 // the impact of some pruning algorithm.
 // We assume that we already have a histogram of memory usage, such as:
 
 //   HISTOGRAM_COUNTS("Memory.RendererTotal", count);
 
 // Somewhere in main thread initialization code, we'd probably define an
 // instance of a FieldTrial, with code such as:
@@ skipping 13 matching lines @@
 // if (trial->group() == kHighMemGroup)
 //   SetPruningAlgorithm(kType1);  // Sample setting of browser state.
 // else if (trial->group() == kLowMemGroup)
 //   SetPruningAlgorithm(kType2);  // Sample alternate setting.
 
 // We then, in addition to our original histogram, output histograms which have
 // slightly different names depending on what group the trial instance happened
 // to randomly be assigned:
 
 // HISTOGRAM_COUNTS("Memory.RendererTotal", count);  // The original histogram.
-// static bool use_memoryexperiment_histogram(
-//     base::FieldTrialList::Find("MemoryExperiment") &&
-//     !base::FieldTrialList::Find("MemoryExperiment")->group_name().empty());

[jar (doing other things), 2011/04/21 22:10:02]

Removal of this code is a VERY good improvement.  The class has evolved, and I
think you are totally correct, that the name can no longer be empty (since the
commitment is made when we query the state... and worst case, it becomes the
default string... which is required to be non-empty).

There are a number of places where the above pattern is currently used, and
should be simplified to match your correction.  Search for:
FieldTrialList::Find

to get a list.

If you don't want to do this, please file a bug against me and I'll do the
cleanup.

[Jói, 2011/04/28 01:03:50]

I've updated all the call-sites now.  I introduced a new static function
TrialExists(name) that is equivalent to !!Find(name) to avoid having to coerce
to boolean at every call-site.  I also updated the docs to suggest using a
static const bool to store the results of the find, as that seems like a good
idea in most cases.

[Jói, 2011/05/02 18:55:03]

FYI, there were some merge changes to resolve, I updated call sites again.

-// if (use_memoryexperiment_histogram) {
+// if (FieldTrialList::Find("Memory.RendererTotal")) {
 //   HISTOGRAM_COUNTS(FieldTrial::MakeName("Memory.RendererTotal",
 //                                         "MemoryExperiment"), count);
 // }
 
 // The above code will create four distinct histograms, with each run of the
 // application being assigned to of of the three groups, and for each group, the
 // correspondingly named histogram will be populated:
 
 // Memory.RendererTotal              // 100% of users still fill this histogram.
 // Memory.RendererTotal_HighMem      // 2% of users will fill this histogram.
@@ skipping 26 matching lines @@
   // A return value to indicate that a given instance has not yet had a group
   // assignment (and hence is not yet participating in the trial).
   static const int kNotFinalized;
 
   // This is the group number of the 'default' group. This provides an easy way
   // to assign all the remaining probability to a group ('default').
   static const int kDefaultGroupNumber;
 
   // The name is used to register the instance with the FieldTrialList class,
   // and can be used to find the trial (only one trial can be present for each
-  // name).
+  // name).  |name| and |default_group_name| may not be empty.
+  //
   // Group probabilities that are later supplied must sum to less than or equal
   // to the total_probability. Arguments year, month and day_of_month specify
   // the expiration time. If the build time is after the expiration time then
   // the field trial reverts to the 'default' group.
+  //
+  // Using this constructor creates a startup-randomized FieldTrial. If you
+  // want a one-time randomized trial, call UseOneTimeRandomization() right
+  // after construction.
   FieldTrial(const std::string& name, Probability total_probability,
              const std::string& default_group_name, const int year,
              const int month, const int day_of_month);
 
+  // Changes the field trial to use one-time randomization, i.e. produce the
+  // same result for the current trial on every run of this client. Must be
+  // called right after construction.
+  //
+  // Before using this method, |FieldTrialList::EnableOneTimeRandomization()|
+  // must be called exactly once.
+  void UseOneTimeRandomization();
+
+  // Disables this trial, meaning it always determines the default group
+  // has been selected. May be called immediately after construction, or
+  // at any time after initialization (should not be interleaved with
+  // AppendGroup calls). Once disabled, there is no way to re-enable a
+  // trial.
+  void Disable();
+
   // Establish the name and probability of the next group in this trial.
   // Sometimes, based on construction randomization, this call may cause the
   // provided group to be *THE* group selected for use in this instance.
   // The return value is the group number of the new group.
   int AppendGroup(const std::string& name, Probability group_probability);
 
   // Return the name of the FieldTrial (excluding the group name).
   std::string name() const { return name_; }
 
   // Return the randomly selected group number that was assigned.
   // Return kDefaultGroupNumber if the instance is in the 'default' group.
   // Note that this will force an instance to participate, and make it illegal
-  // to attempt to probabalistically add any other groups to the trial.
+  // to attempt to probabilistically add any other groups to the trial.
   int group();
 
-  // If the field trial is not in an experiment, this returns the empty string.
-  // if the group's name is empty, a name of "_" concatenated with the group
+  // If the group's name is empty, a string version containing the group
   // number is used as the group name.
   std::string group_name();
 
   // Return the default group name of the FieldTrial.
   std::string default_group_name() const { return default_group_name_; }
 
-  // Helper function for the most common use: as an argument to specifiy the
+  // Helper function for the most common use: as an argument to specify the
   // name of a HISTOGRAM.  Use the original histogram name as the name_prefix.
   static std::string MakeName(const std::string& name_prefix,
                               const std::string& trial_name);
 
   // Enable benchmarking sets field trials to a common setting.
   static void EnableBenchmarking();
 
  private:
   // Allow tests to access our innards for testing purposes.
   FRIEND_TEST(FieldTrialTest, Registration);
   FRIEND_TEST(FieldTrialTest, AbsoluteProbabilities);
   FRIEND_TEST(FieldTrialTest, RemainingProbability);
   FRIEND_TEST(FieldTrialTest, FiftyFiftyProbability);
   FRIEND_TEST(FieldTrialTest, MiddleProbabilities);
   FRIEND_TEST(FieldTrialTest, OneWinner);
   FRIEND_TEST(FieldTrialTest, DisableProbability);
   FRIEND_TEST(FieldTrialTest, Save);
   FRIEND_TEST(FieldTrialTest, DuplicateRestore);
   FRIEND_TEST(FieldTrialTest, MakeName);
+  FRIEND_TEST(FieldTrialTest, HashClientId);
+  FRIEND_TEST(FieldTrialTest, HashClientIdIsUniform);
+  FRIEND_TEST(FieldTrialTest, UseOneTimeRandomization);
 
   friend class base::FieldTrialList;
 
   friend class RefCounted<FieldTrial>;
 
   virtual ~FieldTrial();
 
   // Returns the group_name. A winner need not have been chosen.
   std::string group_name_internal() const { return group_name_; }
 
   // Get build time.
   static Time GetBuildTime();
 
+  // Calculates a uniformly-distributed double between [0.0, 1.0) given
+  // a |client_id| and a |trial_name| (the latter is used as salt to avoid
+  // separate one-time randomized trials from all having the same results).
+  static double HashClientId(const std::string& client_id,
+                             const std::string& trial_name);

[jar (doing other things), 2011/04/21 22:10:02]

I would have expected the client_id to be a constant, that is held in a class
static (accessible via a public static method in the singleton for
FieldTrialList).  I'd then expect that the trial_name could be extracted from
the FieldTrial instance, which could be done by making this a non-static method.
 

Is there a good reason for this to be a static method?

[Jói, 2011/04/28 01:03:50]

 2011/04/21 22:10:02, jar wrote:
The main reason I chose this interface is that it's a lot lighter-weight to
test, no need to set up various FieldTrialTest instances.  It's a private
implementation detail and it should be just as performant as if it were a
method, so in my opinion it doesn't need to be changed.

+
   // The name of the field trial, as can be found via the FieldTrialList.
-  // This is empty of the trial is not in the experiment.
+  // This is empty if the trial is not in the experiment.

[jar (doing other things), 2011/04/21 22:10:02]

hmmm.... is this ever empty now?

[Jói, 2011/04/28 01:03:50]

You're right, I updated the documentation and added a DCHECK in the constructor
to ensure the name is never empty.

   const std::string name_;
 
   // The maximum sum of all probabilities supplied, which corresponds to 100%.
   // This is the scaling factor used to adjust supplied probabilities.
   const Probability divisor_;
 
   // The name of the default group.
   const std::string default_group_name_;
 
   // The randomly selected probability that is used to select a group (or have
   // the instance not participate).  It is the product of divisor_ and a random
   // number between [0, 1).
-  const Probability random_;
+  Probability random_;
 
   // Sum of the probabilities of all appended groups.
   Probability accumulated_group_probability_;
 
   int next_group_number_;
 
   // The pseudo-randomly assigned group number.
   // This is kNotFinalized if no group has been assigned.
   int group_;
 
-  // A textual name for the randomly selected group. If this Trial is not a
-  // member of an group, this string is empty.
+  // A textual name for the randomly selected group. Valid after |group()|
+  // has been called.
   std::string group_name_;
 
-  // When disable_field_trial_ is true, field trial reverts to the 'default'
+  // When enable_field_trial_ is false, field trial reverts to the 'default'
   // group.
-  bool disable_field_trial_;
+  bool enable_field_trial_;

[jar (doing other things), 2011/04/21 22:10:02]

Thanks for making this change!

[Jói, 2011/04/28 01:03:50]

No prob.

 
   // When benchmarking is enabled, field trials all revert to the 'default'
   // group.
   static bool enable_benchmarking_;
 
   DISALLOW_COPY_AND_ASSIGN(FieldTrial);
 };
 
 //------------------------------------------------------------------------------
 // Class with a list of all active field trials.  A trial is active if it has
@@ skipping 46 matching lines @@
   static TimeTicks application_start_time() {
     if (global_)
       return global_->application_start_time_;
     // For testing purposes only, or when we don't yet have a start time.
     return TimeTicks::Now();
   }
 
   // Return the number of active field trials.
   static size_t GetFieldTrialCount();
 
+  // Sets an opaque, diverse ID for this client that does not change
+  // between sessions.  This must be called exactly once before any call to
+  // |FieldTrial::UseOneTimeRandomization()| and does not need to be called
+  // unless such a call is made.
+  static void EnableOneTimeRandomization(const std::string& client_id);

[jar (doing other things), 2011/04/21 22:10:02]

I'd be tempted to make this part of required initialization, passed into the
constructor on line 248, and then have assertions rather than the test at line
302.

The only concern is the lack of a value for the persistent id.  I'd suggest that
there be a constant, defined in metrics_services, which is
kUNINITALIZED_CLIENT_ID (or something of that sort).  The constructor can then
detect this non-initialized state rather directly.

[Jói, 2011/04/28 01:03:50]

I disagree, but am willing to be overridden.  Let me explain why I disgaree:

I think it's nice to be able to use FieldTrial / FieldTrialList without
necessarily having a one-time random ID for your client.  It's also more
flexible to be able to defer initializing the FieldTrialList with this until you
actually need it (right before you create any one-time randomized trials) rather
than having to do it at construction time.

For the ability of using the FieldTrialList without providing a one-time ID, if
you were suggesting allowing users to specify "not initialized" in the
constructor, I think it makes for a cleaner public interface not to have to
declare a "not initialized" value in the header file and document on the
constructor that callers need to use it - cleaner to keep that detail
implementation-private by using a separate initialization function, and safer
since callers might not read the documentation and might specify e.g. some
static string as the one-time secret, which would destroy our ability to DCHECK
on initialization before they request a one-time randomized trial.

I would suggest keeping the interface as-is, but as I said, I am willing to be
overridden.

[jar (doing other things), 2011/04/29 00:57:11]

I'm not sold on your arguments.  To be specific, for your two arguments:

a) "[enable] ...right before you create any one-time randomized trials...": 
This makes little sense to me, because I wouldn't want various users of this
service, presumably each residing all over creation in a binary, deciding on
*their* seed.  If we went in a lazy direction, we'd want some central service to
select the seed... you can't leave it to be decided by multiple consumers. 
...which again points back to doing something around construction time.

b) "[I don't like overloading initialization state with the presence of a
low-entropy seed]"  This seems motivated by a hypothentical future user that
doesn't want to use a seed, and doesn't want this functionality.  I don't think
we should cater to a fictional user that doesn't use the functionality.  ...but
avoiding the overloading is reasonable.... so... A boolean slot to indicate that
a seed was provided, or not provided, would be fine.  That would provide
something to to DCHECK on, and wouldn't overload the meaning of the seed. 

It seems a waste to provide a whole separate bool to indicate if there is such a
seed argument, and certainly a zero-length string might be a hint... but then
you could argue again about overloading the meaning of the string. I'm not as
concerned about that difference, as it still seems to focus construction details
at the singular point of time. 

Bottom line: piecemeal construction makes much more sense when there really are
a variety of use cases.  Without such real world use cases, a simple clear
construct-and-you-are-ready-to-roll interface is generally cleaner.

<sigh> That said... I didn't see a super-straight-forward way to call the
constructor with an argument (i.e., call a non-default constructor).  Currently
the code seems to cheat(?) and just put an instance definition in a class, and
count on the default (no-arg) constructor.  Most (all?) of the other
initializations also have this form :-/.  It could be that this initialization
will be different... and will pass an argument to the constructor.  It could be
the seed string, or it could be an instance of something (metrics services?)
that supports some GetUserSpecificSeed() interface.  The less code we need to
land in browser_main, and the less insight into this exchange, the better.

On 2011/04/28 01:03:50, Jói wrote:

[Jói, 2011/05/02 18:55:03]

I've switched to having client_id as an argument to FieldTrialList and using a
scoped_ptr<FieldTrialList> in BrowserMainParts to let us defer initialization of
the object until we have the parameter available.

Just to clarify on the former approach that is now gone, it had DCHECKs in place
to ensure you did not initialize multiple times, and that you initialized before
using a one-time randomized trial, so there was no risk of misuse.

Switching to constructor initialization uncovered a bug, I wasn't reflecting the
client_id over to the renderer process. So there's something to be said for
construction-time initialization :)

+
+  // Returns true if you can call |FieldTrial::UseOneTimeRandomization()|
+  // without error, i.e. if |EnableOneTimeRandomization()| has been called.
+  static bool IsOneTimeRandomizationEnabled();
+
+  // Returns an opaque, diverse ID for this client that does not change
+  // between sessions.
+  //
+  // Returns the empty string if |EnableOneTimeRandomization()| has not
+  // been called.
+  static const std::string& client_id();
+
  private:
   // A map from FieldTrial names to the actual instances.
   typedef std::map<std::string, FieldTrial*> RegistrationList;
 
   // Helper function should be called only while holding lock_.
   FieldTrial* PreLockedFind(const std::string& name);
 
   static FieldTrialList* global_;  // The singleton of this class.
 
   // This will tell us if there is an attempt to register a field trial without
   // creating the FieldTrialList. This is not an error, unless a FieldTrialList
   // is created after that.
   static bool register_without_global_;
 
-  // A helper value made availabel to users, that shows when the FieldTrialList
+  // A helper value made available to users, that shows when the FieldTrialList
   // was initialized.  Note that this is a singleton instance, and hence is a
   // good approximation to the start of the process.
   TimeTicks application_start_time_;
 
   // Lock for access to registered_.
   base::Lock lock_;
   RegistrationList registered_;
 
+  // An opaque, diverse ID for this client that does not change
+  // between sessions, or the empty string if not initialized.
+  std::string client_id_;
+
   DISALLOW_COPY_AND_ASSIGN(FieldTrialList);
 };
 
 }  // namespace base
 
 #endif  // BASE_METRICS_FIELD_TRIAL_H_