Clustered search head configurations synchronization with bloom filter

• US 10,606,810 B2
• Filed: 01/09/2017
• Issued: 03/31/2020
• Est. Priority Date: 01/09/2017
• Status: Active Grant

• Current Assignee: Splunk Inc.
• Original Assignee: Splunk Inc.
• Inventors: Xu, Yuan
• Primary Examiner(s): Khong, Alexander
• Application Number:
  US15/401,427
• Publication Number:
  US 20180196864A1
• Time in Patent Office: 1,177 Days
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/188 Virtual file systems

Abstract

Embodiments of the present disclosure provide techniques for efficiently and accurately performing propagation of search-head specific configuration customizations across multiple individual configuration files of search heads of a cluster for a consistent user experience. The cluster of search heads may be synchronized such that the search heads operate to receive the configuration or knowledge object customizations from one or more clients from a central or lead search head. To reduce the amount of data that is transferred during propagation, the list of configuration or knowledge object customizations maintained in each search head is filtered from the list of the lead search head until a divergence point is determined. Once determined and communicated to the lead search head, the lead search head sends the configuration and knowledge object customization data that is absent from the internal list of the member search head.

Claims

1. A method comprising:

accessing, by one or more processing devices corresponding to a first search head of a cluster comprising a plurality of search heads of a data aggregation and analysis system, a first list of knowledge object customizations corresponding to the first search head;

generating a digest of the first list of knowledge object customizations corresponding to the first search head, wherein the digest is a reduced size representation of the first list of knowledge object customizations;

propagating the digest to a second search head of the cluster;

receiving an indication of a first divergence point determined between the first list of knowledge object customizations and a second list of knowledge object customizations corresponding to the second search head based on a comparison of the digest with the second list of knowledge object customizations, the first divergence point corresponding to a first position in the first list of knowledge object customizations where the first list of knowledge object customizations diverges from the second list of knowledge object customizations; and

sending a first set of knowledge object customizations from the first list of knowledge object customizations to the second search head, wherein the first set of knowledge object customizations comprises at least one knowledge object customization from the first list of knowledge object customizations relative to a position in the first list of knowledge object customizations corresponding to the first divergence point.

2. The method of claim 1, wherein the first list of knowledge object customizations comprises a journal of knowledge object customizations locally stored with respect to at least one processing device of the one or more processing devices corresponding to the first search head.

3. The method of claim 1, wherein the second list of knowledge object customizations corresponding to the second search head comprises a journal of knowledge object customizations locally stored with respect to at least one processing device of one or more processing devices corresponding to the second search head.

4. The method of claim 1, wherein the generating the digest comprises applying a Bloom filter to the first list of knowledge object customizations.

5. The method of claim 1, wherein the first list of knowledge object customizations comprises a list of global unique identifiers (GUIDs), each knowledge object customization of the first list of knowledge object customizations corresponding specifically to a respective GUID of the list of GUIDs.

6. The method of claim 1, wherein the digest comprises a bitmask generated by applying a Bloom filter to a list of global unique identifiers (GUID) values corresponding to the first list of knowledge object customizations.

7. The method of claim 1, wherein the sending the first set of knowledge object customizations comprises:

sending a first set of knowledge object customizations comprising at least one knowledge object customization positioned in the first list of knowledge object customizations relative to the first divergence point to the second search head; and

updating, in the second search head, the second list of knowledge object customizations with the first set of knowledge object customizations.

8. The method of claim 1, further comprising:

propagating the digest to a third search head of the cluster;

receiving an indication of a second divergence point determined between the digest and a third list of knowledge object customizations corresponding to the third search head, the second divergence point corresponding to a second position in the digest; and

sending a second set of knowledge object customizations from the first list of knowledge object customizations to the third search head, wherein the second set of knowledge object customizations comprises knowledge object customizations from the first list of configurations after a position in the first list of configurations corresponding to the second divergence point.

9. The method of claim 1, wherein the generating the digest comprises:

receiving an update list of knowledge object customizations from the second search head, the update list comprising at least one knowledge object customization from the second list of knowledge object customizations absent from the digest;

comparing a current size of the digest with a pre-determined threshold size;

updating the digest and the first list of knowledge object customizations to include the knowledge object customizations comprised in the update list when the current size of the digest is less than a pre-determined threshold size; and

generating a second digest based on the update list when the size of the digest meets or exceeds the pre-determined threshold size.

10. The method of claim 1, wherein the first divergence point is determined by:

applying one or more hash functions to a first global unique identifier (GUID) corresponding to a first knowledge object customization of the second list of knowledge object customizations to determine a corresponding one or more hash values;

referencing one or more addresses in the digest corresponding to the one or more hash values to determine one or more corresponding address values, wherein the one or more address values are indicative of the presence or absence of the first GUID in the digest;

