Abstract:
Methods and an apparatus for data sorting is provided. Keys are derived from a data set and a mapping function is obtained for sorting the data set in accordance with the mapping function. A wide key sort on the keys is performed over a plurality of distributed nodes using the mapping function, resulting in sorted lists of rows from the data set produced in parallel from the nodes with each row associated with a unique one of the keys pushed to a stack machine. The sort process is an ordered row traversal from the stack machine.

Description:
RELATED APPLICATIONS 
       [0001]    This is a non-provisional application which claims the benefit of priority to U.S. Provisional Application No. 62/270,619, entitled “Method and Apparatus for Efficient Data Storing;” filed on Dec. 22, 2015, the disclosure of which in its entirety is incorporated by reference herein. 
     
    
     BACKGROUND 
       [0002]    Sorting data is a common problem in the big data applications space. Sorting implementations can suffer from significant limitations in practice, particularly when built from dedicated hardware (HW), but also when implemented in software (SW), where both may ultimately be subject to strict area and power constraints, relative to the scalability of critical sort capabilities. For example, a vectorized (SIMD) SW implementation of a sort algorithm is at least implicitly constrained by the vector HW core&#39;s own micro architectural limitations (only finite core HW, vector width, operational frequency &amp; power curves, etc.), as much as a dedicated HW solution may be gate-limited in an FPGA or ASIC, forcing difficult tradeoffs that can affect not just the overall applicability of the practical implementation, but even, effectively, of the algorithm itself. Such limitations are often manifested in bounded sort key width, a characteristic fundamental to the breadth of problems the algorithm may solve. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0003]      FIG. 1  depicts a HW wide key sort technique, according to an embodiment. 
           [0004]      FIG. 2  graphically depicts results from a HW wide key sort technique, according to an example embodiment. 
           [0005]      FIGS. 3A-3B  depicts processing levels for a HW wide sort technique, according to an example embodiment. 
           [0006]      FIGS. 4A-4D  depicts a more detailed view of different levels of granularity for a HW wide sort technique, according to an example embodiment. 
       
    
    
     DETAILED DESCRIPTION 
       [0007]    Various embodiments depicted herein are implemented as one or more software modules, which are programmed within memory and/or non-transitory computer-readable storage media and executed on one or more processing devices (having memory, storage, network connections, one or more processors, etc.), 
         [0008]    The embodiments herein provide, among other things: 
         [0009]    A scalable architecture that can be implemented in hardware logic (ASIC/FPGA), or even as software in parallel CPU threads, to effect a sort of small to very large data sets, applicable to data at rest or in flight. Basic properties of scalability and skew tolerance are favorable, for predictable performance, while the technique itself is simple enough to be relatively low cost (in terms of, e.g., resources and routability) in a parallel hardware solution. Indeed this approach exploits what practical custom hardware solutions and multi-threaded software can do best: implement simple distributed parallelism, requiring only small-scale connectivity. 
         [0010]    Methods for optimizing utilization and throughput of physical implementation
       Independent parallel implementations can work together for performance scaling, or separately for concurrency   Maintaining multiple frontiers intra- and inter-level   Dynamic, and potentially even predictive, data-parallel distribution to mitigate skew       
 
         [0014]    Methods for addressing of input data lists, which may be primarily extrinsic, computed by partition and offset (simple static scheduling) 
         [0015]    Methods for optimizing scalability and resource requirements
       Performing multi-buffering vs. in-situ may be included (storage)   Naturally amenable to block compression schemes   Time &amp; resource scaling O(N log N), with implementation resource scaling being effective, but also optional (flexible scalability)       
 
         [0019]    Methods for reducing latency, e.g. for small data sets, may be included (latency vs. throughput) 
         [0020]    No special hardware vendor dependencies—circuitry fundamental enough to be supported anywhere (fundamental) 
         [0021]    Storage requirements O(N), making this efficiently applicable to data at rest problems, while also supporting data in flight in various topologies, including but not limited to dataflow and streaming architectures (extended system architectures &amp; topologies) 
         [0022]    Moreover the methods and apparatuses presented herein provide for: sorting of data sets small to large and efficient extension of core (primitive) sorting algorithms &amp; implementations with limited scaling of key width. 
         [0023]    Still further the techniques presented herein provided for 
         [0024]    Method and apparatus to extend the key-width scale of a given sort algorithm
       Many orders of magnitude extension   Efficient for HW area, power, and   Storage (including potential memory space) costs       
 
         [0028]    Focus on localized and pipelined-parallelism
       Optimizes throughput performance   Aligns with strengths of highly parallel implementations in HW and SW   Admits iterative approaches, as well, in a flexible and adaptive fashion, depending on resource availability, etc.       
 
         [0032]    Efficient result data structures
       Help minimize storage/memory requirements   Amenable to a simple compression scheme (included)   May be built and traversed efficiently by parallel processes       
 
         [0036]    Generalized to increase applicability
       Key Domain mapping may vary by application, supporting different notions of key &amp; row space   Hash mapping may vary by application, to control ultimate sorting semantics   Admits statistical approaches to characterize performance expectations, which may be further extended       
 
         [0040]    Networked, streaming, and dataflow-oriented implementations are enabled particularly by pipelined-parallelism, as the overall process may be distributed over custom HW chips, cores, processors, nodes, systems, etc. 
         [0041]    In an example, implementation the following constraints and assumptions are assumed. It is noted this is modifiable and customizable based on the situation.
       Local Constraints
           Simplified localized TeraSort (TERADATA®, Inc.)   Cardinality, N=1B   Key space, 10-byte   Tuple size, K=10-byte key+6-byte value=16 bytes   Stability (waived)   
           Assumptions
           Memory capacity&gt;=2*K*N (e.g. 32 GB)   Memory BW (M)   
           Sustainable and Consistent for Thousands of Streams
           Core throughput (T=Keys/s)   
           T is a function of many variables, including K, algorithms, network, PE arch, . . .       
 
         [0054]    The Approach in the example implementation is as follows with reference to the  FIGS. 1-2 . 
       Approach 
       [0000]    
       
         
           
             Multi-pass, deep merge sort network (tree)
           Each network node (PE?) capable of performing localized merge sort at throughput T   Increased depth minimizes total number of levels &amp; minimizes memory BW dependency (i.e. mitigates memory BW bound)   
         
             Key factors in assumptions
           Node results must traverse internal network efficiently
               otherwise, potential for cumulative penalties to effective T   
               Multiple passes must be scheduled to maximize network utilization
               Dead time diminishes effective T   
               T must not limit the network
               T&gt;M (remain consistently Memory BW bound)   That is the time to do a key comparison and emission is always faster than memory RW time   
               Thousands of independent sequential memory streams sustainable at optimal rate
               Generally not a trivial assumption, in terms of practical queuing latencies, contention, etc. on a memory fabric   Susceptibility to issues can diminish overall performance substantially   
               
         
           
         
       
     
       Merge Sort Tree 
       [0000]    
       
         
           
             Each cone
           Fixed dimensions, variable input length   Binary merge sort network in core   One “pass” with W inputs of key lists
               Length (L) of each input list depends on Level number i (0&lt;=i&lt;Z)   L=W i      
               Throughput T   Depth of cone D=log 2 (W)+1   Number of m-nodes (PEs?) in cone
               2 (W+1) −1 (not illustrated)   
               
         
             Entire tree (after all passes)
           Number of levels Z=ceil(log 2 (N)/D)   Each level ends up reading all N keys, for complexity
               Z*N=N cell(log(N)/D)=N ceil(log(N)/(log(W)+1))   
               Space complexity is 2N
               Alternate memory buffer O(N) each level   
               
         
             Total time
           N*Z*K/(M/2)   
         
             Key rate R
           R=N/(N*Z*K/(M/2))=M/(2*K*Z)=M/(2*K*ceil(log(N)/(log(W)+1)))   Practical adjustment   64-byte DRAM line packs 4 keys   So L=C*W i  where C˜4   Implies very first level of first-level cone must sort (mod 4) keys together, prior to beginning conventional merge sort   Slight asymmetry of first-level cone, and T loss, but probably not too bad   All outputs&gt;4 keys, so pack normally   
         
           
         
       
     
       Merge Sort Data Perspective 
       [0000]    
       
         
           
             Binary progression per level
           Alternating blocks (lists) of locally sorted results, where block size (=L) increases   Final block is size L=N (pad accordingly) and results are complete   
         
             Alternating memory buffer 2N is simple way to produce/consume 
           
         
       
     
       Examples Assumptions 
       [0000]    
       
         
           
             Example
           M˜=46 GB/s (4 channels DDR4@ 1800, de-rating 20% for inefficiencies)   W=2 10  
               So D=11   Total m-nodes per cone=2047   
               R˜450 M/s   No more than˜450/64=7× performance over×86 approach   Probably need 4 channels DDR4@ 2400 to reach (max) 10× performance
               Note: Does not account for future×86 rate running with like DRAM   Could be less than 10× improvement   
               Another way may be to increase W→2 14  (core costs?&gt;=32K m-nodes (&gt;PEs?))   
         
             Again assumes
           Key packing makes first level slightly asymmetrical, possibly smaller T   High per-pass efficiency   Memory BW bound (&gt;=2 10  independent input lists stream optimally)
               Generally non-trivial assumption (queuing latencies, contention, etc. can have huge impact)   PEs can be clustered to form  2047  m-nodes within cone   
               Internal flow is non-limiting through tree   
         
           
         
       
     
         [0117]    The  FIGS. 3A-3B  are now discussed as embodiments, presented herein for the hardware sorted merge approach. 
         [0118]    Address space partitioned statically, extrinsically in powers of 2, with optional stride, fetched in W lists per physical cone implemented. List length: L=W i  for level iCone depth: D=log(W)Number of levels: Z=┌log(N)/D┐μ sorter throughput: TMemory BW: M (subject to interface-dependent 2×) 
         [0119]    Key size: K 
         [0120]    Each Level sees N elements 
         [0121]    Total comparisons O(N log N) 
         [0122]    Generally skew-tolerant. Stability implementation choice (determinism), inexpensive either way 
         [0123]    Amenable to block compression schemes. Inter-Level Memory may be structurally distinct (extended system topologies) 
         [0124]    Simple time bound: N.Z.max(1/T, K/M) 
         [0125]    Memory complexity: 2N (in-situ is plausible at ˜N) 
         [0126]    (compression would reduce by factor) 
         [0127]    Example Physical Implementation: Assume 2×32-Cones handling 16-byte Keys@200 MHzsorting total 220 keys. Assume small cache line (64B) 4-Key pre-cone sort (≧1 Key/Clock) only used for Level O. 
         [0128]    Multitple sort frontiers maintained through pipelining to maximize utilization of Cone intra- and inter-Levels. Naturally exploits localized parallelism and connectivity, favoring HW factors such as routability and resource costs. 
         [0129]    Lower bound on time: 2 20 [3/(2*200 10 6 )+1/(200 10 6 )]=13.1 ms Required Memory BW (Max):2*(16*200 10 6 )=˜6.4 GB/s per direction, 3 of 4 Levels Example (est.) resource requirements (for cones alone):32*6*16*8=24K Flops/cone (48K total)(Compare 1×64-Cone at 15.7 ms, same area) 
         [0130]    The  FIGS. 4A-5D  provide additional depiction of he HW wide-key sort approach discussed herein. 
         [0131]    Specifically, an implicit key domain is induced from original data set D (as shown in the  FIG. 4A ), which assumes a meaningful row space, of which r is an element, and mapping function f(r). Note that f(.) as noted in the  FIGS. 4A-4D  implicitly includes D in its domain. “Wide key” denotes keys wider than a primitive sort capability. The sorted output are keys but could also be represented indirectly by, for example, row identifiers of the original row space. 
         [0132]    In the  FIG. 4B , the Key Domain includes original row space association (r). Wide-key sort process iterative, ala radix, over key hashes h j (.), which may be, e.g., a simple window from Most-Significant Bit (MSB) to Least-Significant Bit (LSB), depending on application. Results, conceptually, are lists R j  composed of row identifiers sorted according to original key order, for distinct keys in h j-1  (.) for non-distinct keys, a group identifier (g j,i  usually consecutive starting from 0) is assigned, in directing to next list R j+1 . Effectively fixed-point recursion, until all keys are distinct (up to iteration M) where M is bounded proportional to key width but may be minimized by this adaptive approach. In-order traversal beginning with R 1  gives sorted result. 
         [0133]    In the  FIG. 4C , iterative sort passes essentially unroll in pipeline-parallelizable form, as individual groups are established. K j  is a list of input sort keys, generally denoted as K j ={G j , h j (f(R j ′), with G 0  empty. T j  is a mapping of group identifiers (g j ), implicit in to original row space, which corresponds with the row identifiers of non-distinct keys (R j ′) from pass j-1. Note the G i  may be represented in various ways, e.g., as literal values, repeating one for each non-distinct key&#39;s RID in a group, or as a single delimiter qualifying a subset of row identifiers (a subset of R j ′). G j  is a list of group identifiers implicit in R j , comprising the mapping I j ′. R j ′ is a list of Row Identifiers (RIDS) from the original row space, where prime indicates RIDS corresponding with the row identifiers of non-distinct keys identified in pass j-1. R j  is a list of result elements, each of which may be either 1) RID from the original row space (sorted by the original Key Domain), or 2) group size and offset reference into R j+1 . Note that group identifier may be implicit and consecutive, starting from 0 on each pass. Note also that the initial list R 0 ={0. . . N−1}, is trivial and may be implicit in the implementation. The depicted triangle with the sub-j is a mapping of group identifiers implicit in R j-1  to two values, an arithmetic adjustment of group offset and size, as the group occurs in list R j . Note that adjustment sets are an optional space optimization for packing group output. The final result induced by in-order traversal of sorted lists {R 1 , R 2 , . . . R M+1 ), in the manner of a stack machine, following group size and offset into successive lists, beginning at the start of R 1 . Group offset and size adjustments (depicted triangle sub-1 through depicted triangle sub-M+1), if implemented are utilized at each transition from R j  to R j+1 ; transitions from R j+1  to R j  occur according to size and current stack machine trace. 
         [0134]    In the  FIG. 4D , collision detect and compute processing occurs at the end of each complete sort pass. These processes may proceed in, e.g., a pipelined-parallel fashion having only minor data and control dependencies. The depicted triangle sub-J+1 may or may not be implemented as a space optimization, through the details discussed below assume and also include such space optimization. For every distinct K j , R J+1  includes the associated row identifier (RID); non-distinct keys are collected, sized and grouped and a predicted offset into R j+2  is based on a (e.g. cumulative) tally. T J+1  includes the chosen group identifier mapping to each associated RID in the group of non-distinct keys, which may be implemented by, e.g., a delimiter or a 1:1 mapping. For every distinct group identifier in Gj, the depicted triangle sub-J+1 includes a size and offset adjustment, representing the reduction in size of R j+1  due to non-distinct keys in the group being replaced by a size/offset reference and an offset reduction that is the cumulative size reduction over all previous groups in G j , respectively. Note that this means for the first group identifier in G j  (j&gt;0) may have a non-zero size adjustment, but its offset adjustment will always be 0. The depicted triangle sub-1 is formed from the empty G 0 , includes only the trivial zero size and offset adjustment for its first (and only) group identifier mapping. App processing maintains order of the sorted key input K j , in conjunction with the order input G j  when non-empty (i.e., J&gt;0). Note the sort pass may include R j ′ as low-order part of sort key, if stronger determinism is desired or configured in the processing. 
         [0135]    The processing depicted in the  FIGS. 4A-4D  illustrate a number of beneficial features. The sort approach adapts according to redundancy in the Key Domain, minimizing M as much as possible, where the time complexity is proportional both to M and degree of redundancy. Generally, additional parallelism, e.g., additional HW may be employed to mitigate effects of these factors. More may be said of cost-based models, but essentially bounded above by a linear combination of the cost functions, one function per Sort Pass; and below by the maximum of the same. Any such algorithm is subject to statistical properties of Key Domain and original Data Set on which the domain is based increased redundancy generally leads to larger M), For example, information entropy of the Data Set below a certain threshold will correlate with greater redundancy and larger M. Simple, sufficient characterization metric may also be deployed, assuming entropy threshold is insufficient, as this may be dependent on many factures, including the nature of f(.). Moreover, the approach presented provides opportunities for pipelined-parallelism lending to more efficient implementations. Utilizing sequential lists during the sort process permits optimal scheduling of data accesses, where external memory may be in use, while permitting high-level streaming, dataflow, and network-based implementations. Of the sort process, only h i (f(.)) need be random access in nature, which may employ advanced scheduling, caches, etc., to mitigate possible latency. Results are comprised of simple list and mapping structures which allow a stack machine to employ, e.g., advanced scheduling, caches, etc. to mitigate any random access latency in interpreting the final sorted result. Depending on sorting requirements, characteristics of the Key Doman, and Sort Pass implementation, h i (.) may vary in size varying j, or may traverse the keys in different permutations, e.g., from LSB to MSB, instead of MSB to LSB (numeric vs. text sort, etc.). Similarly, masking may be employed to accommodate, e.g., variable-length keys. Low-level sort is depicted as a full cone of “Sorted Merge Sort,” which is one implementation possibility, alternative sort primitives are supported all the same. R i  size and offset components, and their respective adjustments (depicted triangle sub-j), may be represented in many ways, the simplest being small fixed-width integers (e.g., consistent with RID size) with a delimiter bit, adjustments being signed or unsigned by convention. 
         [0136]    The above description is illustrative, and not restrictive. Many other embodiments will be apparent to those of skill in the art upon reviewing the above description. The scope of embodiments should therefore be determined with reference to the appended claims, along with the full scope of equivalents to which such claims are entitled