Dynamic device clustering

• US 10,353,803 B2
• Filed: 08/21/2017
• Issued: 07/16/2019
• Est. Priority Date: 08/21/2017
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Lee, Eun Chang, Li, Xun, Rangarajan, Kumar, Magruder, Michael McKenzie, Mi, Zheng
• Primary Examiner(s): Rivera, Anibal
• Application Number:
  US15/682,268
• Publication Number:
  US 20190057019A1
• Time in Patent Office: 694 Days
• CPC Class Codes: G06F 11/2289 by configuration test
• CPC Class Codes: G06F 11/3414 Workload generation, e.g. scripts, playback
• CPC Class Codes: G06F 11/3419 by assessing time
• CPC Class Codes: G06F 11/3495 for systems
• CPC Class Codes: G06F 11/3664 Environments for testing or debugging software
• CPC Class Codes: G06F 11/3668 Software testing software testing in telephone exchanges H04M3/242, testing of hardware G06F11/22
• CPC Class Codes: G06F 16/437 Administration of user profiles, e.g. generation, initialisation, adaptation, distribution
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: G06F 9/5077 Logical partitioning of resources; Management or configuration of virtualized resources specific details on emulation or internal functioning of virtual machines G06F9/455

Abstract

A cluster of devices can be identified where results from executing a test by any cluster devices can be considered as being from the same device. Thus, instead of waiting for a single device to produce comparable results, multiple devices from the same cluster can simultaneously perform the test and obtain the needed set of test results more quickly. The technology can identify clusters of devices that are all similar to a primary cluster device. A device pair can be considered similar when (1) a mean each of a set of test results from each device are within a first threshold of each other, (2) a measurement of the consistency of each test result set are within a second threshold of each other, and (3) a measurement of the consistency of a combination of the test results sets is between the consistency measurements of the individual test result sets.

Claims

1. A method for identifying a cluster of devices, the method comprising:

selecting a set of candidate devices;

receiving a procedure executable on each of the candidate devices;

causing two or more of the candidate devices to perform the procedure, wherein each of the two or more of the candidate devices produces logged results in response to performing the procedure;

selecting a particular pair of candidate devices of the two or more candidate devices;

computing a delta between the logged results produced by each candidate device of the particular pair of candidate devices;

based on determining that the delta is below a delta threshold, identifying the particular pair of candidate devices as similar candidate devices; and

identifying the cluster of devices as the set of devices that includes both;

a primary device of the candidate devices that has been most often identified as similar to other devices of the candidate devices, and

a group of one or more devices including devices that have been determined to be similar to the primary device.

2. The method of claim 1, wherein the causing the two or more of the candidate devices to perform the procedure comprises causing the two or more of the candidate devices to each perform the procedure multiple times, wherein the logged results that each of the two or more of the candidate devices produce include a result from each of the multiple performances of the procedure.

3. The method of claim 2, wherein computing the delta between the logged results comprises:

computing a mean of the results from each of the two or more of the candidate devices; and

computing the delta as the difference between the means of the results for each device of the particular pair of candidate devices.

4. The method of claim 2, further comprising:

for a particular set of the results from the multiple performances of the procedure by each of the particular pair of candidate devices, computing a consistency value for the particular set of results by;

computing a difference between multiple pairs of results from the particular set of results;

converting each difference to a percentage; and

computing a consistency value for the converted percentage differences;

wherein the identifying the particular pair of candidate devices as similar candidate devices is further based on determining that the consistency value, computed for each of the particular set of results corresponding to each device of the particular pair of candidate devices, are within a threshold difference from each other.

5. The method of claim 4, wherein computing the consistency value comprises computing the P95 percent-point function for the converted percentage differences.

6. The method of claim 4, wherein the set of results from the multiple performances of the procedure by a first device of the particular pair of candidate devices is a first set of results, wherein the set of results from the multiple performances of the procedure by a second device of the particular pair of candidate devices is a second set of results, and wherein the method further comprises:

selecting a third set of results comprising at least one result from each of the first set of results and second set of results;

computing a consistency value for the third set of results by;

computing a difference value between multiple pairs of results from the third set of results;

converting each difference value to a percentage value; and

computing a consistency outcome for the converted percentage difference values;

wherein the identifying the particular pair of candidate devices as similar candidate devices is further based on determining that the consistency outcome is between the consistency values computed for the first set of results and for the second set of results.

7. The method of claim 1, wherein the logged results comprise one or more of data recording memory usage during the performance of the procedure, CPU cycles used during the performance of the procedure, or a time expired used during the performance of the procedure.

