Record compression using incremental reverse templating

In one embodiment, a method for compression is disclosed, including receiving source data, creating at least one template based upon common data, and creating a compressed record including a reference to the at least one template and a template delta that represents a difference between the at least one template and source data.

TECHNICAL FIELD

The present disclosure relates generally to data compression and network management.

BACKGROUND

Data compression is desirable in many situations for efficiently storing, providing, maintaining, and/or transferring data. In systems which maintain large data sets, eliminating data redundancy is paramount to efficiency. The redundancy increases storage requirements and has a detrimental impact on read/write performance because caches become less efficient. In environments where millions of large records have to be maintained, this presents a significant challenge. Furthermore, in some situations, it is necessary to compress data incrementally where records are added one by one over the life cycle of the system.

In one case, network management systems are required to collect large amounts of data from devices. When centrally managing home networks, this may be millions of devices. This data may include configuration settings, live performance and fault data, device logs, etc. For example, a service provider may desire to actively manage consumer home devices and backup entire device configuration settings several times a day in order to offer customers a restore function or to handle seamless replacement of devices while preserving user-settings. The data that needs to be stored is often highly redundant across millions of devices. Compressing individual records in isolation is not efficient because this does not take advantage of similarities across data records.

In another case, designated servers of a distributed management system may generate management policy for devices based on templates and distribute the generated policy instructions to enforcement elements. It may not be desirable to distribute information about some common templates the policy is derived from across the system, but rather it may be preferable for enforcement elements to be able to receive a complete set of instructions for each client and compress data incrementally, which provides for a more loosely coupled system design.

DESCRIPTION OF EXAMPLE EMBODIMENTS

In accordance with an embodiment of the present invention, an apparatus is provided including an interface operable to receive a plurality of source data and a processor operable to create at least one template based upon common data from the plurality of source data. The processor is also operable to create a compressed record including a reference to at least one template and a template delta that represents a difference between the template and one of the plurality of source data.

In accordance with another embodiment of the present invention, logic encoded in one or more tangible media for execution is provided, the logic when executed being operable to receive a plurality of source data, create at least one template, and create a compressed record as described above.

In accordance with another embodiment of the present invention, a method is provided, including receiving a plurality of source data, creating at least one template, and creating a compressed record as described above.

Table 1 below provides a description of terms applicable throughout this document.

TABLE 1TermDescriptionSource RecordAn original record with uncompressed data thatis being added to the system.Source DataThe uncompressed data of the Source Record.Source DataThe amount of storage space required to storeSizeSource Data.Stored RecordThe record with Compressed Data stored in thedatabase.CompressedA representation of Stored Record Data afterDatacompression.TemplateA persistent collection of re-usable Templates.CatalogTemplateA set of common data re-used by a number ofStored Records.TemplateA unique identifier used to represent aIdentifierspecific Template.Template DataThe data represented by the Template.RetiredA Template, which is no longer used forTemplatecompressing new Source Records. It can stillbe referenced and used by existing StoredRecords.ActiveAny non-Retired Template. The most efficientTemplateActive Template is chosen during compression.PopularityA value representing frequency of theMetricrespective Template used in Stored Records.This could be a simple reference counter orsome approximate metric which does not requiretransactional updates in one example.TemplateRepresentation of a data difference betweenDeltaSource Data and Template Data.TemplateThe amount of storage space required to storeDelta SizeTemplate Delta.Match RatioA metric representing closeness of match of agiven Source Record to a given Template. Itcan be calculated as follows: (Source DataSize − Template Delta Size)/Source Data Size.Example: If Source Data matches Templatecompletely, the ratio is 1. The larger theTemplate Delta for a given Source Data, thelower the Match Ratio for this record.Average MatchA metric for representing the average of MatchRatioRatios for all Stored Records using a givenTemplate. It can be calculated as a sum ofMatch Ratios for the Template divided by numberof Stored Records using the Template.RelativeA metric representing both popularity andMatch Ratioefficiency of a given Template. In otherwords, it is a measurement of a Template'scontribution to the Total Match Ratio. It maybe calculated as Average Match Ratio weightedby the Popularity Matrix.Total MatchA measure of total compression provided by theRatiosystem for all Stored Records. It can becalculated as a weighted average of AverageMatch Ratios of all Active Templates. Theweight is determined by the Popularity Metricof the Template.Example: Suppose we have 2 Active Templates.First template is used by 5 records withAverage Match Ratio of 1 (direct match).Second template is used by 5 records withAverage Match Ratio of 0.8. Then, the TotalMatch Ratio is 0.9.

