# HG changeset patch # User František Kučera # Date 1580764207 -3600 # Node ID abbc9bcfbcc4599f997d4b25117180f32e46f1c6 # Parent b862d16a2e9f22de4f26f0964d938d4dbc599f3b Release v0.15 – streamlets, parallel processing diff -r b862d16a2e9f -r abbc9bcfbcc4 relpipe-data/download.xml --- a/relpipe-data/download.xml Thu Jan 30 14:57:09 2020 +0100 +++ b/relpipe-data/download.xml Mon Feb 03 22:10:07 2020 +0100 @@ -22,7 +22,7 @@ hg clone https://hg.globalcode.info/relpipe/relpipe-in-xml.cpp; hg clone https://hg.globalcode.info/relpipe/relpipe-in-xmltable.cpp; hg clone https://hg.globalcode.info/relpipe/relpipe-lib-cli.cpp; -hg clone https://hg.globalcode.info/relpipe/relpipe-lib-protocol.cpp; +hg clone https://hg.globalcode.info/relpipe/relpipe-lib-common.cpp; hg clone https://hg.globalcode.info/relpipe/relpipe-lib-reader.cpp; hg clone https://hg.globalcode.info/relpipe/relpipe-lib-writer.cpp; hg clone https://hg.globalcode.info/relpipe/relpipe-lib-xmlwriter.cpp; @@ -57,6 +57,7 @@

Released versions

2020-01-31: v0.15
2019-10-30: v0.14
2019-07-30: v0.13
2019-05-28: v0.12

+ + Computing hashes in parallel + utilize all CPU cores while computing SHA-256 and other file hashes + 03800 + + + +

+ Using relpipe-in-filesystem we can gather various file attributes + – basic (name, size, type, …), extended (xattr like e.g. original URL), metadata embedded in files (JPEG Exif, PNG, PDF etc.), XPath values from XML, JAR/ZIP metadata… + or compute hashes of the file content (SHA-256, SHA-512 etc.). +

+ +

This example shows how we can compute various file content hashes and how to do it efficiently on a machine with multiple CPU cores.

+ +

+ Background: + Contemporary storage (especially SSD or even RAM) is usually fast enough that the bottleneck is the CPU and not the storage. + It means that computing hashes of multiple files sequentially will take much more time than it could. + So it is better to compute the hashes in parallel and utilize multiple cores of our CPU. + On the other hand, we are going to collect several file attributes and we are working with structured data, which means that we have to preserve the structure and in the end merge all pieces together without corrupting the structures. + And this is a perfect task for and especially relpipe-in-filesystem which is the first tool in our collection that implements streamlets and parallel processing. +

+ +

+ Following script prints list of files in our /bin directory and their SHA-256 hashes and also tells us, how many identical (i.e. exactly same content) files we have: +

+ + + +

+ Output looks like this: +

+ + + +

+ This pipeline consists of four steps: +

+ +

+ findFiles + – prepares the list of files separated by \0 byte; + we can do also some basic filtering here +
+ fetchAttributes + – does the heavy work – computes SHA-256 hash of each file; + thanks to --parallel N option, utilizes N cores of our CPU; + we can experiment with the N value and look how the total time decreases +
+ aggregate + – uses SQL to order the records and SQL window function to show, how many files have the same content; + in this step we could use also relpipe-tr-awk or relpipe-tr-guile if we prefer AWK or Guile/Scheme to SQL +
+ relpipe-out-tabular + – formats the results as a table in the terminal (we could use e.g. relpipe-out-gui to call a GUI viewer or format the results as XML, CSV or other format) +

+ +

+ In the case of the /bin directory, the results are not so exciting – we see that the files with same content are just symlinks to the same binary. + But we can run this pipeline on a different directory and discover real duplicates that occupy precious space on our hard drives + or we can build an index for fast searching (even offline media) and checking whether we have a file with given content or not. +

+ +

+ Following script shows how we can compute hashes using multiple algorithms: +

+ + + +

+ There are two variants: + In fetchAttributes1 we compute MD5 hash and then SHA-1 hash for each record (file). And we have parallelism (--parallel 4) over records. + In fetchAttributes2 we compute MD5 and SHA-1 hashes in parallel for each record (file). And we have also parallelism (--parallel 4) over records. + This is a common way how streamlets work: + If we ask a single streamlet instance to compute multiple attributes, it is done sequentially (usually – depends on particular streamlet implementation). + But if we create multiple instances of a streamlet, we have automatically multiple processes that work in parallel on each record. + The advantage of this kind of parallelism is that we can utilize multiple CPU cores even with one or few records. + The disadvantage is that if there is some common initialization phase (like parsing the XML file or other format etc.), this work is doubled in each process. + It is up to the user to choose the optimal (or good enough) way – there is no automagic mechanism. +

