Patent Publication Number: US-10783102-B2

Title: Dynamically configurable high performance database-aware hash engine

Description:
FIELD OF THE DISCLOSURE 
     This disclosure relates to hash engine hardware. Techniques are presented for achieving software configurability and sustaining real time throughput. 
     BACKGROUND 
     Hash functions are used in network and database processing and cyclic redundancy checks (CRC). Different applications have different processing throughput requirements. Some networking applications require a hash to be performed in real time at data-rate speeds. Such hashing may be done on a network packet basis and may be conducive to hardware acceleration. In lower bandwidth applications, where either the amount of data to be hashed is minimal in comparison to the overall amount of processing or where a hash is infrequently required, hardware acceleration is typically not used. In these applications, software running on a processor core may perform a hash using the core itself. In some cases, the core may have a CRC instruction that facilitates hash calculations. The data to be hashed is provided as an argument to the CRC instruction, and the resultant CRC is stored in a processor output register. The application can hash more data by issuing the CRC instruction multiple times, using the existing CRC as a partial hash to start with and additional data as an argument to the CRC instruction. 
     In database applications, a hash may need to be calculated for each row of a table, and may be performed on one or more key columns of the table. For example, a database may use hashing for an index or a join operation. Previous solutions for calculating a hash on table data involved doing either of the following two techniques. In the first technique, software loads the key columns into memory and applies a hash function using a general-purpose processor core. This could be done with either specialized hash instructions or logical/arithmetic operations. In the second technique, software packs the elements of a row to be hashed into a data structure and then feeds the data structure into a hash coprocessor and/or uses a general-purpose processor to perform the hash. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       In the drawings: 
         FIG. 1  is a block diagram that depicts an example hash engine that configures hardware to sustain real-time hashing throughput, in an embodiment; 
         FIG. 2  is a flow diagram that depicts an example process that configures hardware to sustain real-time hashing throughput, in an embodiment; 
         FIG. 3  is a block diagram that depicts an example hash engine that coordinates the loads of parallel hash lanes, in an embodiment; 
         FIG. 4  is a block diagram that depicts an example computer that hashes database columns in real time, in an embodiment; 
         FIG. 5  is a block diagram that depicts an example hash engine that hashes network packets in real time, in an embodiment; 
         FIG. 6  is a block diagram that depicts an example computer that routes content based on real-time hashing, in an embodiment; 
         FIG. 7  is a block diagram that depicts an example hash engine that may preempt and resume real-time hashing, in an embodiment; 
         FIG. 8  is a block diagram that depicts an example hash engine that uses descriptors for software configurability, in an embodiment; 
         FIG. 9  is a block diagram that depicts an example hash engine that adjusts a column pointer, in an embodiment; 
         FIG. 10  is a block diagram that illustrates a computer system upon which an embodiment of the invention may be implemented. 
     
    
    
     DETAILED DESCRIPTION 
     In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention. 
     Embodiments are described herein according to the following outline:
         1.0 General Overview   2.0 Example Computer   3.0 Example Hash Lane Process   4.0 Coordinated Loading of Hash Lanes   5.0 Database and DMA   6.0 Packet Sniffing   7.0 Content Routing   8.0 Seeding and Resumption   9.0 Descriptors   10.0 Progress Pointer   11.0 Hardware Overview
 
