SYSTEMS AND METHODS FOR MEMORY MANAGEMENT IN BIG DATA APPLICATIONS

The disclosed embodiments describe techniques for allocating memory to functions processing big data. In one embodiment, a method is disclosed comprising allocating a first memory space to a function, the memory space comprising an initial amount of memory for the function; declaring the first memory space as the current memory space; processing data using the function, the processing writing data to the current memory space; determining that the function requires additional memory space; allocating a new memory space based on the current memory space and a growth factor; copying all data in the current memory space to the new memory space; declaring the current memory space as the old memory space; declaring the new memory space as the current memory space; and not deallocating the old memory space.

BACKGROUND

The exponential growth of data in every facet of human endeavor has necessitated the rise of applications capable of efficiently and quickly processing massive amounts of data. Current systems generally do not efficiently allocate memory when processing such massive amounts of data.

BRIEF SUMMARY

The example embodiments provide systems, devices, computer-readable media, and methods for dramatically improving the amount of memory required by applications processing massive amounts of data.

The analysis of massive data often requires parsing the data into associated values called tuples, which are then conceptually organized into tables of rows and columns where each tuple becomes a row. Using a website analysis application as a simple example, the columns could be user identifier (ID), timestamp, website, and gender. The corresponding row would be a user's unique ID, along with the timestamp of when that user visited the named website and the user's gender. The website column has the property of a high-cardinality dimension, because the number of different websites around the world is very large. The gender column is an example of a low cardinality dimension as the number of possible values is very small.

In some environments, millions of these rows of data can be collected from websites all over the world and stored in a central location to be analyzed. Because any individual user can visit many different websites every day, and may often visit the same website multiple times a day, some or all of these columns can contain duplicates.

As an example, an analysis task for this scenario may be defined as a task to compute the number of unique visitors for every website. To complete the task, an application will use an “aggregator function” (or, simply, an “aggregator”) to track the number of unique visitors to a specific website. During operation, the application must allocate memory space for an aggregator function for each website. If we assume we have one million websites, we will need one million aggregator functions and one million allocations of space for these aggregator functions.

As each row is processed, the application may find a corresponding website aggregator function and presents a user ID to the aggregator function. The aggregator function maintains a list of unique user IDs seen so far, checks the incoming user ID against this list, and if it has not been seen before, it adds the user ID to its list. If it has seen this user ID previously, the presented user ID may be ignored. At the end of processing of all rows, the number of user IDs in the aggregator's list is the unique count of visitors to that website. In practice, a few popular websites will have many user IDs in their lists, while many websites will have only a few.

One property of human-generated data is that for high-cardinality dimensions (e.g., the website column in the previous example) associated with a frequency attribute (e.g., the number of unique user IDs), the distribution of the number of unique user IDs versus the number of websites with that number of unique user IDs tends to follow a power-law distribution. When plotted on a chart with both axes logarithmic, the number of rows (websites) versus the frequency of user IDs associated with the number of rows is roughly a straight line.FIG.1depicts a typical example drawn from real data.

InFIG.1, the left of the graph100illustrates that about ten million websites (rows) were associated with only one visitor cookie (user ID), while on the right of the graph100, there was at least one website (i.e., row) that had over 400 million user cookies. In the middle of the graph100, there were ten thousand websites that each had ten thousand unique users. One of the properties of a power-law distribution is the slope of the resulting line. In graph100, the slope is negative because the curve slopes downward, going from left to right. As noted on the chart, the upper part of the curve has a slope of about −0.62, and the lower part of the curve has a slope of −0.96, which is close to −1.0. Thus, the overall trend is roughly a straight line over multiple orders of magnitude on both axes.

Aggregator functions typically used to process this kind of data are designed to have geometric growth properties. This means that the size of the aggregator function starts small, and when extra space is needed, the application or the aggregator function resizes its usable space by a constant factor (r) which can be any positive number greater than 1.0 but typically is 2.0 or more. After an aggregator function is initialized at a starting size, if the aggregator function needs to grow, the new allocated size for any one aggregator function can be defined as follows:

where sizenewrepresents the new memory space size, sizecurrentrepresents the current memory space size, and r represents a fixed (i.e., constant) growth factor.

Some aggregator functions can have an upper bound on their size. If a specific aggregator function does not specify an upper size bound, the user will typically compute a practical upper size bound based on the overall size of the user's data. Either way, this knowledge of the upper size bound is commonly used to allocate the overall consumption of computer memory, which would be the number of aggregator functions required times the upper size bound of the aggregator function. If, during processing, an aggregator function exceeds its upper size bound, it may require special handling. This special handling varies considerably across applications and is not limiting.