Dictionary-based algorithms for data compression are known. Many of these types of algorithms rely on building a dictionary of reusable blocks which are repeated within a current data set. The various algorithm variations compete in their approach towards finding the most optimal repeatable blocks in the most efficient manner. However, dictionary-based algorithms are not well suited for a situation where data records are added incrementally and concurrently. Dictionary-based algorithms find many small repeatable blocks in a current data set as opposed to a major pattern, like a form template, that could be common across many different data records over time. When many data records are added over time, as in the case of a database, dictionary-based algorithms have been previously used on individual records, rather than incrementally updating the dictionary as new records appear based upon a set of records.

Dictionary-based algorithms also typically take a very low-level (general) approach to data compression without taking into account, for example, that order of certain elements may not be significant in a given domain. In essence, they do binary comparisons without assuming much about how the data could be specialized in a given domain. For example, if a device configuration is represented as name-value pairs, the order may not matter, yet standard compression algorithms will treat such data as different if the same two name-value pairs appear in different order.

Another type of data compression algorithm is known as delta-coding. These algorithms are often used in compressing streamed data where a subsequent record has some natural relationship to a previous record. For example, in video this relationship is based on timing. Each frame can have a context of a previous frame by simply keeping the last frame in memory buffer. For every portion of data, these algorithms attempt to describe the portion using deltas from the previous portion. MPEG is an example of such an algorithm, which takes advantage of incremental changes of picture from frame to frame. However, delta-coding algorithms are not well suited for the case of stored records, in which records may be unrelated and can be independently added and removed in any order. Making one record depend on a previous unrelated record is impractical and also increases the retrieval overhead.

In accordance with embodiments of the present disclosure, an advantageous system, method, and logic encoded in one or more tangible media for execution are provided which detect similarities among records as they are added into a system substantially without an overhead of buffering records or retrieving a large number of old records during compression. A “reverse templating” algorithm for efficiently compressing data incrementally is disclosed, being particularly advantageous for compressing data with a high-level of redundancy and including certain patterns or templates. The algorithm dynamically detects or generates an applicable set of templates in an environment of data from different types of devices or different types of services and uses the templates without re-reading previously stored records or buffering a large number of records. The compressed data references one template and describes the delta from the template if any. The algorithm reduces the amount of total delta information stored in the system, while minimizing the number of templates used for compression in order to maintain appropriate speed of compression.

Referring toFIG. 1, an example system100for data compression and/or management is illustrated. System100includes a data compression computer102, devices106, and a network104through which computer102and devices106may communicate.

In one example, computer102executes an algorithm that finds the most applicable template for a given data record out of a set of automatically derived templates. Templates may be derived from detected common data within source records from devices106. The compressed data references one template (e.g., via a template identifier) and describes a delta from the template if any. A delta describes the difference of source data from the template and can itself be further compressed using legacy compression algorithms. The templates are automatically and dynamically derived, managed, and re-evaluated as new records are added such that system target compression is achieved while the number of templates needed during compression is minimized. Old records need not be re-read. Templates which contribute most to compression efficiency remain in the system and are categorized as “active” while inefficient templates are “retired” in an un-intrusive way. In one embodiment, direct control over compression time used for a new record is provided by limiting the number of allowed active templates. Domain-specific algorithms may also be used to determine template delta. For certain domains where appropriate, elements within a record may be treated as an unordered set allowing for a higher rate of template matching.

In one example, computer102periodically obtains and maintains backup snapshots of configurations for a plurality of devices. These configurations can be represented as a set of parameter name-value pairs in a further example. Most of the configuration snapshot data will be identical for many devices, and some minor difference may exist where configurations differ to user-specific settings. No prior knowledge may be available regarding which parts of data may be redundant and which may vary.

Network104may include various networks such as a public switched telephone network (PSTN), an integrated services digital network (ISDN), a local area network (LAN), a wide area network (WAN), a metropolitan area network, and/or a wireless local area network (WLAN), that support standards such as Ethernet, wireless fidelity (WiFi), and/or Voice over Internet Protocol (VoIP). Other protocols for communication are also within the scope of the present invention. Communication network104may generally include any network capable of transmitting audio and/or video telecommunication signals, data, and/or messages, and may be implemented in any form of a wireless or wireline communication network.

Devices106may be various devices that communicate with network104, including but not limited to personal computers, PDAs, telephones, and consumer premises equipment such as modems, gateways, VoIP adaptors, and IPTV set top boxes. Devices106may communicate with network104via various forms of wireless or wireline communication protocols.