determining a presence or absence of the first GUID in the digest based on the one or more address values; and

calculating the divergence point to be a position in the second list of knowledge object customizations corresponding to a position of the first GUID if the first GUID is absent from the digest.

11. The method of claim 1, wherein the first divergence point is determined by:

applying, to a set of global unique identifiers (GUIDs) corresponding to a pre-determined number of knowledge object customizations of the second list of knowledge object customizations, one or more hash functions to each of the set of GUIDs to determine a corresponding one or more hash values for each GUID of the set of GUIDs;

referencing one or more addresses in the digest corresponding to the one or more hash values to determine a corresponding one or more address values for each GUID of the set of GUIDs, wherein the one or more address values is indicative of the presence or absence of the corresponding GUID in the digest;

determining a presence of each GUID of the set of GUIDs in the digest based on the one or more address values;

iteratively repeating the applying, the referencing, and the determining for remaining GUIDs in the set of GUIDs until an absence of a GUID in the digest is determined; and

when a GUID is determined to be absent in the digest, identifying the divergence point as a position in the second list of knowledge object customizations corresponding to the GUID of the set of GUIDs that is absent from the digest.

12. The method of claim 1, wherein the first divergence point is determined by:

applying, to a set of global unique identifiers (GUIDs) comprising a sequence of consecutive GUIDs corresponding to a pre-determined number of knowledge object customizations of the second list of knowledge object customizations, one or more hash functions to each of the set of GUIDs to determine a corresponding one or more hash values for each GUID of the set of GUIDs;

referencing one or more addresses in the digest corresponding to the one or more hash values to determine a corresponding one or more address values, wherein the one or more address values is indicative of the presence or absence of the corresponding GUID in the digest;

determining a presence of each GUID of the set of GUIDs in the digest based on the one or more address values;

iteratively repeating the applying, the referencing, and the determining for remaining GUIDs in the set of GUIDs until an absence of a GUID in the digest is determined; and

when a GUID is determined to be absent in the digest, comparing the set of GUIDs to a corresponding sequence of GUIDs in the first list of knowledge object customizations to identify the divergence point,

wherein the iteratively repeating comprises, for each iteration, adding a GUID corresponding to a next knowledge object customization of the second list of knowledge object customizations to the set of GUIDs and performing the iteratively repeating for the sequence of consecutive GUIDs.

13. The method of claim 1, wherein the first divergence point is determined by:

applying, to a set of global unique identifiers (GUIDs) comprising a sequence of consecutive GUIDs corresponding to a pre-determined number of knowledge object customizations of the second list of knowledge object customizations, one or more hash functions to each of the set of GUIDs to determine a corresponding one or more hash values for each GUID of the set of GUIDs;

referencing one or more addresses in the digest corresponding to the one or more hash values to determine a corresponding one or more address values, wherein the one or more address values is indicative of the presence or absence of the corresponding GUID in the digest;

determining a presence of each GUID of the set of GUIDs in the digest based on the one or more address values;

removing the first GUID in the set of GUIDS and appending the set of GUIDs with a GUID corresponding to a next knowledge object customization of the second list of knowledge object customizations when all GUIDS in the set of GUIDs are determined to be present in the digest;

iteratively repeating the applying, the referencing, and the determining for remaining GUIDs in the one or more GUIDs until an absence of a GUID in the digest is determined; and

when a GUID is determined to be absent in the digest, comparing the set of GUIDs to a corresponding sequence of GUIDs in the first list of knowledge object customizations to identify the divergence point.

14. The method of claim 1, wherein the first divergence point is determined by:

applying, to a set of global unique identifiers (GUIDs) comprising a sequence of consecutive GUIDs corresponding to a pre-determined number of knowledge object customizations of the second list of knowledge object customizations, one or more hash functions to each of the set of GUIDs to determine a corresponding one or more hash values for each GUID of the set of GUIDs;

referencing one or more addresses in the digest corresponding to the one or more hash values to determine a corresponding one or more address values, wherein the one or more address values is indicative of the presence or absence of the corresponding GUID in the digest;

determining a presence of all GUIDs of the set of GUIDs in the digest based on the one or more address values;

removing the first GUID in the set of GUIDs and appending the set of GUIDs with a GUID corresponding to a next knowledge object customization of the second list of knowledge object customizations when all GUIDS in the set of GUIDs are present in the digest;

iteratively repeating the applying, the referencing, and the determining for remaining GUIDs in the one or more GUIDs until an absence of a GUID in the digest is determined; and

when a GUID is determined to be absent in the digest, comparing the set of GUIDs to a corresponding sequence of GUIDs in the first list of knowledge object customizations to identify the divergence point,

wherein a size of the set of GUIDs is configurable.