If we let a=sizestart, then the sequence of new sizes that the aggregator function goes through as it grows is:

where k is the number of size terms in the sequence, r is the growth factor, and a is the initial or starting size of the aggregator function. The progression in Equation 2 comprises a geometric progression. One property of this progression is its dynamic range, which is the largest size of an aggregator divided by its starting size, or

The dynamic range is typically greater than two but can be many orders of magnitude. In some embodiments, the larger the dynamic range, the more pronounced the savings in memory usage. However, even for cases where the dynamic range is as low as two, the example embodiments still provide significant technical benefits.

Big data applications may need to allocate millions of these aggregator functions while processing raw data. Since each aggregator function requires variable memory space, memory management is paramount to the performance of these big data applications.

Thus, there currently exist problems in the state of the art regarding how an application should allocate space for these aggregator functions before processing begins without the knowledge of which functions will need lots of space and which ones will need only a small amount of space. These example embodiments demonstrate dramatic savings in the amount of memory required by a computing device or system and thus improve the overall function of a computing device or system.

In the various embodiments, methods, systems, computer-readable media, and devices are described for allocating memory to functions processing big data.

In one embodiment, a method is disclosed comprising allocating a first memory space to a function, the memory space comprising an initial amount of memory for the function; processing data using the function, the function writing data to the first memory space; determining that the function requires additional memory space; allocating a new memory space based on a predefined growth factor and the current size of the allocated memory space. This is followed by the aggregator function copying its data from the previous memory space to the new memory space and continuing its aggregation function. This embodiment allows the previous memory space to not be deallocated or collected by any garbage collection function. In some embodiments, for performance reasons, the method may not attempt to deallocate and collect the previous memory space until the overall analysis application has completed its job.

In one embodiment, the method further comprises determining that the size of the new memory space exceeds a preconfigured maximum and may raise an exception or flag, which indicates to the application that special handling is required.

The disclosed embodiments further provide non-transitory computer-readable storage media and devices for performing the above methods. In one embodiment, the non-transitory computer-readable storage media tangibly stores computer program instructions capable of being executed by a computer processor, the computer program instructions defining steps of the methods.

DETAILED DESCRIPTION

FIG.1is a graph (100) illustrating a typical real data set exhibiting a power-law distribution.

In the graph (100), a row count is plotted as a function of the number of unique cookies. In an embodiment, each row can be associated with a website, website page, or URL. In graph100, the number of unique cookies (i.e., unique visitor IDs) is counted for each row (i.e., website). Then the number of rows having a number of unique cookies is plotted as illustrated inFIG.1. This is a typical example of the power-law distribution of real data.

The data set inFIG.1includes about 37.5 million rows. As illustrated, a corresponding number of unique cookies is plotted on a logarithmic scale from one to one billion. Thus, as one example, the number of rows (e.g., websites) having one unique cookie is equal to approximately ten million. Similarly, the number of rows having 100 million unique cookies is equal to approximately ten. As illustrated by the trendline, the mapping of unique cookies to rows follows a power-law distribution.

In an embodiment, a big data application may process data represented inFIG.1by assigning an aggregator function for each website, website page, or URL. Details ofFIG.1were described previously and are not repeated herein.

FIG.2is a flow diagram illustrating a method200for processing large data sets using a dynamic memory allocation method according to some embodiments of the disclosure.

In step202, the method200can include initiating a processing job.

In one embodiment, a processing job can comprise any executable code configured to process data. In one embodiment, the data can comprise a large amount of data. In one embodiment, the method200can define the processing job as a series of discrete functions. These functions can be different in some embodiments, while in other embodiments, the functions can comprise the same function, replicated multiple times. In some embodiments, the method200may execute these functions in a distributed manner. For example, in some embodiments, the method200may spawn multiple identical functions to parallel process partitions of a dataset.

As one example, a dataset can comprise a table or other structured data. In other embodiments, the dataset can comprise an unstructured dataset. In one embodiment, the method200includes a pre-processing step whereby the method200partitions the dataset into a set of smaller datasets based on specified criteria. For example, a dataset can comprise a set of unique cookies recorded across multiple websites, as described inFIG.1. In this example, the method200can include grouping the unique cookies based on a website identifier (e.g., domain) and thus forming a set of “rows” of the dataset, each row corresponding to a website.