+ + + +

+ + Finding runnable JARs + look for Java archives with a main class + 03900 + + + +

+ Java archives (*.jar files) that have set the main class can be started using java -jar program.jar command. + Let us find all JARs under a certain directory that are runnable. +

+ + + +

+ The script above will print output like this one: +

+ + + +

+ This pipeline consists of five steps: +

+ +

+ findFiles + – prepares the list of files separated by \0 byte; + if we omit the -iname '*.jar', the result will be the same, + just more files will be examinated +
+ fetchAttributes + – does the heavy work – tries to open each given file as a JAR (same as ZIP format) + and looks for the Main-Class field in the META-INF/MANIFEST.MF file (if any); + because the jar_info streamlet itself is written in Java, it simply uses existing Java functionality for main class lookup instead of reimplementing it in custom code; + thanks to --parallel N option, utilizes N cores of our CPU; + we can experiment with the N value and look how the total time decreases +
+ filterRunable + – uses AWK to skip the records (files) that does not have a main class; + in this step we could use also relpipe-tr-sql or relpipe-tr-guile if we prefer SQL or Guile/Scheme to AWK +
+ shortenPath + – replaces part of the absolute path with the ~ shortcut + (just to make it shorter and hide our username) +
+ relpipe-out-tabular + – formats the results as a table in the terminal (we could use e.g. relpipe-out-gui to call a GUI viewer or format the results as XML, CSV or other format) +

+ +

+ We can omit the -iname '*.jar' and run this pipeline on another directory + in order to find all valid JAR and ZIP files regardless their extension. + We will get also the number of entries (files and directories) in each archive. + In future versions, this streamlet might be extended to optionally provide files from the archive or their list e.g. in form of XML. +

+ + + +

+ + Collecting statistics from XHTML pages + use XPath to get titles and headlines counts from web pages and then show a bar chart and statistics + 04000 + + + +

+ The relpipe-in-filesystem and the xpath streamlet allows us to extract multiple values (attributes) from XML files. + We can use this feature to collect data from e.g. XHTML pages. +

+ + + +

+ The script above will show this barchart and statistics: +

+ + + +

+ This pipeline consists of four steps: +

+ +

+ findFiles + – prepares the list of files separated by \0 byte; + we can add -iname '*.xhtml' if we know the extension and make the pipeline more efficient +
+ fetchAttributes + – does the heavy work – tries to parse each given file as a XML + and if valid, extracts several values specified by the XPath expressions; + thanks to --parallel N option, utilizes N cores of our CPU; + we can experiment with the N value and look how the total time decreases +
+ filterAndOrder + – uses SQL to skip the records (files) that are not XHTML + and takes five valid files with most number of headlines +
+ relpipe-out-gui + – displays the data is a GUI window and generates a bar chart from the numeric values + (we could use e.g. relpipe-out-tabular to display the data in the text terminal or format the results as XML, CSV or other format) +

+ +

+ We can use a similar pipeline to extract any values from any set of XML files (e.g. Maven POM files or WSDL definitions). + Using --option mode raw-xml we can extract even sub-trees (XML fragments) from the XML files, so we can collect also arbitrarily structured data, not only simple values like strings or booleans. +

+ + + +

+ + Release v0.15 + new public release of Relational pipes + v0.15 + + +

+ We are pleased to introduce you the new development version of . + This release brings two big new features: streamlets and parallel processing + several smaller improvements. +

+ +

+ SLEB128: variable-length integers are now signed (i.e. can be even negative!) and encoded as SLEB128
+ streamlets in relpipe-in-filesystem: see details below
+ parallel processing in relpipe-in-filesystem: see details below
+ multiple modes in relpipe-in-xmltable: see details below
+ XInclude in relpipe-in-xmltable: use --xinclude true to process XIncludes before converting XML to relations
+ relpipe-lib-protocol → relpipe-lib-common: this module was renamed and converted to a shared library, it will contain some common functions instead of just the header files

+ +

+ See the examples and screenshots pages for details. +

+ +

+ Please note that this is still a development relasease and thus the API (libraries, CLI arguments, formats) might and will change. + Any suggestions, ideas and bug reports are welcome in our mailing list. +

+ +

Streamlets

+ +

+ Streamlet is a small stream that inflows into the main stream, fuse with it and (typically) brings new attributes. +