15. The method of claim 1, wherein the digest comprises a one dimensional array of values, the one dimensional array having a configurable size.

16. The method of claim 1, wherein the data aggregation and analysis system employs a late-binding schema for searching data.

17. A system comprising:

a local data store comprising a first list of knowledge object customizations received from at least one client computing device; and

a processing device coupled with the local data store, the processing device being configured to;

access, by a first search head of a cluster comprising a plurality of search heads, the first list of knowledge object customizations from the local data store;

generate a digest of the first list of knowledge object customizations corresponding to the first search head, the digest being stored in the local data store, wherein the digest is a reduced size representation of the first list of knowledge object customizations;

propagate the digest to a second search head of the cluster; and

receive an indication of a first divergence point determined between the first list of knowledge object customizations and a second list of knowledge object customizations corresponding to the second search head based on a comparison of the digest and the second list of knowledge object customizations, the first divergence point corresponding to a first position in the first list of knowledge object customizations where the first list of knowledge object customizations diverges from the second list of knowledge object customizations; and

send a first set of knowledge object customizations from the first list of knowledge object customizations to the second search head, wherein the first set of knowledge object customizations comprises at least one knowledge object customization from the first list of knowledge object customizations relative to a position in the first list of knowledge object customizations corresponding to the first divergence point.

18. The system of claim 17, wherein the first list of knowledge object customizations corresponding to the first search head comprises a journal of knowledge object customizations stored in the local data store corresponding to the first search head.

19. The system of claim 17, wherein the processing device is configured to generate the digest of the first list of knowledge object customizations by applying a Bloom filter to the first list of knowledge object customizations in the local data store.

20. The system of claim 17, wherein the first list of knowledge object customizations comprises a list of global unique identifiers (GUIDs), each knowledge object customization of the first list of knowledge object customizations corresponding specifically to a respective GUID of the list of GUIDs.

21. The system of claim 17, wherein the digest comprises a bitmask generated by the processing device by applying a Bloom filter to a list of global unique identifiers (GUID) values corresponding to the first list of knowledge object customizations.

22. The system of claim 17, wherein the processor is configured to send the first set of knowledge object customizations by sending at least one knowledge object customization positioned in the first list of knowledge object customizations after the first divergence point to the second search head,

wherein the second list of knowledge object customizations is updated in the second search head based on the first set of knowledge object customizations.

23. The system of claim 17, wherein the processing device is further configured to:

propagate the digest to a third search head of the cluster;

receive an indication of a second divergence point determined between the digest and a third list of knowledge object customizations corresponding to the third search head, the second divergence point corresponding to a second position in the digest; and

send a second set of knowledge object customizations from the first list of knowledge object customizations to the third search head, wherein the second set of knowledge object customizations comprises knowledge object customizations from the first list of configurations after a position in the first list of configurations corresponding to the second divergence point.

24. The system of claim 17, wherein the processing device is further configured to:

receive an update list of knowledge object customizations from the second search head, the update list comprising at least one knowledge object customization from the second list of knowledge object customizations absent from the digest;

compare a current size of the digest with a pre-determined threshold size;

update the digest and the first list of knowledge object customizations to include the knowledge object customizations comprised in the update list when the current size of the digest is less than a pre-determined threshold size; and

generate a second digest based on the update list when the size of the digest meets or exceeds the pre-determined threshold size.

25. The system of claim 17, wherein the first divergence point is determined by:

applying, to a set of global unique identifiers (GUIDs) corresponding to a pre-determined number of knowledge object customizations of the second list of knowledge object customizations, one or more hash functions to each of the set of GUIDs to determine a corresponding one or more hash values for each GUID of the set of GUIDs;

referencing one or more addresses in the digest corresponding to the one or more hash values to determine a corresponding one or more address values, wherein the one or more address values is indicative of the presence or absence of the corresponding GUID in the digest;

determining a presence or absence of each GUID of the set of GUIDs in the digest based on the one or more address values;

iteratively repeating the applying, the referencing, and the determining for remaining GUIDs in the set of GUIDs until an absence of a GUID in the digest is determined; and

when a GUID is determined to be absent in the digest, identifying the divergence point as a position in the second list of knowledge object customizations corresponding to the GUID of the set of GUIDs that is absent from the digest.

26. The system of claim 17, wherein the first divergence point is determined by:

applying, to a set of global unique identifiers (GUIDs) corresponding to a pre-determined number of knowledge object customizations of the second list of knowledge object customizations, one or more hash functions to each of the set of GUIDs to determine a corresponding one or more hash values for each GUID of the set of GUIDs;

referencing one or more addresses in the digest corresponding to the one or more hash values to determine a corresponding one or more address values, wherein the one or more address values is indicative of the presence or absence of the corresponding GUID in the digest;