In some embodiments, initiating the processing job can comprise reading data from the dataset (including partitions if pre-processed) and feeding the data into one or more functions. For example, method200begins reading data in one embodiment and provides data to the functions as the method200iterates through the data set. In one embodiment, method200can dynamically initialize functions as needed. However, the method200can initialize a fixed number of functions (e.g., based on available hardware or processing resources).

In step204, method200can include initiating N functions, where N is the estimated number of rows (or websites) that need to be processed by the application.

As discussed above, the method200can include partitioning a larger dataset into smaller chunks or partitions. However, in some embodiments, the method200does not equally partition the data. That is, specifically, the size of the data in each partition can vary across partitions. For example, a large number of partitions may include very little data, while a smaller number may include a large amount of data. Continuing the previous example, a small number of websites can include many unique cookies (e.g., the most frequently visited websites). In contrast, a much larger number of less frequently visited websites can include a smaller number of unique cookies. As discussed previously, the data processed by the method200exhibits a power-law distribution of data in many scenarios.

In one embodiment, the method200initiates the N functions as needed. That is, for each contained row of data, method200initiates a new function. Thus, in such embodiments, the number of functions (N) is equal to the number of rows (or websites that need to be processed with the raw data. In general, method200can implement this approach when implemented in an elastic compute environment. For example, the method200can implement each of the N functions as a serverless function. In such an embodiment, method200requires no information regarding the underlying data to be processed, and this enables method200to replicate the same function for all partitions. However, as will be discussed, this feature also results in the lack of knowledge of the memory needed for the function to operate. In another embodiment, method200can allocate a fixed number (N) of functions and input data from the dataset into this fixed number of functions.

In step206, the method200can include dynamically allocating memory to the N functions. Details of how the method200dynamically allocates memory to a given function in the N functions are provided, in more detail, in the description ofFIG.3. In brief, the method200allocates an initial, minimum amount of memory. A given function receives and processes data, using the initial memory allocation to store data and results. As the function ingests and processes data, it may determine that the initial allocation is insufficient to process the incoming or existing data. In response, method200can allocate or request a new region of memory based on a fixed growth factor and its current size and then move or copy its data from the current memory to the new memory. Method200can further retain a reference to the current memory allocation and not allow deallocation of the current memory. It is wide industry practice to consider this a memory leak and, thus, a programming error. However, the example embodiments will demonstrate that this behavior is close to optimum in terms of managing overall memory allocation for the application. Method200can continue to grow the memory space of the function in this manner until the application ends or until method200allocates a maximum amount of memory to the function.

In step208, the method200can include outputting the results of the N functions.

After a given function of the N functions finishes processing its input data, it returns an output result. The disclosure does not limit the type of data output by a given function, and the function can output any type of content. In some embodiments, method200can receive the outputs of each function and further aggregate the outputs to a single output value. In some embodiments, the N functions can operate asynchronously, and thus method200can operate to await the results of all N functions before combining their outputs. In one embodiment, one can further modify the method200to manage the deallocation of memory used by the functions after application completion. However, in other embodiments, a given function may independently deallocate its memory when signaled to do so.

FIG.3is a flow diagram illustrating a method300for dynamically allocating memory to a function according to some embodiments of the disclosure.

In step302, the method300can include allocating initial memory space to a function. In one embodiment, the initial memory space can comprise a minimum amount of memory. In one embodiment, this minimum amount of memory comprises a customizable amount of memory allocated for every function the method300allocates. As an example, the method300may allocate 16 bytes of random-access memory (RAM) for each function.

In step304, method300determines if all data has been processed. If so, it branches to step314. Otherwise, it branches to step306.

In step306, the method300can comprise processing data using the function. As discussed above, the method300can execute the function to perform operations on data received by the function. The disclosed embodiments place no limit on the type of operations performed.

In step308, the application loads new data into the aggregator function. In general, the operations process data and write data to the allocated memory space (such as the initial memory space) during processing. At a minimum, the function will store input data in the memory space and may store the results of processing the memory space as well. Further, the function may store the output data of the function as well. As such, during the execution of the function, the function will continue to consume memory space. The function can (and often will) require additional memory space to process incoming data. However, the use of an initial memory allocation ensures that those functions requiring less than the minimum amount of memory do not require additional memory allocations.

In step310, method300can determine if additional memory is needed. As will be discussed, if method300determines that the amount of memory currently allocated to the function is suitable, method300can proceed back to step304to process new data and load more data (steps306and308, respectively) until step310is triggered. If, however, method300determines that more memory is needed, method300proceeds to step312.

In step312, method300computes the new memory space using Equation 1. It then moves all aggregator function data from the current memory space to the new memory space. It then labels the current memory space as old memory space; and labels the new memory space as current memory space. In step312, the method300does not deallocate the old memory space. In some embodiments, step312can further include determining if the current memory space size has exceeded a preconfigured maximum memory space size where an exception or flag is raised to trigger special handling.

In one embodiment, the method300can externally manage the memory allocation for a function (or many functions). In such an embodiment, the memory space of the function is virtualized, and the executing function need not perform any manual or automatic memory allocation. In such an embodiment, an external process can monitor a designated memory space and manage the memory space (as will be discussed) upon determining that the currently allocated memory space is running out of available space. In such an embodiment, the function may allocate memory via implicit commands such as object creation, function creation, etc., and need not rely on lower-level memory allocation system calls (e.g., malloc or calloc). In such embodiments, method300can be executed in a garbage-collected environment such as a Java®, Ruby, or JavaScript environment. Although main Random Access Memory (RAM) is primarily used as an example, the disclosure is not limited solely to RAM allocation. Indeed, the techniques can equally be applied to, for example, persistent storage (e.g., Flash storage) devices.

In another embodiment, the functions themselves manage their own memory allocations. In this embodiment, the functions themselves manually (or semi-automatically) allocate memory space as needed. In general, such an approach requires that the functions be implemented in a lower-level programming language such as C, C++, Rust, or similar languages that provide memory allocation primitives. In other embodiments, the method300can provide a shared object or dynamically linked library that supports the memory allocation strategies described herein.

In one embodiment, the method300can use a constant growth factor to compute the new memory space to allocate. In one embodiment, the method300can calculate the size of the new memory space using Equation 1.

As one example, the method300may allocate an initial memory allocation of 16 and use a growth factor of 2.0. The first time the method300executes step312, the method300computes a new memory space size of 16*2.0 or 32 bytes. Because the current memory is not deallocated, the total consumed space is 16+32=48 bytes. The second time the method300executes step312, the method300computes a new memory space size of 32*r or 64 bytes, including the current allocation yields 32+64=96 bytes. Thus, as illustrated inFIG.4, Column406F, the incremental increase in memory space increases as a sum of a geometric progression each time the method300detects more memory is needed:

where k is the number of terms in the series, and a is the initial allocation size. Since both a and r are known, k can be estimated using modeling. Column406F represents this sum equation where k varies from 1 to 17 in the example. Additionally, the total space consumed by a single function after k−1 growth cycles excluding the non-deallocated old memory spaces is just:

Further detail regarding Equations 4 and 5 are provided in the Appendix.

In step314, the method300can include outputting the results of all the aggregation functions. The disclosure does not limit the type of data output by the functions, and the functions can output any type of content.

In step316, the method300can include deallocating or freeing all memory spaces allocated to the functions at the end of all processing. In one embodiment, the method300can manually deallocate all memory prior to ending the execution of a function. In another embodiment, method300can comprise running a garbage collection routine to automatically reclaim all memory allocated during the execution of method300.

FIG.4is a table400illustrating memory allocations using the disclosed embodiments where the power-law distribution of the incoming data has an approximate slope of −1.0, and the aggregation functions are configured with a fixed resize factor of 2.0. In the illustrated table400, a model is depicted where the aggregation function has been configured with a growth factor (r) of 2.0 and an initial size of 16 bytes. The input data comprised approximately nine million rows being aggregated by about one million aggregators. The power-law effect of the incoming data is demonstrated in this table, where eight aggregators required a space of about one million bytes. Each of those aggregators would have been loaded by about 65 thousand rows. Meanwhile, about 525 thousand aggregators required a space of only 16 bytes, and each of those aggregators would have been loaded by just one row.

In table400, a simulation of a processing job, such as that described in connection withFIGS.2and3, is illustrated. In the illustrated table400, a fixed growth factor402of 2.0 is used. As described previously, such a fixed growth factor is shown as an example, and other growth factors can be used. Further, in the illustrated embodiment, a hypothetical slope404of −1.0 is used. In the illustrated embodiment, the slope404is used to model the distribution of the input data analyzed by functions in aggregate. In the illustrated embodiment, the slope404comprises a log-log slope of a power-law distribution of the number of aggregator functions associated with a particular function's memory size.

In the illustrated embodiment, the first column406A models the size of a function. Thus, as illustrated, the simulation represented by table400models functions taking 16, 32, 64, etc., bytes of data. The second column406B models the expected number of functions for each size as a result of a power-law distribution with a growth factor402of 2.000 and an overall log-log slope404of −1.000. In the illustrated embodiment, the model was configured so that the minimum or initial size of a function is 16 bytes, the maximum size of a function is about one million bytes, and the total number of functions in the system is about one million.

In the illustrated embodiment, the third column406C is the product of the first column406A and second column406B and represents an ideal or “perfect” memory allocation if such an allocation was practical. As illustrated in the total row, a perfect allocation for all aggregator functions would total about 143 MB.

In the illustrated embodiment, the fourth column406D represents a fixed memory allocation where the system application hypothetically allocates the maximum function size (1 MB) for all one million functions. As illustrated in the total row, this results in an overall allocation of about one terabyte. Notably, the fourth column406D represents memory allocation in the majority of current systems where the data size cannot be known in advance. As discussed previously, big data applications generally do not know which of the many functions will need to grow larger or by how much. As a result, system developers will typically allocate, upfront, the maximum memory size (e.g., 1 MB inFIG.4) for all sub-component functions. As illustrated in the total row, this results in large amounts of wasted memory (e.g., one terabyte of Fixed space versus 143 MB of Perfect space allocation). This is also labeled the F/P ratio. In this example, the fixed allocation is about 7,710 times larger than the perfect allocation would be.

In the illustrated embodiment, the sixth column406F represents the storage consumed by a single given function using the method ofFIGS.2and3if that function were to grow through 16 stages of growth. In the illustrated embodiment, for example, a function requiring 16 bytes of memory is allocated 16 bytes of memory, a function requiring 32 bytes of memory is allocated 48 bytes of memory, etc. In the illustrated embodiment, the fifth column406E represents the product of the sixth column406F and the predicted number of functions in the second column406B. As illustrated in the total row, this results in an overall allocation of about 268 MB. The ratio of the total of column406E divided by the total of the Perfect allocation column, or 142 MB, also labeled as the E/P ratio, is about 1.88, or less than 2.0 Also, note that the ratio of the total of the fixed allocation column divided by the total of the 5th column is about 4095. This means that the method described inFIGS.2and3results in a memory savings that is 4095 times smaller than if the fixed allocation scheme was used. This is also labeled the F/E ratio.

In the illustrated embodiment, the total of the third column406C represents a floor of memory allocations in a perfect allocation scheme, while the total of the fourth column406D represents a ceiling (e.g., fixed) allocation that will meet the demands of the system. As illustrated, the memory allocated using the methods ofFIGS.2and3, or about 268 MB, is significantly less than the total of the fourth column406D, about 1 terabyte, and significantly closer to that of a perfect memory allocation, of 143 MB, as illustrated in the total of the third column406C.

In the illustrated embodiment, the fourth column406D and fifth column406E all represent the “final” memory allocations for each function after the processing job executes and thus represent a maximum memory allocation during the lifetime of the processing job.

In the illustrated embodiment, various comparisons are provided. In a first comparison408, the fixed memory allocation and perfect allocation are compared. As illustrated, the fixed memory allocation uses 7,710 times more memory than the perfect case. Similarly, in the second comparison410, the fixed memory allocation uses 4,096 times more memory than the allocations performed using the methods ofFIGS.2and3. Finally, a third comparison412illustrates the performance of the methods ofFIGS.2and3with respect to the perfect allocation scheme. As illustrated, the allocations performed using the methods ofFIGS.2and3are only 1.88 times greater than the perfect allocation scheme. Thus, as illustrated, when the distribution of data sizes approximates a power-law distribution, the allocations performed using the methods ofFIGS.2and3can perform significantly better than standard approaches currently used, namely the fixed memory allocation. As illustrated in table400, using a fixed memory allocation approach would be impossible with a single device (e.g., laptop or local developer machine) and would require coordination across multiple devices, further complicating such a system. By contrast, using the methods ofFIGS.2and3, the same processing job can be performed easily on a commodity device or local workstation.

FIG.5Ais a table500A illustrating memory allocations using the disclosed embodiments, where the growth factor is held constant at 2.0, and the assumed slope of the power-law distribution of the input data varies from a shallow log-log slope of −0.5 to a very steep log-log slope of −1.5. Each row of the table500A is the last three columns of the Summary row fromFIG.4along with the three columns of metrics showing the effectiveness of the memory savings (discussed herein).

In the illustrated table500A, a plurality of simulations was performed using a fixed growth rate502A and a variable log-log slope504A. For each simulation, the table500A illustrates a total memory allocation using a perfect allocation506A, fixed memory allocation508A, and improved allocation510A performed using the methods ofFIGS.2and3. Details of each approach were provided in the description ofFIG.4and are not repeated herein. In brief, each row of the table500A can correspond to the total row ofFIG.4, albeit with differing slopes. Thus, the individual distribution of function allocations is not illustrated inFIG.5A. In the illustrated embodiment, and as discussed previously, the variable slope504A corresponds to the distribution properties of the underlying data set. Since this slope504A is dependent on the input data, the table500A illustrates the performance of the methods ofFIGS.2and3with different distributions of data.

As illustrated, various comparisons are depicted, including a first comparison512A of F/P, which is between the fixed memory allocation508A approach and the perfect allocation506A, a second comparison514A of F/E, which is between the fixed memory allocation508A approach and the improved allocation510A, and a third comparison516A of E/P, which is between the improved allocation510A and the perfect allocation506A. In general, the first comparison512A is obtained by dividing the fixed memory allocation508A approach by the perfect allocation506A, the second comparison514A is obtained by dividing the fixed memory allocation508A by the improved allocation510A, and the third comparison516A is obtained by dividing the improved allocation510A by the perfect allocation506A.

As illustrated, the improved allocation510A outperforms the fixed memory allocation508A in all simulations. Further, the improved allocation510A never utilizes more than double the memory used by the perfect allocation506A as illustrated in column516A. By contrast, at steep slopes of −1.5, the fixed memory allocation508A is significantly larger than the perfect memory allocation506A. Thus, the steeper the slope, the larger is the benefit of using the methods ofFIGS.2and3.

In the illustrated embodiment, the third comparison516A can be considered the efficiency of the improved allocation510A performed using the methods ofFIGS.2and3. In the embodiments, the efficiency of the improved allocation510A can be guaranteed to be less than or equal to two, that is, double the perfect allocation506A. In one embodiment, this guarantee will hold for all growth factors greater than or equal to two (2.0) and all slopes greater than zero. In the illustrated embodiment, small growth factors require more overall allocation than larger growth factors. However, a growth factor of 2.0 is very common. In some embodiments, shallow slopes require more overall allocation than steep slopes. However, the slope is determined by the input data and is thus not subject to change by the allocation routine.

FIGS.5B through5Dare graphs illustrating memory allocations using the disclosed embodiments.

In graph500B, column516A (E/P) is plotted as a function of log-log slope column504A on a linear scale.

In graph500C, column514A (F/E) and column512A (F/P) are plotted as a function of slope504A on a linear scale.

In graph500D, the perfect allocation506A and improved allocation510A, in bytes, are plotted as a function of slope504A.

As illustrated in graph500B and graph500C, the improved allocation510A consistently outperforms the fixed memory allocation508A. Further, the improved allocation510A grows in effective lockstep with the perfect allocation506A.

FIG.6Ais a table illustrating memory allocations using the disclosed embodiments, where the log-log slope is held constant at −1.0, and the configured growth factor of the aggregator functions varies from a slow growth factor of 1.2 to a much faster growth factor of 4.0. This is a variation of the model used inFIG.5A, except here, the slope is kept constant at −1.0, and the growth factor is allowed to vary from 1.2 to 4.0.

In the illustrated table600A, a plurality of simulations was performed using a variable growth factor602A and a fixed log-log slope604A. For each simulation, the table600A illustrates a total memory allocation using a perfect allocation606A, fixed memory allocation608A, and improved allocation610A performed using the methods ofFIGS.2and3. Details of each approach were provided in the description ofFIG.4and are not repeated herein. In brief, each row of the table600A can correspond to the total row ofFIG.4, albeit with differing growth factors. Thus, individual function allocations are not illustrated inFIG.6A. In the illustrated embodiment, and as discussed previously, the variable growth factor602A corresponds to the amount of memory allocated to functions when such functions exhaust their current memory. The fixed memory allocation608A allocates the maximum memory to all functions upfront, so the growth factor is not influencing the figures in608A.

Since this growth factor602A is being adjusted by the simulation model, the table600A illustrates the performance of the methods ofFIGS.2and3with different growth factor configuration settings that might be chosen in an actual application.

As illustrated, various comparisons are depicted, including a first comparison612A (F/P) between the fixed memory allocation608A approach and the perfect allocation606A, a second comparison614A (F/E) between the fixed memory allocation608A approach and the improved allocation610A, and a third comparison616A (E/P) between the improved allocation610A and the perfect allocation606A. In general, column612A (F/P) is obtained by dividing the fixed memory allocation608A approach by the perfect allocation606A, column614A (F/E) is obtained by dividing the fixed memory allocation608A by the improved allocation610A, and column616A (E/P) is obtained by dividing the improved allocation610A by the perfect allocation606A.

As illustrated, the improved allocation610A outperforms the fixed memory allocation608A in all simulations. Further, the improved allocation610A never utilizes more than double the memory used by the perfect allocation606A as long as the configured growth factor is above two (2.0). However, note that as the configured growth factor decreases, the overall memory allocation increases even for the Perfect allocation, so there is little incentive for using such low growth factors. For configured growth factors greater than 2.0 the improved allocation610A outperforms the fixed memory allocation608A by orders of magnitude.

FIGS.6B through6Dare graphs illustrating memory allocations using the disclosed embodiments.

In graph600B, the third comparison616A (E/P) is plotted as a function of growth factor602A on a linear scale.

In graph600C, column614A and column612A are plotted as a function of growth factor602A on a linear scale.

In graph600D, the perfect allocation606A and improved allocation610A, in bytes, are plotted as a function of growth factor602A. As illustrated in graph600B and graph600C, the improved allocation610A consistently outperforms the fixed memory allocation608A. Further, for growth factors greater than 2.0, the improved allocation610A is always less than or equal to two times the perfect allocation606A.

FIG.7is a block diagram illustrating a computing device showing an example of a computing device700used in the various embodiments of the disclosure.

In some embodiments, computing device700can comprise a network interface card (NIC)702, central processing unit (CPU)714, persistent storage704, volatile memory706, function pool716, and memory manager718.

In some embodiments, the CPU714may comprise a general-purpose CPU. The CPU714may comprise a single-core or multiple-core CPU. The CPU714may comprise a system-on-a-chip (SoC) or a similar embedded system. In some embodiments, a GPU may be used in place of, or in combination with, a CPU714. In the illustrated embodiment, the CPU714can receive and transmit data to other devices via NIC702. In one embodiment, NIC702can comprise an Ethernet interface or other network interface. In some embodiments, the CPU714can be used to process big data workloads as part of a processing job. In such an embodiment, the CPU714can receive this data via the NIC702.

In one embodiment, the CPU714can store data persistently in persistent storage704. As one example, CPU714can receive big data from an external data source and cache the big data in the persistent storage704. In some embodiments, this storage can be temporary while the computing device700executes a processing job. In another embodiment, CPU714can receive data as a stream directly to the function pool716for processing.

In an embodiment, CPU714can manage a function pool716of functions associated with a processing job. Details of functions implementing a processing job have been described previously and are not repeated herein. In an embodiment, the function pool716can be implemented in the CPU714in hardware or can comprise software instructions executing in volatile memory706. In some embodiments, each function in the function pool716can comprise an identical function spawned for a partition of data, as previously discussed. As one example, a big data dataset can be stored in persistent storage704. The CPU714can then partition the big data dataset and spawn a plurality of functions in the function pool716for each partition. In an embodiment, CPU714is configured to execute steps202,204, and208ofFIG.2.

In an embodiment, the computing device700comprises a memory manager718. As with function pool716, in an embodiment the memory manager718can be implemented in the CPU714in hardware or can comprise software instructions executing in volatile memory706. In an embodiment, the memory manager718manages the memory used by functions in the function pool function pool716. As discussed, the memory manager718can be part of a managed execution environment (e.g., a Java environment or similar environment). In an embodiment, memory manager718communicates with the function pool716and intercepts all memory allocations requested and processed for the functions. As such, in an embodiment, memory manager718may handle all memory allocation commands (either implicit or explicit) issued by functions in the function pool716. Specifically, memory manager718can be configured to execute the methods described inFIG.3.

As illustrated, memory manager718is communicatively coupled to volatile memory706. In an embodiment, memory manager718allocates memory (e.g.,708A,708B,708C,708D,710A,710B,712) to functions in the function pool716. As illustrated graphically on the x-axis, the size of memory708A,708B,708C,708D,710A,710B,712for each function varies based on the input data and memory requirements as described in more detail in the description ofFIG.3. The specific number and sizing of memory708A,708B,708C,708D,710A,710B,712is not intended to accurately depict the exact contents of memory and is provided solely to illustrate the differing sizes of memory managed by memory manager718.

In an embodiment, memory manager718is configured to manage memory allocations as well as writing to memory. In such an embodiment, functions in the function pool716issue requests to write to volatile memory706via memory manager718. In another embodiment, as illustrated by the dotted line, after allocation, functions in the function pool716can write to volatile memory706directly. However, in such an embodiment, memory manager718manages the sizing of memory708A,708B,708C,708D,710A,710B,712for each function.

In an embodiment, memory manager718further includes a garbage collector configured to monitor the status of functions in the function pool716and periodically free memory used by the functions when the functions are terminated. Details of this operation are provided in more detail inFIG.3.

FIG.8is a block diagram illustrating a computing device showing an example of a client or server device used in the various embodiments of the disclosure.

The device800may include more or fewer components than those shown inFIG.8, depending on the deployment or usage of the device800. For example, a server computing device, such as a rack-mounted server, may not include audio interfaces852, displays854, keypads856, illuminators858, haptic interfaces862, Global Positioning System (GPS) receiver864, or cameras/sensors866. Some devices may include additional components not shown, such as graphics processing unit (GPU) devices, cryptographic coprocessors, artificial intelligence (AI) accelerators, or other peripheral devices.

As shown inFIG.8, the device800includes a central processing unit (CPU)722in communication with a mass memory830via bus824. The device800also includes one or more network interfaces850, an audio interface852, a display854, a keypad856, an illuminator858, an input/output interface860, a haptic interface862, a global positioning system, or GPS receiver864and a camera(s) or other optical, thermal, or electromagnetic sensors866. Device800can include one camera/sensor866or a plurality of cameras/sensors866. The positioning of the camera(s)/sensor(s)866on the device800can change per device800model, per device800capabilities, and the like, or some combination thereof.

In some embodiments, the CPU822may comprise a general-purpose CPU. The CPU822may comprise a single-core or multiple-core CPU. The CPU822may comprise a system-on-a-chip (SoC) or a similar embedded system. In some embodiments, a GPU may be used in place of, or in combination with, a CPU822. Mass memory830may comprise a dynamic random-access memory (DRAM) device, a static random-access memory device (SRAM), or a Flash (e.g., NAND Flash) memory device. In some embodiments, mass memory830may comprise a combination of such memory types. In one embodiment, the bus824may comprise a Peripheral Component Interconnect Express (PCIe) bus. In some embodiments, the bus824may comprise multiple busses instead of a single bus.

Mass memory830illustrates another example of computer storage media for the storage of information such as computer-readable instructions, data structures, program modules, or other data. Mass memory830stores a basic input/output system (“BIOS”)840for controlling the low-level operation of the device800. The mass memory also stores an operating system841for controlling the operation of the device800

Applications842may include computer-executable instructions which, when executed by the device800, perform any of the methods (or portions of the methods) described previously in the description of the preceding Figures. In some embodiments, the software or programs implementing the method embodiments can be read from a hard disk drive (not illustrated) and temporarily stored in RAM832by CPU822. CPU822may then read the software or data from RAM832, process them, and store them in RAM832again.

The device800may optionally communicate with a base station (not shown) or directly with another computing device. The one or more network interfaces850are sometimes referred to as a transceiver, transceiving device, or network interface card (NIC).

The audio interface852produces and receives audio signals such as the sound of a human voice. For example, the audio interface852may be coupled to a speaker and microphone (not shown) to enable telecommunication with others or generate an audio acknowledgment for some action. Display854may be a liquid crystal display (LCD), gas plasma, light-emitting diode (LED), or any other type of display used with a computing device. Display854may also include a touch-sensitive screen arranged to receive input from an object such as a stylus or a digit from a human hand.

Keypad856may comprise any input device arranged to receive input from a user. Illuminator858may provide a status indication or provide light.

The device800also comprises an input/output interface860for communicating with external devices, using communication technologies, such as USB, infrared, Bluetooth™, or the like. The haptic interface862provides tactile feedback to a user of the client device.

The GPS receiver864can determine the physical coordinates of the device800on the surface of the Earth, which typically outputs a location as latitude and longitude values. GPS receiver864can also employ other geo-positioning mechanisms, including, but not limited to, triangulation, assisted GPS (AGPS), E-OTD, CI, SAI, ETA, BSS, or the like, to further determine the physical location of the device800on the surface of the Earth. In one embodiment, however, the device800may communicate through other components, provide other information that may be employed to determine the physical location of the device, including, for example, a MAC address, IP address, or the like.

Throughout the specification and claims, terms may have nuanced meanings suggested or implied in context beyond an explicitly stated meaning. Likewise, the phrase “in some embodiments” as used herein does not necessarily refer to the same embodiment, and the phrase “in another embodiment” as used herein does not necessarily refer to a different embodiment. It is intended, for example, that claimed subject matter include combinations of example embodiments in whole or in part.