Referring now toFIG. 2in conjunction withFIG. 1, example data compression computer102is illustrated in more detail. Computer102includes a processor202operably coupled via a bus216to the following components: a template generator204, a template catalog storage206, a record storage208, a network interface210via an input/output port; a user interface212via an input/output port; and a memory214(e.g., SDRAM or flash memory) via a memory interface.

Processor202may be a microprocessor, controller, or any other suitable computing device or resource. Processor202may include a variety of processors (e.g., digital signal processors), conventional CPUs being applicable. When a source record is received at computer102, processor202may use system components to compress, store, and/or manage the data.

Template generator204may be any combination of hardware, software, and/or encoded logic, and is used to generate templates.

Template catalog storage206stores active and/or retired templates generated by template generator204. Template catalog storage206is a component that stores information in any applicable medium, such as a database.

Record storage208includes stored records after compression. Record storage208is a component that stores information in any applicable medium, such as a database.

Network interface210includes in one example, an adaptor for providing wired communications with a network, such as a LAN connector (e.g., a 10/100/1000 Base-T Ethernet port) via a MII interface, and/or a transmitter/receiver (transceiver) for providing wireless communications with a network and/or wireless device. Network interface210may communicate using any of various protocols known in the art for wireless or wired connectivity in one example.

User interface212is operably coupled to processor202and may include data input means, such as a keyboard, mouse, etc., and data display means, such as a display system. In one example, user interface212may include an alpha-numeric keypad and screen for entering or displaying compression parameters, such as target total match ratio, number of templates, and/or other information. Other types of user interfaces, such as touch screens, are within the scope of the present invention.

Memory214may include a variety of volatile or non-volatile memories, and in one example includes without limitation, magnetic media, optical media, random access memory (RAM), read-only memory (ROM), flash memory, removable media, or any other suitable local or remote memory component, or combination thereof. In one example, memory214may be used to store passwords, network and telecommunications programs, various protocols, and/or an operating system (OS).

It will be recognized by those of ordinary skill in the art that computer102may include any number of processors, storage, memory modules, and interfaces to accomplish the functionality and features described herein. Furthermore, computer components (e.g., processor202, template generator204, template catalog storage206, record storage208, and memory214) may be centrally located with respect to one another, or distributed throughout a network.

Furthermore, it should be understood that data is not limited to originating from devices, but may be from a system component, such as a process or subsystem on the same operating system, and that data may be transferred via mechanisms other than a network or network interface, such as by a direct local application library call. Accordingly, a data compression/management system need not be distributed in other embodiments. For example, an application generating weather reports based on sensors may store the reports in a database. The database can determine templates from the plurality of reports and store data more efficiently with the present invention.

FIG. 3illustrates a representation of an example source record302including source data304.

FIG. 4illustrates a representation of an example stored record310including compressed data312, a template identifier314, and a template delta316.

FIG. 5illustrates a representation of an example template320including identifier314, data322, a popularity metric324, and an average match ratio326.

FIG. 6illustrates a representation of example template delta316including missing tuples330, extra tuples332, and modified tuples334. In one embodiment, template delta316is represented as an unordered set of tuples (records). The tuple may, for example, contain a parameter name as unique identifier, and a parameter value or other data. In many domains, the order of tuples is not significant and an unordered set of tuples presents significant benefits in complexity of calculating the delta and match ratio. The source data is then represented using the unordered set of tuples in the same way. By comparing the set, the template delta is calculated, including lists of missing, extra, and/or modified tuples.

FIG. 7illustrates a representation of an example template catalog340including a total match ratio342, active templates344, and retired templates346. In one embodiment, only active templates are used during compression as distinguished from retired templates. Retired templates may continue to exist in the system for as long as they are referenced by stored data in one embodiment.

Referring now toFIG. 8in conjunction withFIGS. 1-7, an example method of data compression is illustrated in a flowchart. At decision block402, a decision is made whether active templates exist in a template catalog. If no from decision block402, source data is used to create a new active template at functional block404, and the template may be used at functional block412. If yes from decision block402, the active templates are searched for a perfect active template match (i.e., an active template having a template delta of zero) at functional block406. If a perfect match is found at decision block408, the template may be used at functional block412. If a perfect match is not found, the best template is found at functional block410, and the best template may be used for compression at functional block412.