1.0 General Overview
       

     Techniques are provided for configuring and operating hardware to sustain real-time hashing throughput. In an embodiment, during a first set of clock cycles, a particular amount of data items of a first data column are transferred into multiple hash lanes. During a second set of clock cycles, the same particular amount of data items of a second data column are transferred into the hash lanes. The particular amount of data items of the first and second data columns are then processed to calculate a set of hash values. When combined with techniques such as pipelining and horizontal scaling, the loading, hashing, and other processing occur in real time at the full speed of the underlying data path. For example, hashing throughput may sustainably equal or exceed the throughput of main memory. 
     Downstream routing of content may be based on a calculated hash value. Applications include database scans and joins and network packet sniffing. 
     Within the hash engine, the throughput of parallel hash lanes may be aggregated. If the data stream naturally contains rows, such as from a table or other source of records, then data items (column values) of a same row are loaded into a same hash lane of several lanes. 
     Descriptors may be used to achieve software configurability of column loading and hashing. A progress pointer may be adjusted to keep track of which data items will next be loaded into a hash lane. Partial hashes across part of a row of a table can be calculated and stored, and then completed and/or resumed when additional columns of the row are fed into the hash lane. This may include preempting work in progress that gets resumed at a later time. Additional flexibility can be achieved by hashing with a configurable seed when the hash of a row begins. 
     2.0 Example Computer 
       FIG. 1  is a block diagram that depicts an example hash engine  100 , in an embodiment. Hash engine  100  has dedicated hardware of high-performance hash lanes that hash data in real time. 
     Hash engine  100  may be a combination of at least one integrated circuit that accepts bulk content, such as a data stream. Hash engine  100  processes a fixed amount of the content during each hardware clock cycle to calculate or adjust at least one hash value. 
     Hash engine  100  has implementation flexibility, especially with regard to packaging and form factor. For example, hash engine  100  may be part of a general-purpose computer, such as a rack server, a personal computer, a mainframe, a smartphone, or other computer enclosure. Hash engine  100  may instead be part of a dedicated appliance or other device, such as a router or other network element, a disk controller, a host adapter, a disk array controller, a hardware accelerator, a stream encoder, or an encryption device such as a secure cryptoprocessor. 
     Hash engine  100  has fabrication flexibility. Hash engine  100  may be part of a system on a chip (SoC), may be self-contained within its own chip or package of chips, or as discrete components of varied fabrication integration. Hash engine  100  may be mounted on a printed circuit board (PCB) along with, or as part of, a controller, a microcontroller, a microprocessor, or a digital signal processor (DSP). 
     In an embodiment, hash engine  100  may process machine instructions or microcode. In another embodiment, hash engine  100  operates without instructions, and instead uses an application specific integrated circuit (ASIC) or other dedicated circuitry. 
     The content that hash engine  100  processes may be logically arranged into columns, such as A and B. Each column contains a set of data items or values. 
     Each column has a data type that all of the data items of the column conform to. For example, data types may be integers, real numbers, booleans, characters, character arrays, or other common data types such as primitive data types. 
     Each data type has a respective width or amount of bytes of memory needed to store a single data item of a column of that data type. Column A needs one byte, such as byte A 1 . 1 , to store a data item. 
     Column B needs four bytes, such as bytes B 1 . 1 -B 1 . 4 , to store a data item. For example, column B may store a machine-word integer. Depending on the capacity of hash engine  100 , a column may have a larger data type, such as a double-precision floating-point number that has eight bytes. 
     Although only columns A-B are shown, hash engine  100  may process content having more columns. For example, hash engine  100  may process a batch of content having two columns as shown, and then later, although not shown, process another batch of another content stream having more or fewer columns and columns of other data types with other widths. The maximum column width and the maximum amount of columns depends on the implementation. 
     In this example, the data items of columns A-B are arranged as rows, such as records or other tabular data, perhaps from a database table. As shown, the column data has two rows,  1 - 2 . 
     Initially, columns A-B may reside in memory. The data items of columns A-B may be comingled within one memory region, such as with row-major storage. 
     Alternatively, columns A and B may be stored as separate column arrays, such that the data items of column A occupy one memory region, and the data items of column B occupy a different memory region. Column arrays may implement column-major storage. 
     The purpose of hash engine  100  may be to hash data so rapidly that the hash engine may process a data stream in real time. Because a single hash lane may not have sufficient processing bandwidth required for an application, hash engine  100  has multiple hash lanes  110 - 111  that operate in parallel to combine their throughput. 
     At time T 1 , data is loaded into hash lanes  110 - 111 . The hash lanes may be more or less identical. Hash lane  110  may be a processing unit that performs hash calculations in real time on a data stream. 
     In this example, time T 1  spans hardware clock cycles  1 . 1 - 1 . 2  and  2 . 1 - 2 . 8 . During each clock cycle, either or both of hash lanes  110 - 111  processes a byte of data. 
     If a data item has more than one byte, all of its bytes are eventually processed by a same hash lane. Data items A 1  and B 1  are for a same row. As such, all of the bytes of data items A 1  and B 1  are loaded into and processed by a same hash lane, such as shown in  110 . 
     Hash lanes  110 - 111  may be synchronized by a shared clock signal. Likewise, hash lanes  110 - 111  both may update their respective hash values  120 - 121  with a shared clock frequency. 
     Because a data item may have multiple bytes, hash lane  110  may need multiple cycles to process one data item of one column. 
     For example, data item B 1  of column B has data bytes B 1 . 1 -B 1 . 4 , which take four cycles ( 2 . 1 - 2 . 4 ) to be processed by hash lane  110 . During cycles  2 . 5 - 2 . 8 , the bytes (B 2 . 1 -B 2 . 4 ) of data item B 2  are processed by hash lane  111 . During cycle  1 . 1 , sole byte A 1 . 1  of data item A 1  of column A is processed by hash lane  110 . 
     After time T 1 , bytes A 1 . 1  and B 1 . 1 -B 1 . 4  reside within hash lane  110 , and bytes A 2 . 1  and B 2 . 1 -B 2 . 4  reside within hash lane  111 . However not all of these bytes need reside within hash lane  110  or  111  simultaneously. 
     In an embodiment, only one data byte resides within hash lane  110  at a time. In another embodiment, hash lane  110  includes registers, a first-in first-out (FIFO), or other memory that holds one or more additional bytes that await individual processing. 
     At time T 2 , hash lane  110  emits hash value  120 . For example, hash lane  110  may process a data byte, such as A 1 . 1  during cycle  1 . 1 , to calculate hash value  120 . 
     Hash lane  110  calculates hash value  120  by applying a hash function to the data byte. For example, the hash function may be cryptographic (such as MDS, SHA-1, or RIPEMD-160), a checksum, a fingerprint, an error detection or correction code, or other data mapping function. 
     Hash value  120  may operate as an accumulator. For example, the hash function may update hash value  120  based on a combination of the prior value of hash value  120  and the current data byte value currently being processed. 
     Although times T 1 -T 2  are shown as separate times, depending on how the hash function is organized and pipelined, times T 1  and T 2  may overlap. For example, during one cycle hash lane  110  may simultaneously hash several data bytes that have been loaded into the hash lane. 
     For example, during one cycle, bytes B 1 . 3  and B 1 . 4  may be loaded into hash lane  110  while bytes B 1 . 1  and B 1 . 2  are being hashed into the current accumulated hash value  120  which is based on the hash value of byte A 1 . 1 . Such pipelining allows the overall hash function to be broken up into smaller processing pieces which can increase hash bandwidth/throughput by allowing the cycle time to be reduced. 
     In an embodiment, hash lane  110  hashes one byte per cycle. In another embodiment, hash lane  110  hashes multiple bytes per cycle. 
     In an embodiment, how many bytes are processed by hash lane  110  per cycle is software programmable. In an embodiment, the hash function is software programmable. 
     In an embodiment, hash lane  110  emits each raw (unhashed) data byte, for downstream consumption. For example, hash engine  100  may be part of a disk controller that provides data to a client by reading the data from disk, hashing it, and forwarding the raw bytes to a controller buffer for eventual transfer to main memory. As such, hash engine  100 , including hash lane  110 , may be elements of the primary data path. 
     In an embodiment, hash lane  110  does not emit raw data. Instead, hash engine  100 , including hash lane  110 , receive one fork (copy) of the data stream, while the client receives another fork of the same stream. As such, hash lane  110  may be the end of a side branch that discards content after hashing it. 
     In an embodiment, hash lanes  110 - 111  may be loaded with data simultaneously. For example, clock cycles  1 . 1  and  1 . 2  may be a same cycle. In another embodiment, additional synchronization of hash lanes  110 - 111  avoids contention by including alternating turns to load data from a shared resource, such as memory or a data bus. 
     For example although hash lanes  110 - 111  simultaneously perform their individual hash calculations, each of hash lanes  110 - 111  may have a data buffer into which input data is loaded in small batches of data items. Hash lane  110  may have four bytes loaded during one set of clock cycles, while hash lane  111  is not loaded. 
     However during that set of cycles, both hash lanes  110 - 111  hash data that that were loaded earlier. In a next set of cycles, the roles may reverse, with hash lane  111  loading data into its buffer, and hash lane  110  not loading. 
     As shown, both hash lanes  110 - 111  load different rows from the same columns of a same original data stream, perhaps as part of processing a same file retrieval or database query. In another example, each of hash lanes  110 - 111  is dedicated to a separate data stream for a separate client request. For example, hash lane  110  may process one data stream retrieved from a file, and hash lane  111  may process another data stream from a database. 
     To avoid attempts to load a same input row, hash lanes  110 - 111  may be hardwired or programmable to load particular rows. For example, hash lane  110  may load odd rows, and hash lane  111  may load even rows. In an embodiment, hash lanes  110 - 111  share metadata that indicates which rows are already loaded, which rows are available for loading, or which hash lanes are currently loading which rows. 
     In an embodiment, the raw data loaded into hash lanes  110 - 111  may be joined into a combined output stream for downstream consumption. As such the rows may or may not be reordered. 
     In an embodiment, hash engine  100  may enter a low-power mode when not in use. In an embodiment, an individual hash lane may enter a low-power mode when not in use. 
     3.0 Example Hash Lane Process 
       FIG. 2  is a flow diagram that depicts an example hash lane process that uses dedicated hardware of high-performance hash lanes to hash data in real time, in an embodiment. This hash lane process is described in the context of  FIG. 1 . 
     Steps  201 - 202  occur during a first set of clock cycles, in which an amount of data items of a first data column are transferred into each of multiple hash lanes. For example during cycles  1 . 1 - 1 . 2 , data bytes A 1 . 1  and A 1 . 2  are loaded into hash lanes  110 - 111  as two data items from column A. 
     Although not shown, step  201  may transfer multiple data items. For example if hash lane  110  has a storage capacity of sixteen bytes, and each data item of column B has four bytes, and hash lane  110  processes one byte per cycle, then 16/4=four data items may be loaded into hash lane  110  during a first set of 16/1=sixteen cycles. Whereas, if hash lane  110  processes two bytes per cycle, then only 16/2=eight cycles are needed to process the same sixteen bytes of data. 
     In an embodiment, one data item per clock cycle is transferred into hash lane  110 . In the shown embodiment, each hash lane has one hash accumulator (not shown). For example, hash lane  110  has one accumulator, and the accumulator calculates hash value  120 . For each data item transferred for a given column, hash lane  110  may need a separate accumulator. With one accumulator per lane, one data item is transferred into each hash lane from each column before transferring another data item from a different row into hash lane  110 . 
     Steps  203 - 204  occur during a second set of clock cycles, in which the same amount of data items of a second data column are transferred into the hash lanes. For example during cycles  2 . 1 - 2 . 2 , data bytes B 1 . 1 -B 1 . 4  are loaded into hash lane  110  as one data item from column B, and data bytes B 2 . 1 -B 2 . 4  are loaded into hash lane  111  as one data item. If step  201  transferred four data items, the step  203  would also transfer four data items. 
     In step  205 , the data items that were transferred into the hash lanes during steps  201 - 204  are processed to calculate at least one hash value. For example, hash lane  110  hashes bytes A 1 . 1  and B 1 . 1 -B 1 . 4  to calculate hash value  120 . During this step, hash lane  111  may also calculate hash value  121 . 
     Hash value  120  is available to downstream consumers. For example, if hash value  120  is a cyclic redundancy check (CRC) code, then an operating system may read hash value  120 , after it has accumulated results for all bytes of a file, to determine whether file integrity has been compromised. 
     Although only one hash value per hash lane is shown in  FIG. 1 , hash lane  110  may have multiple hash values. In an embodiment, each of multiple hash values is calculated by a distinct hash function. For example, each hash value may be calculated by a CRC hash function having a different polynomial. For example, each column may have its own accumulator and hash value for a same hash lane. 
     Hash value  120  may be an accumulator that is updated as hash lane  120  processes each byte or set of bytes. In an embodiment, step  205  may overlap with steps  201 - 204 . For example, step  201  may transfer multiple bytes, one at a time, and hash lane  110  may hash an earlier byte while a later byte is being transferred. 
     4.0 Coordinated Loading of Hash Lanes 
       FIG. 3  is a block diagram that depicts an example hash engine  305 , in an embodiment. Hash engine  305  increases throughput by coordinating loading of hash lanes to achieve pipelining, 
     Hash engine  305  may be an implementation of hash engine  100 . Hash engine  305  includes parallel hash lanes  301 - 302  and column memory  306 . 
     Hash engine  305  processes a data stream that is naturally organized into rows that span columns A-C. The data stream is buffered in column memory  306 , which may be an on-chip memory such as static RAM (SRAM). 
     Within column memory  306 , the data stream has column-major storage, such that each of columns A-C is a column array. Within column memory  306  are at least rows  1 - 2  of each column A-C. 
     Column A is two bytes wide. Column B is four bytes wide. Column C is one byte wide. For example, row  1  of column A has data bytes A 1 . 1  and A 1 . 2 . 
     Hash engine  305  has special operational constraints that enable it to coordinate the loading of data into hash lanes  301 - 302 . These constraints are as follows. 
     All of the bytes of a row are loaded into a same hash lane. For example, row  1  has bytes A 1 . 1 -A 1 . 2 , B 1 . 1 -B  1 . 4 , and C 1 . 1 , all of which are loaded into hash lane  301 . 
     As shown, hash engine  305  loads data into the hash lanes during a timeline that spans seven clock cycles T 1 -T 7 . During each cycle, hash engine  305  loads a fixed amount of bytes into the hash lanes. 
     In this example, hash engine  305  loads two bytes per cycle. For some columns, exactly one data item may be loaded during a cycle. For example during T 1 , hash engine  305  loads data item A 1  (bytes A 1 . 1 -A 1 . 2 ) into hash lane  301 . 
     For a wide column, a data item may need multiple cycles to load. For example, loading two bytes per cycle requires two cycles to load a four-byte data item. 
     For example, data item B 1  is loaded during cycles T 3 -T 4 . Bytes B 1 . 1 -B 1 . 2  are loaded during cycle T 3 . Bytes B 1 . 3 -B 1 . 4  are loaded during cycle T 4 . 
     For a narrow column, multiple data items may be read from column memory  306  and loaded into multiple hash lanes during one cycle. For example, data items C 1 . 1 -C 2 . 1  are loaded during cycle T 7 . 
     A narrow column may also be loaded into multiple hash lanes during one cycle. For example, data items C 1 . 1 -C 2 . 1  are loaded into hash lanes  301 - 302  during cycle T 7 . 
     Data items may be read from column memory  306  and loaded into the hash lanes in batches to reap the efficiencies of a bulk transfer. However, a block transfer may need contiguity of bytes. 
     The bytes of any one column array, such as column A, B, or C, may be contiguous. However, multiple column arrays A-C are not guaranteed to be contiguous with each other within column memory  306 . 
     Therefore, a block transfer from column memory  306  into the hash lanes may be limited to a single column. For example, cycles T 3 -T 6  may be dedicated to transferring data exclusively for column B. 
     An amount of cycles needed to accomplish a block transfer may depend on a column width. For example, column B may need four (T 3 -T 6 ) cycles for a block transfer. Whereas, column C may need only one cycle, T 7 , for a block transfer. 
     A same amount of data items may be transferred during a block transfer, regardless of column width. For example, the block transfers of any of columns A-C may each include two data items. 
     In a preferred embodiment, the combined bandwidth of hash lanes  301 - 302  matches the bandwidth of column memory  306 . Matching bandwidth can be achieved by having an optimal number of hash lanes. 
     In a preferred embodiment, the input and output data rates of hash engine  305  are identical and constant. In this example, hash engine  305  loads two bytes per cycle, hashes two bytes per cycle, and may emit two content bytes per cycle. However in this example, each individual hash lane, such as  301 , only has capacity to hash one byte per cycle. As such, both hash lanes  301 - 302  are needed for the aggregate hashing of hash engine  305  to keep pace with data delivered from column memory  306 . Whereas, a preferred embodiment (not shown) each hash lane may hash four content bytes per cycle. 
     In this example, if hash engine  305  had only one hash lane, then hashing rows  1 - 2  would take twice as long to process, which would be fourteen clock cycles, instead of at full memory speed, which otherwise could deliver rows  1 - 2  in only seven cycles, as shown. For example, what appears to be bubbles/stalls (shown as empty cells, such as at T 2  as shown) in hash lane  301  are not actually bubbles/stalls. 
     Instead hash lanes  301 - 302  as configured actually have a full hashing load. For example, although data item A 1  (bytes A 1 . 1 -A 1 . 2 ) is delivered to hash lane  301  in a single cycle, hash lane  301  may need two cycles to hash bytes A 1 . 1 -A 1 . 2 . 
     As such two hash lanes are needed to keep pace with column memory  306 . Likewise, if hash engine  305  had more than two hash lanes, then some hash lanes may be sometimes or always idle. 
     According to those operational constraints, hash engine  305  uses parallel hash lanes to aggregate bandwidth, uses pipelining to achieve higher performance, and uses block transfers to boost throughput. These constraints achieve a coordination of hash lanes, as evident by the visually apparent stair-step patterns shown within hash lanes  301 - 302 . Hash engine  305  may have a sequencer module that imposes this coordination. 
     The hardware modularity of hash engine  305  also confers design flexibility. For example, horizontal scaling may be achieved by adding more hash lanes. Likewise, vertical scaling may be achieved by increasing the capacity of a load cycle. For example, if loading two bytes per cycle into the hash lanes is inadequate (such as for hash lanes that each hash four bytes per cycle), then the load circuitry may be expanded to instead load four bytes per cycle. 
     Some combination of horizontal and vertical scaling may be sufficient to sustain throughput which matches or exceeds that of external memory and/or the throughput required by the application. In this way, hash engine  305  can be predictably calibrated for insertion directly into a general-purpose data path without impacting throughput. 
     5.0 Database and DMA 
       FIG. 4  is a block diagram that depicts an example computer  400 , in an embodiment. Computer  400  has an input data path that streams input data from database  430  on disk, through memory, and into hash engine  460 . Hash engine  460  may be an implementation of hash engine  100 . 
     Computer  400  includes dynamic random access memory (DRAM)  440 , direct memory access (DMA) channel  450 , database  430 , and hash engine  460 . Database  430  is on disk or remote. 
     Database  430  contains columns A-B of a table. Throughput is increased if columns A-B are stored within database  430  in column-major format. 
     Perhaps in response to a query, computer  400  copies some or all of columns A-B into DRAM  440 , which may be a main memory and may optionally provide column-major storage. DRAM  440  may be a dual data rate (DDR) DRAM, a reduced-latency DRAM (RLDRAM), or any bulk memory whether dynamic, static, or non-volatile. 
     As shown, hash engine  460  has two lanes. Hash engine  460  may use a direct memory DMA channel, such as  450 , of a DMA controller to use a block transfer to load data from DRAM  440  into a hash lane or on-chip memory, such as a cache or local SRAM. In an embodiment, hash engine  460  may centrally orchestrate block transfers into hash lanes. In another embodiment, each hash lane temporarily acquires or permanently owns a DMA channel that it uses to fetch data to process. 
     In an embodiment, the peak bitrate of DRAM  440  does not exceed the peak bitrate of hash engine  460 . In this embodiment, hash engine  460  sustainably processes the content stream in real time. 
     Hash engine  460  applies a hash function that may have special relevance to database applications. For example, the hash value that a hash lane calculates may be used as a key for a hash join that perhaps implements a join clause of a structured query language (SQL) query. In another example, the hash value may be used to implement a filtration criterion, perhaps as part of a where clause of an SQL query. In another example, the hash value may have desirable spreading characteristics and may be used to partition rows of a table to different processors in a multi-core processing system. 
     For example, a compound criterion may select people (rows) having an adult age (column A) and living in a given zip code (column B). A hash function may be applied to the two columns to provide a hash value. In some applications, extracting a single-bit from a calculated hash value may be used for filtration or other binary decisions. 
     In this case, a downstream application (or logic associated with the hash engine itself) could read the hash value for a current row to decide whether the row should be selected or filtered out. As such, the hash value would not be an accumulator, but would instead be recalculated from scratch for each row. 
     6.0 Packet Sniffing 
       FIG. 5  is a block diagram that depicts an example hash engine  500 , in an embodiment. Hash engine  500  has an input data stream that arrives over a network. Hash engine  500  may be an implementation of hash engine  100 . 
     The input data stream is organized as rows, and each row arrives in its own network packet, such as  561 - 562 . Packets  561 - 562  may be internet protocol version 4 (IPV4) packets. 
     In one example, a row is extracted from an interesting portion(s) of a packet payload. For example, an IPV4 packet commonly has a 20-byte header having multiple control fields and a body (payload). 
     A computer may extract the body or some or all of the header for loading into the hash engine or memory as one row. Alternatively, each entire packet or packet body may be a row. 
     In another example, packets  561 - 562  are Ethernet frames. Each frame may contribute interesting fields to a row, such as the preamble, MAC address, or payload. 
     Regardless of protocol, packets  561 - 562  likely bear an error detection code such as a CRC code or checksum. If it has a CRC code, the hash engine may recalculate the CRC code based on the content of the packet to check whether the recalculated CRC code matches the sent CRC code. 
     In another example, the hash value may be read to determine a packet classification, such as a particular protocol (e.g. TCP or UDP), an application type, or a user session. Hash engine  500  may be part of a packet sniffer, which may facilitate a firewall, a router, a traffic analyzer, an intrusion detector, or a governor of quality of service (QoS). 
     7.0 Content Routing 
       FIG. 6  is a block diagram that depicts an example computer  600 , in an embodiment. Computer  600  has a hash engine that performs routing, such as load balancing. The hash engine may be an implementation of hash engine  100 . 
     The hash engine may be part of a high-performance data path. The stream of content may have such high bandwidth that a downstream uniprocessor that analyzes, processes, or otherwise consumes the stream would be overwhelmed. 
     Computer  600  may have multiple processing cores, such as  641 - 643 , that each consumes some of the content stream. Although an individual core may have insufficient bandwidth, the combined bandwidth of cores  641 - 643  is sufficient to process the content stream in real time. 
     A hash lane, such as  610 , may be loaded with a record with columns A-B stored in bytes A 1  and B 1 -B 2 . Hash lane  610  may process each record to calculate hash value  620 . 
     After processing a record, hash lane  610  emits the record along with hash value  620 . The emitted record and hash value  620  may be available to select  630 . 
     Select  630  may have distinct circuitry or may be part of hash lane  610 . Select  630  may be implemented in hardware, software, or some combination of them. As such, select  630  may be software configurable. 
     Select  630  processes hash value  620  to make a content-based routing decision. For example, select  630  may apply a modulo-three operation to hash value  620  to decide which of three downstream cores  641 - 643  should consume the record. 
     Select  630  need not examine the record itself. Select  630  may signal hardware to conduct the record to whichever core that select  630  chooses based on hash value  620 . 
     In this example, content-based routing is used to distribute the load to multiple cores. In other examples, the multiple destinations of select  630  are components other than cores. 
     The destinations may be separate disks, separate network interfaces, separate buffers, separate inter-process sockets or queues, or separate applications. For example, select  630  may perform error checking based on hash value  620  and route erroneous records to one file and non-erroneous records to another file. 
     In an embodiment, select  630  implements content addressable routing. For example, computer  600  may use select  630  to stream records to different cores (or other destinations) based on column values. 
     For example, hash value  620  and select  630  may coordinate to achieve range-based routing. For example, column A may have HTTP response codes, and core  641  may receive all records with 200-series (2XX) success codes, 
     8.0 Seeding and Resumption 
       FIG. 7  is a block diagram that depicts an example hash engine  700 , in an embodiment. Hash engine  700  accepts a hash seed, perhaps to resume prior work. Hash engine  700  may be an implementation of hash engine  100 . 
     Hash engine  700  includes hash lane  710  that calculates hash value  720 . Hash value  720  may be an accumulator that may be updated for each byte that hash lane  710  processes. 
     For example, hash value  720  may accumulate a CRC code that is calculated from the byte content of a file. However, the file may be low priority and may be preempted by higher priority content, perhaps to prevent priority inversion. 
     For example, hash value  720  may be implemented with a pushdown stack. Whenever hash lane  710  is preempted by more important traffic, hash value  720  may push its current value down into the stack for safe keeping. 
     Eventually, hash lane  710  may resume processing the interrupted low-priority content. Resumption may be achieved by restoring a saved value into hash value  720 . The saved value is shown as seed value  730 . 
     Seed value  730  may be obtained by popping the stack. Alternatively, seed value  730  may be software configurable and perhaps copied from memory. 
     As such, hash engine  700  may schedule and reschedule work according to quality of service (QoS) promises. In another example, seed value  730  may not represent work to be resumed, but instead supports an algorithm that uses a seed for another purpose, as with cryptography. 
     9.0 Descriptors 
       FIG. 8  is a block diagram that depicts an example hash engine  800 , in an embodiment. Hash engine  800  uses descriptors to achieve software configurability. Hash engine  800  may be an implementation of hash engine  100 . 
     Descriptors, such as  831 - 832  and  840 , enable a hash engine  800  to be more or less data driven. This allows software configurability that achieves dynamic customization needed to switch between distinct applications. 
     If hash engine  800  or hash lane  810  includes a processor that processes microcode or other machine instructions, then there is ample flexibility to achieve dynamic customization. However, such custom coding may be tedious and error prone and may require significant processor resources. 
     As an alternative to custom coding, descriptors may simplify customization according to predetermined patterns that are parameterized. To use a descriptor, hash engine  800  or hash lane  810  must parse or otherwise digest the descriptor to extract parameters. 
     Extracted parameters are then used to configure hash engine  800  or hash lane  810 . Such extraction and configuration may be performed directly by hardware or delegated to microcode or other reusable instructions. 
     Hash descriptor  840  declares aspects of hash value  820 , such as how hashing is calculated and perhaps to where downstream to transmit hash value  820 . Hash descriptor  840  may specify various details such as a seed value, an identifier of a stock hash function, a pointer to instructions of a custom hash function, whether to operate as an accumulator, at what interval to reset the accumulator between records, content priority, how to publicize hash value  820 , how to announce exhaustion of all input rows, and where to relay the raw data downstream, if at all. 
     A software application may create, populate, and submit hash descriptor  840  to hash engine  800  or hash lane  810 , depending on the implementation. In an embodiment, each hash lane may have its own hash descriptor. In another embodiment, multiple hash lanes may share a hash descriptor. 
     Each of column descriptors  831 - 832  declares aspects of a column, such as A or B. A column descriptor, such as  831 , may specify various details such as database column metadata, column data width, column data type, a pointer to column-major memory, a column offset within the rows of row-major storage, a count of rows, and an ordering relative to other columns for loading a given row into hash lane  810 . For example, column descriptors  831 - 832  may each have a unique rank that configures bytes B 1 -B 4  of column B to be loaded into hash lane  810  after byte Al of column A. 
     If hash lane  810  supports preemption, then hash lane  810  may have one or more pushdown stacks for hash descriptors or column descriptors. In an embodiment, descriptors  831 - 832  may be bundled as a unit of work that is submitted to hash engine  800 . For example, hash engine  800  may maintain a backlog queue of units of work that wait to be processed by hash engine 800. 
     10.0 Progress Pointer 
       FIG. 9  is a block diagram that depicts an example hash engine  900 , in an embodiment. Hash engine  900  maintains a column attribute that tracks the progress of a column. Hash engine  900  may be an implementation of hash engine  100 . 
     Hash lane  910  loads a same amount of data items for each column. For example, if a database table has many rows that span two columns, and hash lane  910  loads a data item (row) from the first column, then hash lane  910  will also load a data item (row) from the second column, even if the two columns have different widths and a data item takes a different amount of time to load, depending on its column width. 
     A consequence of this is that even though a same amount of data items are loaded from both columns, the amount of bytes loaded from both columns differs. If the input data has column-major storage of different widths, hash lane  910  may need to independently track its progress for each column. 
     For simplicity of depiction,  FIG. 9  shows only column B. However, the following technique may be repeated for other columns. 
     Hash lane  910  (or hash engine  900 ) maintains column attribute  930  for column B. Other columns may have separate column attributes. 
     Column attribute  930  contains pointer  940  and increment  950 . Pointer  940  is a memory pointer that indicates the memory address of a next data item or set of data items of column B to read from memory and load into hash lane  910 . 
     After reading the next data item(s), pointer  940  must be advanced to point to the next unread data item of column B. Pointer advancement involves pointer math that depends on various factors. 
     For example, if column B were one byte wide, has column-major storage, and is loaded into hash lane  910  one row at a time, then advancing pointer  940  is straightforward. In such a case, pointer  940  need only be incremented by one after each read. 
     However, if the width of column B has multiple bytes (as shown), then pointer  940  would need advancing by that column byte width after each read. Furthermore and although not shown, if hash lane  910  reads multiple data items (rows) from column B as a batch, such as two data items of four bytes each, then pointer  940  would need advancing by 2×4=eight bytes after each read. 
     As shown, hash lane  910  is loaded with one data item at a time that has four bytes. After being loaded with data item B 1  from column B, hash lane  910  may be loaded with the same amount of data items from other columns. 
     Eventually, hash lane  910  is ready to be loaded with a next data item (B 2 ) from column B. To ensure that hash lane  910  is loaded with data from the correct memory location, pointer  940  must be advanced by four bytes between reads of data items B 1  and B 2 . 
     Before this advancement, pointer  940  points to item B 1 , as shown by the solid arrow. Whereas after advancement, pointer  940  points to item B 2 , as shown by the dashed arrow. 
     Pointer advancement is further complicated by row-major storage, which comingles data items of multiple columns in memory. This complicates pointer advancement because it must account not only for data item(s) of column B, but also for any data items read for other columns, even though column attribute  930  and pointer  940  are associated only with column B. 
     For example and although not shown, a column A may be one byte wide, and a column C may be two bytes wide. As such and given that column B is four bytes wide, if hash lane  910  is loaded with one row per batch, then pointer  940  must advance 1+4+2=seven bytes after each read. Whereas, if hash lane  910  is loaded with three rows per batch, then pointer  940  must advance 7*3=21 bytes after each read. 
     Fortunately, the amount that pointer  940  must advance is constant during the processing of a given stream of columns. As such, column attribute  930  may be initialized once with increment  950  that specifies by how much pointer  940  advances after each read. After initialization of column attribute  930  and throughout the processing of the given stream, increment  950  may be immutable. 
     If hash lane  910  supports preemption, then all of the column attributes, such as  930 , for a stream may be saved on a pushdown stack or in other memory. 
     11.0 Hardware Overview 
     According to one embodiment, the techniques described herein are implemented by one or more special-purpose computing devices. The special-purpose computing devices may be hard-wired to perform the techniques, or may include digital electronic devices such as one or more application-specific integrated circuits (ASICs) or field programmable gate arrays (FPGAs) that are persistently programmed to perform the techniques, or may include one or more general purpose hardware processors programmed to perform the techniques pursuant to program instructions in firmware, memory, other storage, or a combination. Such special-purpose computing devices may also combine custom hard-wired logic, ASICs, or FPGAs with custom programming to accomplish the techniques. The special-purpose computing devices may be desktop computer systems, portable computer systems, handheld devices, networking devices or any other device that incorporates hard-wired and/or program logic to implement the techniques. 
     For example,  FIG. 10  is a block diagram that illustrates a computer system  1000  upon which an embodiment of the invention may be implemented. Computer system  1000  includes a bus  1002  or other communication mechanism for communicating information, and a hardware processor  1004  coupled with bus  1002  for processing information. Hardware processor  1004  may be, for example, a general purpose microprocessor. 
     Computer system  1000  also includes a main memory  1006 , such as a random access memory (RAM) or other dynamic storage device, coupled to bus  1002  for storing information and instructions to be executed by processor  1004 . Main memory  1006  also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor  1004 . Such instructions, when stored in non-transitory storage media accessible to processor  1004 , render computer system  1000  into a special-purpose machine that is customized to perform the operations specified in the instructions. 
     Computer system  1000  further includes a read only memory (ROM)  1008  or other static storage device coupled to bus  1002  for storing static information and instructions for processor  1004 . A storage device  1010 , such as a magnetic disk or optical disk, is provided and coupled to bus  1002  for storing information and instructions. 
     Computer system  1000  may be coupled via bus  1002  to a display  1012 , such as a cathode ray tube (CRT), for displaying information to a computer user. An input device  1014 , including alphanumeric and other keys, is coupled to bus  1002  for communicating information and command selections to processor  1004 . Another type of user input device is cursor control  1016 , such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to processor  1004  and for controlling cursor movement on display  1012 . This input device typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), that allows the device to specify positions in a plane. 
     Computer system  1000  may implement the techniques described herein using customized hard-wired logic, one or more ASICs or FPGAs, firmware and/or program logic which in combination with the computer system causes or programs computer system  1000  to be a special-purpose machine. According to one embodiment, the techniques herein are performed by computer system  1000  in response to processor  1004  executing one or more sequences of one or more instructions contained in main memory  1006 . Such instructions may be read into main memory  1006  from another storage medium, such as storage device  1010 . Execution of the sequences of instructions contained in main memory  1006  causes processor  1004  to perform the process steps described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions. 
     The term “storage media” as used herein refers to any non-transitory media that store data and/or instructions that cause a machine to operation in a specific fashion. Such storage media may comprise non-volatile media and/or volatile media. Non-volatile media includes, for example, optical or magnetic disks, such as storage device  1010 . Volatile media includes dynamic memory, such as main memory  1006 . Common forms of storage media include, for example, a floppy disk, a flexible disk, hard disk, solid state drive, magnetic tape, or any other magnetic data storage medium, a CD-ROM, any other optical data storage medium, any physical medium with patterns of holes, a RAM, a PROM, and EPROM, a FLASH-EPROM, NVRAM, any other memory chip or cartridge. 
     Storage media is distinct from but may be used in conjunction with transmission media. Transmission media participates in transferring information between storage media. For example, transmission media includes coaxial cables, copper wire and fiber optics, including the wires that comprise bus  1002 . Transmission media can also take the form of acoustic or light waves, such as those generated during radio-wave and infra-red data communications. 
     Various forms of media may be involved in carrying one or more sequences of one or more instructions to processor  1004  for execution. For example, the instructions may initially be carried on a magnetic disk or solid state drive of a remote computer. The remote computer can load the instructions into its dynamic memory and send the instructions over a telephone line using a modem. A modem local to computer system  1000  can receive the data on the telephone line and use an infra-red transmitter to convert the data to an infra-red signal. An infra-red detector can receive the data carried in the infra-red signal and appropriate circuitry can place the data on bus  1002 . Bus  1002  carries the data to main memory  1006 , from which processor  1004  retrieves and executes the instructions. The instructions received by main memory  1006  may optionally be stored on storage device  1010  either before or after execution by processor  1004 . 
     Computer system  1000  also includes a communication interface  1018  coupled to bus  1002 . Communication interface  1018  provides a two-way data communication coupling to a network link  1020  that is connected to a local network  1022 . For example, communication interface  1018  may be an integrated services digital network (ISDN) card, cable modem, satellite modem, or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface  1018  may be a local area network (LAN) card to provide a data communication connection to a compatible LAN. Wireless links may also be implemented. In any such implementation, communication interface  1018  sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information. 
     Network link  1020  typically provides data communication through one or more networks to other data devices. For example, network link  1020  may provide a connection through local network  1022  to a host computer  1024  or to data equipment operated by an Internet Service Provider (ISP)  1026 . ISP  1026  in turn provides data communication services through the world wide packet data communication network now commonly referred to as the “Internet”  1028 . Local network  1022  and Internet  1028  both use electrical, electromagnetic or optical signals that carry digital data streams. The signals through the various networks and the signals on network link  1020  and through communication interface  1018 , which carry the digital data to and from computer system  1000 , are example forms of transmission media. 
     Computer system  1000  can send messages and receive data, including program code, through the network(s), network link  1020  and communication interface  1018 . In the Internet example, a server  1030  might transmit a requested code for an application program through Internet  1028 , ISP  1026 , local network  1022  and communication interface  1018 . 
     The received code may be executed by processor  1004  as it is received, and/or stored in storage device  1010 , or other non-volatile storage for later execution. 
     In the foregoing specification, embodiments of the invention have been described with reference to numerous specific details that may vary from implementation to implementation. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense. The sole and exclusive indicator of the scope of the invention, and what is intended by the applicants to be the scope of the invention, is the literal and equivalent scope of the set of claims that issue from this application, in the specific form in which such claims issue, including any subsequent correction.