determining a presence or absence of each GUID of the set of GUIDs in the digest based on the one or more address values;

iteratively repeating the applying, the referencing, and the determining for remaining GUIDs in the set of GUIDs until an absence of a GUID in the digest is determined; and

when a GUID is determined to be absent in the digest, comparing the set of GUIDs to a corresponding sequence of GUIDs in the first list of knowledge object customizations to identify the divergence point,

wherein the iteratively repeating comprises, for each iteration, adding a GUID corresponding to a next knowledge object customization of the second list of knowledge object customizations to the set of GUIDs and performing the iteratively repeating for the sequence of consecutive GUIDs.

27. The system of claim 17, wherein the first divergence point is determined by:

applying, to a set of global unique identifiers (GUIDs) corresponding to a pre-determined number of knowledge object customizations of the second list of knowledge object customizations, one or more hash functions to each of the set of GUIDs to determine a corresponding one or more hash values for each GUID of the set of GUIDs;

referencing one or more addresses in the digest corresponding to the one or more hash values to determine a corresponding one or more address values, wherein the one or more address values is indicative of the presence or absence of the corresponding GUID in the digest;

determining a presence or absence of all GUIDs of the set of GUIDs in the digest based on the one or more address values;

removing the first GUID in the set of GUIDS and appending the set of GUIDs with a GUID corresponding to a next knowledge object customization of the second list of knowledge object customizations when all GUIDS in the set of GUIDs are determined to be present in the digest;

iteratively repeating the applying, the referencing, and the determining for remaining GUIDs in the one or more GUIDs until an absence of a GUID in the digest is determined; and

when a GUID is determined to be absent in the digest, comparing the set of GUIDs to a corresponding sequence of GUIDs in the first list of knowledge object customizations to identify the divergence point.

28. A non-transitory computer readable medium having instructions stored thereon which, when executed by a processing device, causes the processing device to perform configuration propagation, the instructions comprising:

instructions to access, by one or more processing devices corresponding to a first search head of a cluster comprising a plurality of search heads of a data aggregation and analysis system, a first list of knowledge object customizations corresponding to the first search head;

instructions to generate a digest of the first list of knowledge object customizations corresponding to the first search head, wherein the digest is a reduced size representation of the first list of knowledge object customizations;

instructions to propagate the digest to a second search head of the cluster;

instructions to receive an indication of a first divergence point determined between the first list of knowledge object customizations and a second list of knowledge object customizations corresponding to the second search head based on a comparison of the digest and the second list of knowledge object customizations, the first divergence point corresponding to a first position in the first list of knowledge object customizations where the first list of knowledge object customizations diverges from the second list of knowledge object customizations; and

instructions to send a first set of knowledge object customizations from the first list of knowledge object customizations to the second search head, wherein the first set of knowledge object customizations comprises at least one knowledge object customization from the first list of knowledge object customizations relative to a position in the first list of knowledge object customizations corresponding to the first divergence point.

29. The non-transitory computer readable medium of claim 28, further comprising:

instructions to receive an update list of knowledge object customizations from the second search head, the update list comprising at least one knowledge object customization from the second list of knowledge object customizations absent from the digest;

instructions to compare a current size of the digest with a pre-determined threshold size;

instructions to update the digest and the first list of knowledge object customizations to include the knowledge object customizations comprised in the update list when the current size of the digest is less than a pre-determined threshold size; and

instructions to generate a second digest based on the update list when the size of the digest meets or exceeds the pre-determined threshold size.

30. The non-transitory computer readable medium of claim 28, further comprising:

instructions to apply, to a set of global unique identifiers (GUIDs) corresponding to a pre-determined number of knowledge object customizations of the second list of knowledge object customizations, one or more hash functions to each of the set of GUIDs to determine a corresponding one or more hash values for each GUID of the set of GUIDs;

instructions to reference one or more addresses in the digest corresponding to the one or more hash values to determine a corresponding one or more address values, wherein the one or more address values is indicative of the presence or absence of the corresponding GUID in the digest;

instructions to determine a presence or absence of all GUIDs of the set of GUIDs in the digest based on the one or more address values;

instructions to iteratively repeat the applying, the referencing, and the determining for remaining GUIDs in the set of GUIDs until an absence of a GUID in the digest is determined; and

instructions to compare, when a GUID is determined to be absent in the digest, the set of GUIDs to a corresponding sequence of GUIDs in the first list of knowledge object customizations to identify the divergence point,

wherein the instructions to iteratively repeat comprises, instructions to add, for each iteration, a GUID corresponding to a next knowledge object customization of the second list of knowledge object customizations to the set of GUIDs and instructions to perform the iteratively repeating for the sequence of consecutive GUIDs.