It is noted that different ways of representing a template and calculating a template delta may be used, including a number of text differencing mechanisms such as the diff utility, which is a file comparison utility that outputs the differences between two files. The delta is then represented as data that can be stored in memory.

FIG. 9illustrates an example method for finding the best template illustrated inFIG. 8at functional block410. In one embodiment, functional block410includes determining a template delta for each active template and then finding an active template with the smallest template delta at functional block502. At functional block504, a total match ratio for all active templates is determined, and at decision block506, a decision is made whether desired compression has been reached by comparing the total match ratio to a target match ratio that may be pre-selected, and/or set by the user at a desired time. If yes from decision block506, the template with the smallest template delta is selected as the best template at functional block514. If no from decision block506, a decision is made whether a limit of active templates has been exhausted at decision block508. The limit can be based on a fixed number of templates, total template data size, amount of available memory, or various other metrics that are statically preset or changeable by a user. If yes from decision block508, the template having the smallest relative match ratio (i.e., the worst template) is moved to a retired template list within a template catalog (i.e., retired) at functional block510, and then source data is used to create an active template at functional block512. If no from decision block508, source data is used to create an active template at functional block512without retiring a template. The created template is selected as the best template at functional block514.

It is noted that the target total match ratio can be statically set for a particular domain/deployment in one embodiment and/or can also be adjusted at any point in another embodiment. If the target total match ratio is reached, the system will go into equilibrium (i.e., the active template set will remain stable until the total match ratio is again under the target). If the target total match ratio is poorly selected and cannot be reached due to a large variation of data, the system will keep recycling through the templates. This will generate an ever-growing set of retried templates, but the templates with the highest popularity metric will remain in the system longer. The effect of recycling through many templates does not have a negative impact on time of compression but may increase the average decompression time because retired templates have to be accessed from storage in addition to reading stored record compressed data.

FIG. 10illustrates an example method for finding a template with the smallest template delta illustrated inFIG. 9at functional block502. In one embodiment, functional block502includes selecting a first active template at functional block602, calculating a template delta at functional block604, and then making a decision whether the template delta size is smaller than a previous active template delta size at decision block608. If yes at decision block608, the template identifier and delta size are recorded in a memory at functional block612and a decision is made whether more active templates exist at decision block610. If no at decision block608, the method moves directly to decision block610to make a decision whether there are more active templates. If yes at decision block610, the next active template is selected at functional block606and the method repeats to functional block604. If no at decision block610, the template identifier with the smallest delta size is returned at functional block614.

FIG. 11illustrates an example method for retiring a template illustrated inFIG. 9at functional block510. In one embodiment, functional block510includes selecting an active template at functional block702, looking up the template's relative match ratio at functional block704, and making a decision whether the relative match ratio is smaller than a previously recorded relative match ratio at decision block708. If yes at decision block708, the template identifier is recorded at functional block712and the method moves to functional block710, but if no, a decision is made whether more active templates are available at decision block710. If more active templates are available, a next active template is selected at functional block706and the method repeats at functional block704. If more active templates are not available, the template with the smallest relative match ratio is retired at functional block714.

In one embodiment, a reset function may be provided to the user (e.g., via a user interface) for retiring all templates immediately and for starting from a new template added to the system, thereby allowing for quicker adjustment of the algorithm to a changing environment. An automatic reset (scheduled and/or calculated) may also be incorporated into the algorithm if large changes in source data are expected to be frequent.

FIG. 12illustrates an example method for using a template illustrated inFIG. 8at functional block412. In one embodiment, functional block412includes determining the template delta of the template at functional block802, and then comparing the size of the template delta with the size of the source data at decision block804. If the size of the template delta is smaller than the size of the source data (e.g., no in a decision block with the inequality template delta size>source data size), the template is used. The template popularity is updated at functional block808, and the template identifier and template delta are stored in the compressed data of the stored record at functional block810. If the size of the template delta is greater than the size of the source data (e.g., yes in the decision block), the template is not used and the source data is stored in the compressed data of a stored record without compression at functional block806, thus avoiding storage of “negative” compression.

Advantageously, embodiments of the present invention provide for high-level compression of records including redundant data, which allows the system to scale higher and perform more efficiently with minimal overhead. The incremental nature of the algorithm does not require that previously compressed records be re-evaluated (e.g., that stored records be read or re-compressed) when a new record is added. The compression time can be directly controlled by restricting the number of active templates allowed to be used. The algorithm dynamically adjusts to changing data by creating new templates. The algorithm is also designed to converge on the target compression ratio which can be configured for a given domain.