+ From the technical point of view, streamlets are something between classic filters and functions. + Unlike a function, the streamlet can be written in any programming language and runs as a separate process. + Unlike a filter, the streamlet does not relplace whole stream with a new one, but reads certain attributes from the original stream and adds some new ones back. + Common feature of filters and streamlets is that both continually read the input and continually deliver outputs, so the memory requirements are usually constant and „infinite“ streams might be processed. + And unlike ordinary commands (executed e.g. using xargs or a shell loop over a set of files), the streamlet does not fork() and exec() on each input file – the single streamlet process is reused for all records in the stream which is much more efficient (especially if there is some expensive initialization phase). +

+ +

+ Because streamlets are small scripts or compiled programs, they can be used for extending with minimal effort. + A streamlet can be e.g. few-lines Bash script – or on the other hand: a more powerful C++ or Java program. + Currently we have templates/examples written in Bash, C++ and Java. But it is possible to use any scripting or programming language. + The streamlet communicates with its parent (who manages the whole stream) through a simple message-based protocol. + Full documentation will be published when stable (before v1.0.0) as a part of the public API. +

+ +

+ The first module where streamlets have been implemented is relpipe-in-filesystem. + Streamlets in this module get a single input attribute (the file path) and add various file metadata to the stream. + We have e.g. streamlets that compute hashes (SHA-256 etc.), extract metadata from image files (PNG, JPEG etc.) or PDF documents (title, author… or even the full content in plain-text), OCR-recognized text from images, + count lines of code, extract portions of XML files using XPath or some metadata from JAR/ZIP files. + The streamlets are a way how to keep relpipe-in-filesystem simple with small code footpring while making it extensible and thus powerful. + We are not going to face the question: „Should we add this nice feature (+) and thus also this library dependency (-)? Would it be bloatware or not?“. + We (or the users) can add any feature through streamlets while the core relpipe-in-filesystem will stay simple and nobody (who does not need that feature) will not suffer from the growing complexity. +

+ But streamlets are not limited to relpipe-in-filesystem – they are a general concept and there will be relpipe-tr-streamlet module. + Such streamlets will get any set of input attributes (not only file names) defined by the user and compute values based on them. + Such streamlet can e.g. modify a text attribute, compute a sum of numeric attributes, encrypt or decrypt values or interact with some external systems. + Writing a streamlet is easier than writing a transformation (like relpipe-tr-*) and it is more than OK to write simple single-purpose ad-hoc streamlets. + It is like writing simple shell scripts or functions. + Examples of really simple streamlets are: inode (Bash) and pid (C++). + It requires implementing only two functions: first one returns names and types of the output attributes and the second one returns that attributes for a record. + However, the streamlets might be parametrized through options, might return dynamic number of output attributes and might provide complex logic. + Some streamlets will become a stable part of the specification and API (xpath and hash seems to be such ones). +

+ One of open questions is whether to have streamlets in relpipe-in-filesystem when we have relpipe-tr-streamlet. + One tool should do one thing and we should not duplicate the effort… + But it still makes some sense because the file streamlets are specific kind of streamlets and e.g. Bash completion should suggest them if we work with files but not with other data. + And it is also nice to have all metadata collecting on the same level in a single command (i.e. --streamlet beside --file and --xattr) + than having to collect basic and extended file attributes using single command and collect other file metadata using different command. +

+ +

Parallel processing

+ +

+ There are two kinds of parallelism: over attributes and over records. +

+ +

+ Because streamlets are forked processes, they are quite naturally parallelized over attributes. + We can e.g. compute SHA-1 hash in one streamlet and SHA-256 hash in another streamlet and we will utilize two CPU cores (or we can ask one streamlet to compute both SHA-1 and SHA-256 hashes and then we will utilize only one CPU core). + The relpipe-in-filesystem tool simply 1) feeds all streamlet instances with the current file name, 2) streamlets work in parallel and then 3) the tool collects results from all streamlets. +

+ +

+ But it would not be enough. Today, we usually have more CPU cores than heavy attributes (like hashes). + So we need to process multiple records in parallel. + The first design proposal (not implemented) was that the tool will simply distribute the file names to STDINs of particular streamlet processes in the round-robin fashion and processes will write to the common STDOUT (just with a lock for synchronization to keep the records atomic – the data format is specifically designed for such use). + This will be really simple and somehow helpful (better than nothing). + But this design has a significant flaw: the tool is not aware of how busy particular streamlet processes are and will feed them with tasks (file names) equally. + So it will work satisfactorily only in case that all tasks have similar difficultness. + This is unfortunately not the usual case because e.g. computing a hash of a big file takes much more time than computing a hash of a small file. + Thus some streamlet processes will be overloaded while other will be idle and in the end whole group will be waiting for the overloaded ones (and only one or few CPU cores will be utilized). + So this is not a good way to go. +

+ +