8. The method of claim 1, wherein the selecting the set of candidate devices is performed by selecting devices that all have the same hardware and software configuration.

9. The method of claim 1, wherein the cluster of devices is a first cluster of devices and the procedure is a first procedure;

and

wherein the method further comprises identifying a second cluster of devices for a second procedure, wherein the second cluster of devices includes at least one device that is in the first cluster of devices and at least one device that is not in the first cluster of devices.

10. The method of claim 1, wherein the selecting the set of candidate devices is performed by selecting devices, from a pool of available devices, based on an amount of processing each selected device has performed within a specified time window.

11. The method of claim 1, wherein the selecting the particular pair of candidate devices comprises selecting all possible pairs of candidate devices among the candidate devices;

wherein the computing the delta is performed for all the identified pairs of candidate devices; and

wherein each pair of identified candidate devices is analyzed for being identified as similar based on whether the corresponding delta is below the delta threshold.

12. The method of claim 1, wherein the devices in the identified cluster of devices are used to perform further iterations of the procedure such that results from each iteration of the procedure that the devices in the cluster of devices perform are treated as results from the same device.

13. The method of claim 12, wherein the procedure is a procedure to test a build of software and wherein the further iterations of the procedure are performed by first installing a new build of the software on each device in the cluster of devices before performing the further iterations of the procedure.

14. The method of claim 12, wherein devices within the cluster of devices are selected to perform the further iterations of the procedure based on current load measures of the devices of the cluster of devices.

15. A computer-readable storage medium storing instructions that, when executed by a computing system, cause the computing system to perform operations for identifying a cluster of devices, the operations comprising:

causing two or more candidate devices to perform a procedure, wherein each of the two or more of the candidate devices produces logged results in response to performing the procedure;

selecting multiple pairs of the two or more candidate devices;

for each particular pair of candidate devices, of the multiple pairs;

computing a delta between the logged results produced by each candidate devices of the particular pair of candidate devices; and

performing a classification of the particular pair of candidate devices that excludes the particular pair of candidate devices from being identified as similar candidate devices when the delta is above a delta threshold; and

identifying the cluster of devices as the set of devices that includes both;

a primary device of the candidate devices that has been most often identified as similar to other devices of the candidate devices, and

a group of one or more devices including devices that have been determined to be similar to the primary device.

16. The computer-readable storage medium of claim 15, wherein the causing the two or more of the candidate devices to perform the procedure comprises causing the two or more of the candidate devices to each perform the procedure multiple times, wherein the logged results that each of the two or more of the candidate devices produce include a result from each of the multiple performances of the procedure;

wherein the operations further comprise, for a list of the results from the multiple performances of the procedure by each devices of the particular pair of candidate devices, computing a consistency value for the list of results by;

computing a difference between each pair of proximate results on the list of results;

converting each difference to a percentage; and

computing a consistency value for the converted list of percentages; and

wherein the classification of the particular pair of candidate devices further excludes the particular pair of candidate devices from being identified as similar candidate devices when the consistency values, computed for each of the lists of results corresponding to each device of the particular pair of candidate devices, are not within a threshold difference from each other.

17. The computer-readable storage medium of claim 15, wherein the devices in the identified cluster of devices are used to perform further iterations of the procedure such that results from each iteration of the procedure that the devices in the cluster of devices performs are treated as results from the same device.

18. A system for identifying a cluster of devices, the system comprising:

one or more processors; and

a memory storing instructions that, when executed by the system, cause the system to perform operations comprising;

receiving a procedure executable on each of a set of candidate devices;

causing two or more of the candidate devices to perform the procedure, wherein each of the two or more of the candidate devices produces logged results in response to performing the procedure;

selecting a particular pair of candidate devices of the two or more candidate devices;

computing a delta between the logged results produced by each candidate devices of the particular pair of candidate devices;

based on determining that the delta is below a delta threshold, identifying the particular pair of candidate devices as similar candidate devices; and

identifying the cluster of devices based on pairs of the candidate devices that have been identified as similar.

19. The system of claim 18, wherein the causing the two or more of the candidate devices to perform the procedure comprises causing the two or more of the candidate devices to each perform the procedure multiple times, wherein the logged results that each of the two or more of the candidate devices produce include a result from each of the multiple performances of the procedure;

and

wherein computing the delta between the logged results comprises;

computing a mean of the results from each of the two or more of the candidate devices; and

computing the delta as the difference between the means of the results for each device of particular pair of candidate devices.

20. The system of claim 18, wherein the devices in the identified cluster of devices are used to perform further iterations of the procedure such that results from each iteration of the procedure that the devices in the cluster of devices perform are treated as results from the same device.