+ The solution is using a queue. The tool will feed the tasks (file names in the relpipe-in-filesystem case) to the queue + and the streamlet processes will fetch them from the queue as soon as they are idle. + So we will utilize all the CPU cores all the time (obviously if we have more records than CPU cores, which is usually true). + Because our target platform are POSIX operating systems (and primary one is GNU/Linux), we choose POSIX MQ as the queue. + POSIX MQ is a nice and simple technology, it is standardized and really classic. It does not require any broker process or any third-party library so it does not bring additional dependencies – it is provided directly by the OS. + However, fallback is still possible: + a) if we set --parallel 1 (which is default behavior), it will run directly in a single process without the queue; + b) the POSIX MQ have quite simple API so it is possible to write an adapter and port the tool to another system that does not have POSIX MQ and still enjoy the parallelism (or simply reimplement this API using shared memory and a semaphore). +

+ +

+ We could add another queue to the output side and use it for serialization of the stream (which flows to the single STDOUT/FD). + But it is not necessary (thanks to the format design) and would add just some overhead. + So on the output side, we use just a POSIX semaphore (and a lock/guard based on it). + Thus the tool still has no other dependencies than the standard library and the operating system. +

+ +

+ If we still have idle CPU cores or machines and need even more parallelism, streamlets can fork their own sub-processes, use threads or some technology like MPI or OpenMP. + However, simple parallel processing of records (--parallel N) is usually more than suitable and efficiently utilize our hardware. +

+ +

XPath modes

+ +

+ Both relpipe-in-xmltable and the xpath streamlet uses XPath language to extract values from XML documents. + There are several modes of value extraction: +

+ string: this is default option, simply the text content +
+ boolean: the value converted to a boolean in the XPath fashion; + +
+ raw-xml: a portion of original XML document; + this is a way to put multiple values or any structured data in a single attribute; + if the XPath points to multiple nodes, it can still be returned as a valid XML document using a configurable wrapper node (so we can return e.g. all headlines from a document) +
+ line-number: number of the line where given node was found; + this can be used for referencing particular place in the document
+ xpath: XPath pointing to particular node; + it would be a different XPath expression than the original one (which might point to a set of nodes); + this can also be used for referencing particular place in the document

+ +

+ Both tools share the naming convention and are configured in a similar way – using e.g. relpipe-in-xmltable --mode raw-xml or --streamlet xpath --option mode raw-xml. +

+ +

Feature overview

+ +

Data types

boolean
variable-length signed integer (SLEB128)
string in UTF-8

Inputs

Recfile
XML
XMLTable
CSV
file system
CLI
fstab
SQL script

Transformations

sql: filtering and transformations using the SQL language
awk: filtering and transformations using the classic AWK tool and language
guile: filtering and transformations defined in the Scheme language using GNU Guile
grep: regular expression filter, removes unwanted records from the relation
cut: regular expression attribute cutter (removes or duplicates attributes and can also DROP whole relation)
sed: regular expression replacer
validator: just a pass-through filter that crashes on invalid data
python: highly experimental

Streamlets

xpath (example, unstable)
hash (example, unstable)
jar_info (example, unstable)
mime_type (example, unstable)
exiftool (example, unstable)
pid (example, unstable)
cloc (example, unstable)
exiv2 (example, unstable)
inode (example, unstable)
lines_count (example, unstable)
pdftotext (example, unstable)
pdfinfo (example, unstable)
tesseract (example, unstable)

Outputs

ASN.1 BER
Recfile
CSV
tabular
XML
nullbyte
GUI in Qt
ODS (LibreOffice)

+ +

New examples

Computing hashes in parallel
Finding runnable JARs
Collecting statistics from XHTML pages

+ +

Backward incompatible changes

+ +

+ The data format has changed: SLEB128 is now used for encoding numbers. + If the data format was used only on-thy-fly, no additional steps are required during upgrade. + If the data format was used for persistence (streams redirected to files), recommended upgrade procedure is: + convert files to XML using old version of relpipe-out-xml and then convert it from XML back using new version of relpipe-in-xml. +

+ +

Installation

+ +

+ Instalation was tested on Debian GNU/Linux 10.2. + The process should be similar on other distributions. +

+ + + +

+ are modular thus you can download and install only parts you need (the libraries are needed always). + Tools out-gui.qt and tr-python require additional libraries and are not built by default. +

+ + + +

verify the format from the performance point of view
improve parsing (corrupted input may currently lead to huge memory allocations), more fuzzing
code clean-up and refactoring, move some reusable parts to common libraries
test the build with another compiler and tune the code
pkg-config: version numbers, debug vs. release
packaging for Guix SD and .deb and .rpm distributions, Snapcraft, Flatpak etc.