Big Data Craft

Network virtualization for the Cloud: Open vSwitch study

Constantine Peresypkin — Tue, 02 Oct 2012 18:14:48 +0000

In face of the current reality of ten thousand node data-centers and all the BigData jazz it seems like the network guys were slightly forgotten. We have enough hardware virtualization solutions but until now the network was left on the outskirts of the cloud hype. Let’s see what we can use right now and if it will get better in the future.

When people talk about network virtualization nowadays one name immediately springs into mind: Nicira, they invented OpenFlow, Open vSwitch (OVS) and… were acquired by VMware.

Why Nicira? They essentially designed the current state of network virtualization. OpenFlow is implemented in physical hardware and OVS is used by a lot of people to drive the software network stack in virtualized environments.

But is it any good? Let’s see. If you open the specification for OpenFlow it looks simple: let’s cut the hardware intervention at the Ethernet level and implement all other features in software. We essentially write a program (handler) that matches some fields in packet and acts according to simple rules: forward to port, drop, pass to other handler. But then, how do you install these handlers inside the switch? The solution is also not that complicated: you just write another more complex software that runs on something generic (like PC). It chooses handlers for particular flows by issuing a command to the switch, when switch encounters something it does not have handler for, it just passes it to this PC (controller) and controller either chooses a new handler for the switch or processes the packet internally.

What do we see here? It looks like there is an execution platform inside the hardware for running the network handlers and a controller which chooses the handler for each state. It looks very promising and flexible, and can be implemented not only in hardware but also in software only. And the same guys implemented it in OVS, shall we peek inside? Yes, I’ve answered to myself, and downloaded the OVS source.

When I looked inside the code I was little… how should I put it… surprised? OVS code has everything but a kitchen sink inside: serializeable hash table, JSON parser, VLAN tagging, several QoS implementations, STP implementation, Unix socket server, RPC over SSL server and the icing on the cake: their own database with a key/value + columnar storage engine. And everything implemented from scratch (or so it seems).

Ok, they have enough shock value already, but how does this thing work? It turns out that the operation is not that different from the hardware I’ve described above. It just has a kernel module instead of actual hardware and the flow handlers are just some functions inside the module. It looks like this.

Daemon uses netlink to talk to kernel module and install the handlers, database stores the configuration, controller talks to daemon via OpenFlow or plain JSON.

So, we got a software stack for network, why is it good for virtualization?

Short answer: because everybody uses Linux. And when your hypervisor runs on Linux why not use some of its capabilities for a nice network boost. But why OpenFlow/OVS?

The OVS docs describe it like this:

Open vSwitch is targeted at multi-server virtualization deployments, a landscape for which the previous stack is not well suited. These environments are often characterized by highly dynamic end-points, the maintenance of logical abstractions, and (sometimes) integration with or offloading to special purpose switching hardware.

But Linux always had a good network stack, easily manageable and extendible. What are the advantages? There are some.

OVS can migrate the network state with the bridge port (connected to the VM instance, for example). You will loose some packets, but the connections may still stay intact.
OVS can use metadata to tag frames (VM instance UUID, for example).
OVS can install event triggers inside the daemon to notify the controller on the state change (VM reboot, for example).

Does it justify a new kernel module + new DB engine + new RPC protocols? Maybe not. But you can’t get these capabilities from any other open source software anyway.

The only question I have right now is why Nicira did not implement STT in OVS, but certainly did in its proprietary NVP software?

What does BigData mean?

Camuel Gilyadov — Mon, 24 Sep 2012 07:44:39 +0000

The full deck available at http://cci.uncc.edu/sites/cci.uncc.edu/files/media/pdf_files/Stonebreaker-charlotte.pdf

Apache Drill Design Meeting

Camuel Gilyadov — Sat, 15 Sep 2012 03:18:36 +0000

MapR folks invited me to participate in Apache Drill design meeting. Meetup site indicates that 60 people have been participated which sounds about right.

Tomer Shiran started the meeting with the overview of Apache Drill project. Then I (Camuel here) presented our team view for Apache Drill architecture. Jason Frantz of MapR continued touching technical aspects in follow on discussion. After a pizza break, Julian Hyde presented his view on logical/physical query plan separation and suggested using optiq framework for DrQL optimizer.

Overall my take away are as follows:

There is very healthy interest in interactive querying for BigData.
There were not even a single voice calling on making up vanilla Hadoop for this task.
There is a general consensus on plurality of query languages and plurality of data formats.
There is a general consensus that user always should be given freedom to supply manually authored physical query plan for execution, bypassing optimizer altogether and as opposed to hardcore hinting.
Except me no one tried to challenge “common logical query model” concept. Since there are no real joins in Dremel and no indexes and only one data source with exactly one possibility – a single full table scan, I cannot see the justification for the complexity of optimizers and the logical query model. Dremel is an antidote concept to all this.

Thank you – MapR, for the Drill initiative, the great design meeting and the invitation.

Hadoop on OpenStack Swift: experiments

Constantine Peresypkin — Sat, 08 Sep 2012 18:52:10 +0000

Some time has passed since our initial post on Hadoop over OpenStack Swift implementation. A couple of things have changed (Rackspace finally implemented range requests in their Cloudfiles library) others remained the same (still no built-in support for Hadoop in OpenStack / CloudFiles).

We got a lot of feedback and questions regarding the integration but not always had the time or patience to properly address them, sorry for that. But one of our readers, Zheng Xu, did a great job by putting together a slide deck on the exact procedure.

But there are still some points I need to address regarding the procedure he assembled there. It mostly boils down to Cloudfiles: although current Cloudfiles implementation has HTTP range support, our implementation uses our own code for the latter, therefore I really encourage ether using our Cloudfiles distribution (with patches) or changing our Hadoop code to use the new Rackspace one. Although the simple filesystem tasks will work as expected, any MapReduce job that works with big files will fail without correct HTTP range support.

I want to thank Zheng Xu for the effort and congratulate him on the success of his small experiment.

Apache Drill Progress

Camuel Gilyadov — Tue, 04 Sep 2012 14:57:16 +0000

We are continuing our efforts in contributing our OpenDremel code to Apache Drill project and look forward to be active with it right after that.

Right now the efforts are being put into our ANTLR-based parser, we want to make it work with the new grammar of BigQuery language. That should be done within a few days, the parser will be committed to the new Drill repository as a first phase of the OpenDremel-Drill merge.

Next on, we plan to refactor and contribute the Semantic Analyzer, which processes the output of the parser into an intermediate form, resolving references and rewriting (flattening) the query into single full table scan operation. That is expected within a week or two, it would depend when the Drill architecture doc will be published. We still don’t know what will be the schema language/format. Will it be Protobuf? Avro? OpenDremel supports Avro right now and has an initial support for Protobuf.

The final phase of OpenDremel – Drill merge, will be the contribution of the code generator based on the Apache Velocity templates. We have two sets of templates for now: one is a Java-based and executed with Janino executor and second one uses C/asm and executed with ZeroVM executor.

Everyone who wishes to help is welcome. The OpenDremel code resides in its usual Google code repo – http://code.google.com/p/dremel/. BE SURE TO LOCATE AND USE REPO COMBO BOX on the upper part of the page.

We probably will use https://github.com/ApacheDrill repo as a staging area or the Apache git repo directly, it all depends on what will be proposed by Ted Dunning – the Apache Drill Champion.

We also continue work on our generic execution backend built on top of OpenStack Swift and integrated with ZeroVM. We are contributing to both projects here.

We look ahead to Apache Drill with pluggable frontends and pluggable backends. So it would be able to run on top of a toy single-JVM Janino backend, or under YARN management on HDFS with Janino or ZeroVM backend, or even on a Zwift backend (that’s how we codenamed OpenStack Swift + ZeroVM combo).

On other hand the frontends will be pluggable too, so, in the future, support for new languages such as Apache Pig or Apache Hive can be added easily. Another option would be to create single frontend with pluggable language handlers, that would allow us to embed functionality from other projects such as Apache Mahout or R.

Apache Drill

Camuel Gilyadov — Sat, 25 Aug 2012 23:41:43 +0000

We are not longer alone implementing Google Dremel and BigQuery technology. A proposal was made recently to Apache Foundation suggesting similar project. Moreover Ted Dunning kindly invited us to take part in the project.

The project is just starting now and there is no source code yet and not even a consensus design. So we sat together today evening and wrote a proposed design for Apache Drill. We already working for about two years on Dremel and BigQuery implementation. It was a fascinating journey and we have learned quite a lot and would be more than happy to share our experiences and accumulated knowledge.

All our code (OpenDremel/Dazo/ZeroVM) has Apache License from the beginning and used several Apache technologies from Avro to Velocity. Apache seems to be best home for Drill project and we are looking forward to contribute to it.

Apache Drill from Camuel Gilyadov

Start-Up Chile

Camuel Gilyadov — Sat, 07 Jul 2012 19:45:38 +0000

I’ve been frequently asked about my experiences in Start-Up Chile program. For the past half year that I’ve been participating in the program I could say that it was interesting and fulfilling experience.

On top of provided seed capital you get a supporting framework of mentors and fellow startupists. You can literally “feel” the surrounding entrepreneurial spirit. And despite me being unlucky to find peer support with my infrastructure BigData@Cloud idea (most folks were doing consumer web kind of startups) I did found the framework highly encouraging.

Provided capital is equity-free which is especially nice and makes negotiating next financing round easier. Getting the money is paperwork-intensive process but the staff are friendly and helping.

I found Chileans hospitable and friendly to foreigner. Yet minimal Spanish seems to be mandatory. I found myself speaking Spanish after a few month in Santiago and that was unplanned initially.

Santiago is a nice mountain-surrounded modern city and pretty safe I would say. I cannot count how many times locals warned me on how unsafe Santiago really is, but except permanently going strike/riot in the central part of the city I never experienced and never witnessed or heard about any incident. And I’m usually working deep into the night and walk extensively before retiring to bed. I lived in Centro but especially enjoyed walking in west-northern part of the town. Underground transprtation is quite efficient to get around, a little hot during mid-day in February I remember. I was mostly fully consumed by my startup so haven’t enough time to tour the rest of the country, and even Santiago only from walking experience guided by GPS in my Nokia. I really should rent a car one weekend and get out for a couple of days… In fact I did one weekend in Vinna del Mar / Valparaiso and found it quite a nice and relaxing place.

The local entrepreneourship and geekish community is also thriving and this is not including very visible Start-Up Chile folks. Go to meetup.com and choose your favorite topic or technology and I bet you will find a packed santiago interest group there.

Apache Hadoop over OpenStack Swift

Camuel Gilyadov — Thu, 01 Mar 2012 09:59:57 +0000

This is a post by Constantine Peresypkin and David Gruzman.

Lately we were working on integrating Hadoop with OpenStack Swift. Hadoop doesn’t need an introduction neither does OpenStack. Swift is an object-storage system and the technology behind RackSpace cloud-files (and quite a few others like Korea Telecom object storage, Internap and etc…)

Before we go into details of Hadoop-Swift integration let’s get some relevant background:

Hadoop already have integration with Amazon S3 and is widely used to crunch S3-stored data. http://wiki.apache.org/hadoop/AmazonS3
NameNode is a known SPOF in Hadoop. If it can be avoided it would be nice.
Current S3 integration stages all data as temporary files on local disk to S3. That’s because S3 needs to know content length in advance it is one of the required headers.
Current S3 also suffers form 5GB max file limitation which is slightly annoying.
Hadoop requires seek support which means that HTTP range support is required if it is run over an object-storage . S3 supports it.
Append file support is optional for Hadoop, but it’s required for HBase. S3 doesn’t have any append support thus native integration can not use HBase over S3.
While OpenStack Swift is compatible with S3, RackSpace CloudFiles is not. It is because RackSpace CloudFiles disables S3-compatibility layer in Swift. This prevents existing Swift users from integration with Hadoop.
The only information that is available on Internet on Hadoop-Swift integration is that with using Apache Whirr! it should work. But for best of our knowledge it is relevant only to rolling out Block FileSystem on top of Swift not a Native FileSystem. In other words we haven’t found any solution on how to process data that is already stored in RackSpace CloudFiles without costly re-importing.

So instrumented with above information let’s examine what we got here:

In general we instrumented Hadoop to run over Swift naively, without resorting to S3 compatibility layer. This means it works with CloudFiles which misses the S3-compatibility layer.
CloudFiles client SDK doesn’t have support for HTTP range functionality. Hacked it to allow using HTTP range, this is a must for Hadoop to work.
Removed the need for NameNode in similar way it is removed with S3 integration for Amazon.
As opposed to S3 implementation we avoided staging files on local disk to and from CloudFiles/Swift. In other words data directly streamed to/from compute node RAM into CloudFiles/Swift.
Though the data is still processed remotely. Extensive data shipping takes place between compute nodes and CloudFiles/Swift. As frequent readers of this blog know we are working on technology that will allow to run code snippets directly in Swift. Look here for more details: http://www.zerovm.com. As next step we plan to perform predicate-pushdown optimization to process most of data completely locally inside ZeroVM-enabled object-storage system.
Support for native Swift large objects is planned also (something that’s absent in Amazon S3)
We also working on append support for Swift (this could be easily done through Swift large object support which uses versioning) so even HBase will work on top of Swift, and this is not the case with S3 now.
As it is the case with Hadoop S3, storing BigData in native format on Swift provides options for multi-site replication and CDN

I also added a question to Quora on this issue: http://www.quora.com/Is-it-possible-to-run-Hadoop-to-directly-process-data-stored-in-RackSpace-CloudFiles-Swift

Futility of “tooling” a proprietary cloud.

Camuel Gilyadov — Sun, 12 Feb 2012 02:44:14 +0000

I’v been pitched by a lot of entrepreneurs trying to make a better-than-original “tooling” for a proprietary cloud, particularly for AWS. Ain’t the attempt futile from the beginning? Amazon is smart, innovative and working hard to make its cloud offering comprehensive and has much larger arsenal to overdo anyone who dare to compete on their own turf. That is their party, the invitation cannot be taken for granted.

Let’s take NoSQL data-stores and DBMS vendors as examples. There are VC-backed companies out-there which are exclusively focused on outdoing Amazon with running MySQL/NoSQL on their own cloud, Xeround comes to mind, but many others also hoping their product will catch fire on EC2.

Well, if just single branding and plain convenience is not enough , how about these two exclusive and “unfair” competative advatnages in Amazon arselnal:

[My unverified assumption is] that DynamoDB has storage integrated into its fabric whenever all the rest must use slower EBS.
Not it is just integrated, but as announced by Amazon, it uses SSD-backed storage. SSD-backed storage is not available, as of today, for DynamoDB competitors running on AWS. So competitors must continue to use ordinary EBS. That is in fact a double-kick, first the mere fact of using different hardware for a competitive advantage and second, the announcment itself as catalyst to trigger migration.

So, future EMR, may also have an integrated storage as well as other hardware optimization, making Hadoop more efficient on AWS and good if so. Same goes to RDS and other current and future PaaS-related services.

Do I accuse Amazon on wrongdoing? Of course not! They brought the cloud to the main-street while others were only talking about it they and made large-scale computing affordable to all and continue dropping prices passing their economies-of-scale savings on customers and also keeps optimizing and enhancing their infrastructure constantly, and were good to their shareholders also. However, as any proprietary and monopolistic platform, they do hinder some outside-of-Amazon innovation. No matter how good they are, we don’t want only one company in the world doing cloud-infrastructure stuff for the rest. That’s why, OpenStack are so extremely important for the industry. If OpenStack will be widely adopted then infrastructural and “tooling” kind of innovation could go directly into OpenStack for greater good and fairer monetization model for the author.

OpenDremel update and Dremel vs. Tenzing

Camuel Gilyadov — Wed, 08 Feb 2012 03:34:41 +0000

I wasn’t blogged for whole 2011 year… I’m not dead, quite on contrary, we were pretty active with OpenDremel project in 2011. First, we are renaming it to Dazo to avoid using a trademarked name and second, we did a good job implementing a secure generic execution engine and integrating it into OpenStack Swift. It also came out, that the engine is actually quite useful virtualization technology in itself and it could potentially deserve a better fate than being buried as OpenDremel subcomponent. So, we do plan to release it as independent project and are quite busy with that now, so the work on OpenDremel is all but stalled unfortunately. As for storage infrastructure we settled with OpenStack Swift, we falled in love with Swift from the day it was released and now after we have integrated ZeroVM into it we even like it even more. So right now, we have fully salable storage backend with the unique capability to run securely any arbitrary native code inside, close to data. Now, what’s left is to take our old Metaxa Query Compiler and integrate it with that backend and then after many iterations it would bake into something pretty similar to Google Dremel and BigQuery. Even better, it will always process data locally (not sure BigQuery does it now) and it will not be limited to BQL on nested records, but for any query on any data and with full multi-tenant semantics. That’s how interesting 2011 was…

It was a preamble now back to the main feature:

Google released a paper on Tenzing last year on VLDB. Tenzing is an SQL query-system implemented on top of MapReduce infrastructure and it can be thought as Google-way to do Hive and as always full of juicy details. There is already a quality post on this published and another one here. On top of that my additional takeways are:

1. It is possible to build MPP-grade system on top of MapReduce with relatively low-latency (10 seconds). However, it would requires quite a number of patches to MapReduce. Hive and Hadoop has certainly a lot to learn from Tenzing.

2. Even with Google version of a patched and leaner-than-Hadoop implementation of MapReduce getting it to Dremel latencies was not achievable. On other hand 10 seconds as minimal latency is not that bad and in same ball park as Netezza/Greenplum/Aster and other MPP gear.

3. As general Sawzall vs. Dremel vs. Tenzing comparison there is an nice youtube-datawarehousing presentation published. In fact, Dremel beats both of them on latency and if not only for limited expressive power of its query language it would end up as complete winner on all metrics considered there. Sawzall having imperative query language scores highest on the power metric. I guess when OpenDremel will be released it will be a unique combination of low-latency querying with the full expressive power of imperatively-augmented SQL.

4. Tenzing can query MySQL databases as many other popular data formats. What we witnessing here is that query-engines is being decoupled from storage engines. 10 years ago it was only the case for MySQL ecosystem and anyone who tried Oracle external table interface knows how friendly past DBMSes were to external data sources. Dremel columnar encoding component was released internally in Google as separate ColumnIO storage engine. Then Google open-sourced their key-value LevelDB engine a-la Hadoop’s RCFiles. So we can learn here of emergence of multiple storage-engines working with multiple query engines, quite interesting phenomenon.

5. The query is compiled into native code (with LLVM) and this gave significant acceleration by factor from six to twelve. This means that SQL to native code compilation is a must for high-performance BigData query engines.

Upcoming hardware renaissance era: part #2.

Camuel Gilyadov — Mon, 17 Jan 2011 17:17:39 +0000

Some examples of upcoming hardware renaissance era:

1. Virtually all server vendors are pitching modularized data centers by now. MDC are boxes resembling shipping containers accommodating complete vritualized data-center inside. With MDC one just connects power, network and chilled water and gets access to the cloud in the box. Most MDC are good to be deployed outside and have built-in protection against weather elements. Of course all current offering are based on x86 commodity servers but here is a hint: once competition moves to comparing whose shipping container can stuff more storage and computing power inside and who has better price/performance and energy efficiency, we will see innovation in hardware skyrocketing.

2. On processor front…. ARM architecture has all ingredients to become next Intel. If I am not mistaken, ARM processors are outnumbering x86 10 to 1 with tens of billions of processors shipped. 95% of cellphones and advanced gadgets use ARM. ARM power efficiency puts x86 in shame. However, till now ARM was focused on gadgets and dismissed data-center market. Not anymore! With newer Cortex-A15 ARM took aim at x86 on datacenter territory. Calxeda already got ~$50M in venture money for commercializing ARM in datacenter. However, ARM is not alone here, Tilera with their server-vendor partner Quanta are already shipping 512 core server in 2U form-factor. Tilera took lean MIPS processor core and put some 100 of them into single die together with x8 10Gbit Ethernet channels and four DDR3 memory channels. Nvidia also claimed that they are not GPU-only vendor anymore and are readying general-purpose processors based on ARM architecture with ample amount of GPU muscle inside. That said Intel and AMD are also far from stagnating and moving into heterogeneous many-core designs. I think we never witnessed more innovation in processor space than now.

3. On memory front… Flash is making inroads to claim space in memory-hierarchy between DRAM and HDD. Disrupting DRAM market and high-performance 15K RPM HDD market. I think 15K RPM HDD and DRAM-based SSD products are already safe to be declared dead. Same about HDD smaller than 2.5 inch form-factor. I even think 2.5 HDD are also in risk. Only capacity-optimized HDDs would survive. Even without flash, the DRAM got such capacity that most datasets fits in RAM completely. And if not in RAM of single server than it surely fits in shared cluster RAM. This solid-memory advancements in DRAM and Flash disrupts storage market, especially making high-performance SAN redundant. The only storage tomorrow server will need is capacity-optimized and energy-optimized ones. That fact among other forced EMC to move into computing… and provide complete cloud in the box instead just storage in the box like it did in the past.

4. Networking… in my view networking is most stagnating hardware market here. Infiniband finally moves into mainstream and it is good. Does it? Or it will succumb to 10GbE? Remains to be seen. My bet is on Infiniband due to architectural superiority. Networking virtualization is still on whiteboards… unfortunately. So in networking there is no signs of renaissance but the potential is there.

Emerging Proprietary Hardware Renaissance

Camuel Gilyadov — Wed, 17 Nov 2010 14:42:53 +0000

INTRO
I cannot count number of times I heard that cloud computing means innovation stagnation in the proprietary hardware business and that with cloud computing, hardware doesn’t matter anymore and will succumb sooner or later into boring razor-thin-margins oligopolistic commodity industry.

GAME OVER FOR FAT MARGINS IN PROPRIETARY HARDWARE?
Why folks think like that? Well… there is one reason that dominates their thinking – hardware products became components and worse of all they became a well standardized components. And as such, certain low-wage countries can quickly master how to assemble them in large quantities and win competition purely on cost and nothing else seriously matters in component business. No one carries about component extended enterprise feature set and premium brand and long list of ISV partnerships and etc… what matters is very well defined functionality and price, price and price. In fact it already happened to low-end gear like entry-level basic servers and routers. The situation is very different for enterprise IT products. I estimate that if IT costs will be tripled overnight for most enterprises it would not matter in their bottom line. So IT departments of most enterprises are cost-insensitive regarding IT gear. They will not blindly overpay in most cases but cost is not high in their priority list either. IT for most enterprises is more or less fixed cost amortized among very large number of its products or services. I guess if Coca Cola IT was tripled the price of single can of coke should be elevated for less than a cent. Unlikely that it is life-threatening to their business. Therefore the game was and largely still is to market hardware products directly to enterprise IT departments competing on enterprise feature set rather than price. Now with emerging cloud computing paradigm hardware products are components and are marketed to cloud operators which are essentially server farmers. And they are extremely cost-sensitive and marketing to them premium computing gear will be as successful as marketing a premium booze as fuel to alcohol-fueled car owner. If for cloud operator server costs will be tripled overnight the next morning it would be out of business. So without a doubt it is a game over for fat margins in hardware manufacturing/assembly business. What happened to enterprise software 5 years ago is happening to enterprise hardware right now – commoditization.

PROPRIETARY HARDWARE INNOVATION
So the common thinking goes, in the boring commodity business no one is going to invest in innovation so no one is going to invest much into proprietary hardware because no cloud vendor is going to buy premium hardware. The only hope is private cloud as a freshly invented loophole to continue to sell premium gear to enterprises. Well lets consider the following situation. XYZ startup manages to build a proprietary appliance which is essentially a cloud-in-the-box solution that through tight internal integration and optimization for one particular task achieves an order-of-magnitude better price-performance.Lets say it is an KV-store appliance. Would cloud-operators be interested? I bet they will. From outside it doesn’t matter if the functionality are backed up by cassandra-on-generic hardware or custom-hardware-appliance. So the cloud provider quietly rolling out such appliances can compete well both on price and on functionality (like latency) with other cloud providers running software-based KV-store on generic hardware. Other startup ABC may produce a computing appliance that can run ruby-on-rail or java or pyton applications order-of-magnitude more efficiently than a generic hardware and a cloud provider deploying such appliances from ABC startup could compete better serving RoR clients. Yet another startup may build a custom rack-sized box filled with fermi chip specifically designed for video processing. I can bring more examples but the trend is obvious. Use large chunk of dedicated hardware to do one specific task and do it extremely efficiently and you can have nice margins as hardware manufacturer. Before cloud – hardware must be generic because single enterprise server should be able to run a variety of different workloads. With cloud computing it is not longer the case. A vendor can build a dedicated hardware appliance optimized to do one specific workload and serve the whole world with it raising high barriers for the competitors. So despite popular belief I think cloud computing presents unique opportunities to creative hardware engineers, tough not in premium enterprise-feature set area as it used to be but in extreme-efficiency, acceleration and specialization areas.

Two Envelopes Problem: Am I just dumb?

Camuel Gilyadov — Sun, 17 Oct 2010 19:34:02 +0000

It seems the recent craze about statistician being a profession of choice in the future gains steam. In future where we will be surrounded by quality BigData, capable computers and bug-free open source software including OpenDremel. Well the last one I made up… but the rest seems to be the current situation. Acknowledging this I was checking what is the state of open-source statistics software and who are the guys behind it and etc.. But it is not my today topic, it is the topic of one of my next posts. Today I want to talk about one of the strangest problems/paradoxes on the internet I have ever seen. The story is, that I encountered right now “the two envelops problem” or “paradox” as some put it. Having worked with math guys for a long time (having math mastery that I’ll never reach in my life) I immediately recognized that problem as I was teased by it few times a long time a go. However, I was never told that this is such a big deal of a problem. Wikipedia lists it under “Unsolved problems in statistics”. Heh? And I never understood what is so paradoxical or hard or even interesting in it? For me it seemed high-school grade problem at most. So I put “two envelopes problem” into Google and found tens of blogs trying to explain it and propose ~~over-engineered~~ over-complicated and long solutions to such a simple problem. I have a very strange feeling that I’m either totally dumb or a genius and I know I’m not a genius In some sources it is mentioned that only Bayesian subjectivists suffer from this, however in large majority of other sources it is presented as an universal problem… Well enough talking lets dive in into simplest solution on internet (or I will be embarrassed by someone pointing my mistake or similar solution published elsewhere).

The problem description for those who never heard about it:

You are approached by a guy that shows you two identical envelopes. Both envelopes contain money. You are allowed to pick and keep any one of them for yourself. After you pick one, the guy makes you an offer to swap envelopes. The question is if one should swap. For me it is as clear as sunny day that it doesn’t matter if you swap and it is easily provable by simple math. Somehow most folks (some Ph.D. level!) get into very hairy calculations that suggest that one should swap and than even more hairy ones why one should not. Some mention subjectivity but most don’t.

The simplest solution on internet (joking… but seriously I haven’t found such simple one):

Let’s denote the smaller sum in one of envelopes as X and therefore the larger sum in the other will be 2X. Then expected value of current envelope selection before swap consideration is 1.5X. How I got to it? Very simply we have 0.5 probability of holding the envelope with larger sum that is 2X and 0.5 probability with holding an envelope with smaller sum witch is X. So:

0.5*2X+0.5*X = X+0.5X=1.5X

So far so good… let’s now calculate the expected value if we swap. If we swap, we will have same 0.5 probability of holding larger sum and same 0.5 probability of holding the smaller sum. Needless to repeat the calculation, you will get exactly same 1.5X as an expected value, meaning that the swap doesn’t matter. Or if time has any value it doesn’t make sense to waste it by swapping envelopes.

Do you see it as hard problem? I bet 10-year old will do fine with it, especially if offered some reward.

How come others get lost here?

The answer is that some try to apply Bayesian subjectivism probability theory and then innocent folks follow it and gets lost as well.

If you look to Wikipedia article for example you will find a classic wrong solution that allegedly is “obvious” and then a link outside Wikipedia to a “correct” solution. The correct solution seems a long post with a lot of formulae and usage of Bayes theorem that at the end came to correct answer.

Well… I see clearly a flaw with the solution published in wikipedia. That solution really looks artificial, but according to the number of followers it should be obvious for many. The blunder is in the third line:

The other envelope may contain either 2A or A/2

By A they denoted the sum in the envelope they are holding. The mistake is in “either 2A or A/2″, it should be “either 2A or A”, Then everything will be ok and no “paradox” will emerge in the end. The mistake stems from the fallacy of using same name for two separate variables that are dependent but not equal! And then repeatedly confusing them since they have same name. Here is a “patch” to be applied to wikipedia published reasoning:

1. I denote by A the amount in my selected envelope. => FINE
2. The probability that A is the smaller amount is 1/2, and that it is the larger amount is also 1/2. => FINE
3. The other envelope may contain either 2A or A/2. =>INCORRECT variable A denotes different values so it is highly confusing to write it this way.

let’s explicitly consider two cases here instead of implicit “either..or…”

in first case let’s assume we are holding the smaller sum then the other envelope contains 2A
in the second case let’s assume we have holding the larger sum then the other envelope contains A/2. However, the A is different from A of first case so let’s write it as _A/2

Moreover we know that _A is not just different from A but is exactly twice the other so
_A = 2A
So the expression “either 2A or A/2″ must be written as “either 2A or _A/2″ or substituting _A=2A as “either 2A or A”.

Then for calculating expected value you also substitute A instead of A/2 and get same expected value than before swap.

===============================

That said, I saw many people feeling so “enlightened” by reading a complicated “correct” solution that they erroneously think and argue that one should not accept the following offer thinking it is equivalent to the above problem (well not exactly this but I rephrased it for clarity):

One guy comes to you and says there are three envelopes. You are allowed to pick one and keep it. One envelope is red and two are white. All three contain money. One of white envelopes contain twice as many as red one. Another white one contains half of red one. The white envelopes are identical and there is no way to know which one contains double and which one contains half. The question is which envelope you should choose: the red one or one of the white ones. And the answer is that you should pick one of white envelopes! In fact the calculation errorneously applied to the two-envelopes problem is 100% correct to the three-envelopes-problem. And on average you will win choosing one of white envelopes rather than a red one.

Debunking common misconceptions in SSD, particularly for analytics

Camuel Gilyadov — Wed, 13 Oct 2010 13:45:23 +0000

1. SSD is NOT synonymous for flash memory.

First of all let’s settle on terms. SSD is best described as a concept of using semiconductor memory as disk. There is two common cases: DRAM-as-disk and flash-as-disk. And flash-memory is a semiconductor technology pretty similar to DRAM, just with slightly different set of trade-offs made.

Today there are little options to use flash memory in analytics beyond SSD. Nevertheless, it should not suggest that SSD is synonymous for flash memory. Flash memory can be used in products beyond SSD, and SSD can use non-flash technology, for example DRAM.

So the question is: do we have any option of using flash-memory in other form rather than flash-as-disk?

FusionIO is the only one and was always bold in claiming that their product are not-SSD but a totally new category product, called ioMemory. Usually I dismiss such claims automatically in subconscious as a common-practice of term-obfuscation. However, in the case of FusionIO I found it to be a a rare exception and technically true. On hardware level there is no disk-related overhead in FusionIO solution and in my opinion FusionIO are closest to the flash-on-motherboard vision among all the rest of SSD manufacturers. That said, FusionIO succumbed to implementing a disk-oriented storage layer in software because unavailability of any other standards covering flash-as-flash concept.

You can find a more in-depth coverage of New-Dynasty SSD versus Legacy SSD issue in recent article of Zsolt Kerekes on StorageSearch.com. Albeit I’m not 100% agree with his categorization.

2. SSD DOESN’T provide more throughput than HDD.

The bragging about performance density of SSD could safely be dismissed. There is no problem in stacking up HDDs together. As many as 48 of them can be put in single server 4U box providing aggregate throughput of 4GB/sec for fraction of SSD price. Same goes to power, vibration, noise and etc… The extent to which this properties are superior to disk is uninteresting and not justifying the associated premium in cost.

Further, for any amount of money, HDD can provide significantly more IO throughput , than SSD of any of today vendor. On any workload: read, write or combined. Not only this, but it will do so with an order of magnitude more capacity for your big data as additional bonus. However, a few nuances are to be considered:

If data is accessed in random small chunks (let’s say 16KB chunks), then SSD will provide significantly more throughput (factor of x100 may be) than disk will do. Reading in chunks at least 1MB will put HDD as a winner in the throughput game again.
The flash memory itself, has great potential to provide an order of magnitude more throughput than disks. Mechanical “gramophone” technology of disks cannot compete in agility with the electrons. However, this potential throughput is hopelessly being left unexploited by the nowadays SSD controller. How bad it is? Pretty bad, SSD controllers pass on less than 10% of potential throughput. The reasons include: flash-management complexity, cost-constraints leading to small embedded DRAM buffers and computationally-weak controllers, and the main reason being that there is no standards for 100 faster disk, neither legacy software could potentially keep with higher multi-gigabyte throughputs, so SSD vendors don’t bother and are obsessed with the laughable idea of bankrupting HDD manufacturers calling the technology disruptive which it is not by definition. So we have a much more expensive disk replacement that is only barely more performant, throughput-wise, than vanilla low-cost HDD array.

3. Array of SSDs DOESN’T provide larger number of useful IOPS than arrays of disks.

While it is true that one SSD can match disk array easily in IOPS, it should not suggest that array of SSD will provide larger number of useful IOPS. The reason is prosaic, array of disks provides an abundance of IOPS, many times more than enough for any analytic application. So any additional IOPS are not needed and astronomical number of IOPS in SSD arrays is a solution looking for a problem in analytics industry.

4. SSD are NOT disruptive to disks.

Well if it is true it is not according to Clayton Christiansen definition of “disruptiveness”. As far as I remember Christiansen defines “disruptiveness” as technology A being disruptive to technology B when all following holds true:

A is worse than technology B in quality and features
A is cheaper than technology B
A is affordable to a large number of new users to whom technology B is appealing but too costly.

SSD-to-disk pair is clearly not true for any condition above so I’m puzzled how one can call it disruptive to disks?

Again. I’m not claiming that SSD or flash-memory is not disruptive to any technology I just claiming that SSD are not disruptive to HDD. In fact, I think flash-memory IS disruptive to DRAM. All three conditions above hold for flash-to-DRAM pair. Also a pair of directly attached SSDs are highly disruptive to SAN.

—————

Make no mistake I’m a true believer in flash-memory as a game-changer for analytics just not in the form of disk replacement. I’ll explore in my upcoming posts the ideas where flash memory can make a change. I know I totally missed any quantification proofs for all the claims above but…. well…. let’s leave it for comment section.

Also one of best coverage of flash-memory for analytics (and not coming from a flash vendor) is of Curt Monash on DBMS2 blog: http://www.dbms2.com/2010/01/31/flash-pcmsolid-state-memory-disk/

Google Percolator: MapReduce Demise?

Camuel Gilyadov — Tue, 12 Oct 2010 20:10:02 +0000

Here is my early thoughts after quickly looking into Google Percolator and skimming the paper .

Major take-away: massive transactional mutating of tens-petabyte-scale dataset on thousands-node cluster is possible!

MapReduce is still useful for distributed sorts of big-data and few other things, nevertheless it’s “karma” has suffered a blow. Beforehand you could end any MapReduce dispute by saying “well… it works for Google”, however, nowadays before you say it you would hear “well…. it didn’t work for Google”. MapReduce is particularly criticized by having 1) too long latency, 2)too wasteful, requiring full rework of the whole tens-of-PB-scale dataset even if only a fraction of it had been changed and 3) inability to support kinda-real-time data processing (meaning processing documents as they are crawled and updating index appropriately). In short: welcome to disillusionment stage of MapReduce saga. And luckily Hadoop is not only MapReduce, I’m convinced Hadoop will thrive and flourish beyond MapReduce and MapReduce being an important big data tool will be widely used where it really makes sense rather than misused or abused in various ways. Aster Data and remaining MPP startups can relax on the issue a bit.

Probably a topic for another post, but I think MapReduce is best leveraged as ETL tool.

See also http://blog.tonybain.com/tony_bain/2010/09/was-stonebraker-right.html for another view on the issue. There are few others posts already published on Precolator but I haven’t yet looked into them.

I’m very happy about my SVLC-hypothesis, I think I knew it for a long time, but somehow only now, after I have put it on paper, I felt that the reasoning about different analytics approaches became easier. It is like having a map instead of visualizing it. So where is Percolator in the context of SVLC? If it is still considered analytics, Percolator is an SVC system – giving up latency for everything else, albeit to a lot lesser degree than its successor MapReduce. That said Percolator has a sizable part that is not analytics anymore but rather transaction processing. And transaction processing is not usefully modeled by my SVLC-hypothesis. In summary: Percolator is essentially the trade-off as MapReduce – sacrificing latency for volume-cost-sophistication but more temperate, more rounded, less-radical.

Unfortunately I haven’t enough time to enjoy the paper as it should be enjoyed with easy weekend-style reading. So inaccuracies may have been infiltrated in:

Percolator is big-data ACID-compliant transaction-processing non-relational DBMS.
Percolator fits most NoSQL definitions and therefore it is a NoSQL.
Percolator continuously mutates dataset (called data corpus in the paper) with full transactional semantics and in the sizes of tens of petabytes on thousands of nodes.
Percolator uses a message-queue style approach for processing crawled data. Meaning, it processes the crawled pages continuously as they arrive updating the index database transactionaly.
BEFORE Percolator: Indexing was done in stages taking weeks. All crawled data was accumulated and staged first, then pass-after-pass transformed into index. 100-passes were quoted in the paper as I remember. When the cycle was completed a new one was initiated. Few weeks latency after content was published and before it appeared in Google search results were considered too long in twitter age, so Google implemented some shortcuts allowing preliminary results to show in search before the cycle is completed.
Percolator doesn’t have declarative query language.
No joins.
Self-stated ~3% single node efficiency relative to the state-of-the-art DBMS system on single node. That’s the price for handling (which is transactional mutating) high-volume dataset… and relatively cheaply. Kudos for Google to being so open on this and not exercising in term-obfuscation. On the other hand, they can afford it… they don’t have to sell it tomorrow on rather competitive NoSQL market
Thread-per-transaction model. Heavily threaded many-core servers as I understand.

Architecturally reminds me MoM (Message Oriented Middleware) with transactional queues and guarantied delivery.

Definitely to be continued…

other Percolator blog posts:

http://www.infoq.com/news/2010/10/google-percolator
http://www.theregister.co.uk/2010/09/24/google_percolator
http://coolthingoftheday.blogspot.com/2010/10/percolator-question-is-how-does-google.html
http://www.quora.com/What-is-Google-Percolator

How scalable is linux kernel on 48-core machine?

Camuel Gilyadov — Tue, 12 Oct 2010 00:40:25 +0000

According to this excellent and comprehensive research with some kernel hacking ~x33 speedup (compared to single core) is possible. For example PostgreSQL running on 48 cores gives ~x4 out of the box and after kernel/postgreSQL patches are applied it grows to ~x33. Assuming IO can keep up of course.

Is NoSQL a DBMS?

Camuel Gilyadov — Tue, 12 Oct 2010 00:14:30 +0000

Yes, it is.

Proof? – By definition.

But Wikipedia…… – fixed.

CAP equivalent for analytics?

Camuel Gilyadov — Sat, 09 Oct 2010 02:46:34 +0000

CAP theorem deals with trade-off in transactional system. It doesn’t need an introduction, unless of course you have been busy on the moon for last couple of years. In this case you can easily Google for good intros. Here is a wikipedia entry on the subject.

I was thinking how would I build an ideal analytics system. Quickly came realization that all “care abouts” cannot be satisfied simultaneously, even assuming enough time for development. Some desirable properties must be sacrificed in favor for others, hence architectural trade-offs are unavoidable in principle. I immediately had déjà vu regarding CAP. So the following is my take on the subject:

SVLC hypothesis regarding architectural trade-offs in analytics

I haven’t came to rigorous definition yet, here is an intuitive one: Current technology doesn’t allow implementation of a single analytics system that is SVLC which is simultaneously sophisticated, high-volume, low-latency and low-cost .One of these four properties must be sacrificed, the extent to which it is sacrificied determines the extend to which other properties could potentially be implemented.

Deep dive for the brave souls

Let’s reiterate the desired system properties first (see ideal analytics system):

Deep Sophistication => …free-form SQL:2008 with multi-way joins of 2 and more big tables, sorts of big tables and all the rest of data heavy lifting.
High Volume => …handling big data volumes, Let’s cap it 1PB meanwhile for easier thinking.
Low Latency => …subsecond response time for the query on average. A more concrete description is that latency must be low enough to allow analyst working interactively in conversational manner with the system.
Low-Cost => … I’ll define it as commodity hardware and software must not exceed hardware costs. More rigorously? $1/GB/month for actively queried data is my very rough estimation for low-cost.
Multi-form => any data, relational, serialized objects, text etc….
Security => can speak for itself

I found that multi-formness and security doesn’t interfere with implementing the rest of properties and can in principal always be implemented in satisfactory way without major compromises. Some nuances exists tough, but I’ll ignore them for clearness. So removing them and getting the following list:

1. Sophistication (deep) => S

2. Volume (high) => V

3. Latency (low) => L

4. Cost (low) => C

These four are highly inter-related and form а constraint system . Implementing one to full extent hampers the rest. Let’s see what trade-offs we have here. Four properties that is 6 potential simple 2-extremes trade-offs. Let’s settle on geometric tetrahedron to model the architectural trade-off space. Four properties correspond to four vertexes and six trade-offs correspond to six edges. Then we model particular trade-off by putting a point on the corresponding edge. So we get something like this:

Okey, so far so good. Now, I’ll try to be а devil advocate and challenge my point that any trade-offs are necessary in the first place. So let’s review the system denoted as

SVLC=> high-volume, low-latency, deep analytics, low cost

Because it is low-latency it will need I/O throughput adequate to scan whole dataset quickly and since it is high-volume (see above for quantitative definition) meaning aforementioned dataset is big, it will need a large number of individual nodes in cluster to provide the required aggregated adequate I/O throughput. The number of machines is further increased with low-cost requirement meaning that simpler servers that are in mainstream sweetspot must be purchased. Therefore system becomes extremely distributed and data being dispersed all over it. The low-cost networking usually mean TCP/IP that is high-overhead, high-latency and low-throughput. Deep Sophistication analytics requires performing complex data-intensive operations like full sorting of big datasets, joining big tables or just simple select distinct over big data that will inevitably have long latencies. Once latency is long enough that probability of node failing mid-query become non-neglectable. Latency increase becomes self-perpetuating because of required finer grain of intermediate result materialization. This is needed to prevent never-ending query restarting and provide a kind of resumable queries. Not other solutions to resumable queries are documented except MapReduce-style intermediate result materialization. This ultimately makes latency batch-class long violating low-latency requirement.

I guess my proof miss the required rigor to be considered seriously by academics, I’m just an engineer I love to see it reworked to something more serious tough. I just hope to get the point across and to be of value to engineers and practicing architects.

Anyhow this is the base of my hypothesis showing that it impossible to achieve full SVLC using today technology.

Let’s consider other cases where we give up something. It is easy to visualize such trade-off as a 2D plane dissecting tetrahedron. The three points were three edges are cut corresponds to three trade-offs. For simplicity I’ll elaborate only radical trade-offs in this post. Radical trade-offs are those were on all six trade-off edges one extreme is selected and this corresponds to putting a trade-off point on one of vertices. Most real-world system make temperate trade-offs that corresponds to the plane that dissects the tetrahedron into sizable parts. Moreover real-world system, especially available from commercial vendors, are a toolbox kind of a system. Meaning that system consists of a set of tools where each one makes a different set of trade-offs. Then it is up to engineer to choose the right tool for the job to the toolbox. However, toolbox approach is not a loophole for this hypothesis, because properties of the different tools don’t add up in desired way. For example the simultaneous use of expensive tool and low-cost tool is still expensive; the simultaneous use of low-latency and high-latency is high-latency. Nevertheless, toolbox approach is best one for real-world problems. Because real-world problems are usually decomposed to a number of sub problems where each may require different tool.

Well…back to the radical systems… Let’s consider all four cases where we completely give up one property to max out the rest three:

SVL => high-volume, low-latency, deep analytics …giving up Cost… seems to be implementable. In its pure form it reminds classic national security style system. Subsecond querying petabyte-scale dataset with arbitrary joins. Heavily over provisioned Netezza / Exadata / Greenplum / Aster and other MPP-system could do it I believe. Data kept in huge RAM or on flash, huge I/O is available to scan the whole dataset in matter of seconds. High-speed, low-overhead networking is available to with huge bi-section network bandwidth capable to shuffle the whole dataset in matter of seconds. Infiniband/RDMA are the best probably. How bad Cost can be here? Well… unhealthy to imagine. Throw some numbers in anyway? Will do some back of envelope calculation in my future posts.

SVC => high-volume, low-cost, deep analytics …giving up Latency… seems to be implementable, in fact it is MapReduce territory, Hadoop natural habitat. Are ETL systems SVC? I think no, because while they given up Latency they haven’t kept on Volume. How bad is Latency? well… forget interactivity, create queuing system and get notified when the job is done. If too slow add servers. If some interactive experimentation is needed, use VLC first to develop and prove your hypothesis and only than crunch the data with SVC. Since cost is involved I guess Hadoop MapReduce is really a king here. Tough if Aster licenses for example are comparable to commodity cluster overall cost and is not many multiples of it, then it could fit the category nicely. Otherwise it will make suboptimal (considering my model context not in wider sense!) great SV system. The great MapReduce debate is not for nothing!

SLC => low-latency, low-cost, deep analytics …seems to be implementable in a minute, just start your favorite spreadsheet application You will be shocked how much data Excel crunches in just few seconds, nowadays. Most traditional BI tools are in this category too. Heck, if not for BigData, the analytics industry will be as would become as exciting as enterprise payroll systems. Though, innovation is possible even there. Heck, 99% of BI is fully feasible to be done completely in-memory, often on single server and the deployment must be really low-risk low-cost very-rapid if done correctly. Most cloud BI vendors are also in this category. “R-project” is here too. This was Kickfire beloved spot as well as is now for QlikTech & GoofData, PivotLink and etc… So pretty much all BI vendors are here except MPP heavy-lifters. How bad Volumes are limited? Well with CPU-DRAM bandwidth being 50GB/sec and DRAM sizes 64GB on common commodity servers I think crunching few tens GB should be well possible in matter of seconds, if not for implementation sloppiness, and with literally pocket money (average enterprise’s pocket not mine… yet).

VLC => high-volume, low-latency, low-cost …giving up Sophistication…seems to be implementable, that is doing a simple scan and giving up the Sophistication, particularly joins. Dremel and BigQuery seem following this approach. How bad is giving up Sophistication? Well, it all depends on how pre-joined/nested dataset is. With normalized schemas, well… unavailability of joins makes it pretty much impractical implement any usable analytics. However, with star-schema and particularly nested data (with some extensive pre-joins even if it means some redundancy), this can work wonders to vast majority of queries, completing them in seconds on even large datasets. However, no pre-join strategy will work for 100% of queries and functions like COUNT DISTINCT must be approximated when run over big dataset like described in Dremel paper. Also I’ll assign sampling strategy to this category, because sophistication also means accuracy here. One clarification: only joins of several big tables are sacrificed here, joins of big table with even large number of small tables are perfectly okay and done on the fly during the scan. Sorts of big table before it was reduced significantly to manageable size is also sacrificed in this approach, however approximation algorithms can be used for this and then it will be okay too.

Hence the conclusion: only 3 of 4 SVLC properties can be implemented in full extend in single analytic system. The hypothesis goes that any attempt that allegedly violates it, in fact either is no a single system or impairment is latent in one or more properties.

[TODO: rewrite] The extended hypothesis for fractional cases:

Systems/trade-offs may be radical or temperate. Radical trade-off completely gives up one of four properties of the system. Temperate trade-off gives-up the property only fractionally on expense of giving-up other properties also fractionally.
Most real-world systems are complex. They are a set of tools, where each separate tool is a concrete trade-off. Then the user of such system can use different tools with different trade-off sequentially or simultaneously. This may seems as way out of the restraint; however it is not, because properties of separate tools don’t add up in desired way. For example the simultaneous use of expensive tool and low-cost tool is still expensive; the simultaneous use of low-latency and high-latency is high-latency. Nevertheless, toolbox approach is best one for real-world problems. Because real-world problems are usually decomposed to a number of sub problems where each may require different tool.
Most often trade-offs of real-world systems are temperate.

Analytics Patterns

Camuel Gilyadov — Fri, 08 Oct 2010 16:22:42 +0000

Unsatisfied by my previous post‘s Advanced Analytics definition and giving it a thought of what is advanced methods in analytics I realized that analytics industry miss a good analytics pattern catalog. A list of common problems followed by a list of common industry-consensus solutions to them. An equivalent of GoF design patterns to analytics. The list, where each list item starts from brief description of common recurring analytics problem and follows by elaboration by commonly accepted solutions to this problem followed by mandatory example section illustrating the solution using widely available tools.

Software engineers stolen this idea from the real architects (those dealing with a concrete structures not an abstract ones ) 15 years ago. They haven’t avoided initial short period of mass obsession and abuse of the concept… who does? But eventually it worked out quite well for them us. I wonder if analytics industry could leverage these experience and create a catalog of some 25-50 most common patterns. Pattern descriptions in a catalog not to exceed few pages and number of patterns limited to few tens, making it wide industry adoption feasible.

What you think? Any ideas? I’ll try to make a first step by dumping patterns from my head right now (it is by no way a finished work):

I’ll call it analytics patterns:

1. Predictive Analytics. That was the easiest for me. I was involved into it for the first time some 12 years ago and developing what is now http://www.oracle.com/demantra/index.html. The system was used mostly to forecast sales taking into account an array of causal factors like seasonality, marketing campaigns, historical growth rates and etc. The problem is that there is a lot of time-based historic data available and it is required to forecast future values in the context of given historic data. The basic mechanism of implementing Predictive Analytics is to find or less preferably to develop a suitable mathematical model that can model closely (but be cautious about overfitting) existing data, usually a time-series data and then use the model to induce forecasted values. In simple terms it is a case of extrapolation. Correct me if I’m wrong. As it was the case in 90-ties I’m pretty sure it is the case now, that exotic hardcore AI approaches like neural networks & genetic programming are best kept exclusively for moonlighting experiments and as material for cooler conversation the next morning. With deadlines defined and limited budget it is best to stick to proven techniques to achieve quick wins. I think the value of working forecasting is self evident.

2. Clustering. Well not the heavy noisy one in a cold hall but the statistics sub-discipline called better cluster-analysis. The problem here is that a lot of high-dimensionality data is available and it is required to discover groups with similar observations in other words automatically classify them. It is implemented by searching for correlations grouping the records according to the discovered correlations. What it is good for? Well in simple terms it helps to discriminate different kinds of objects and observe the specific properties of each kind. Without such grouping, one would be able only to observe properties that all objects exhibit or alternatively go object by object and observe it in isolation.

3. Risk Analysis - particularly through Monte-Carlo simulation. It is not called Monte-Carlo because it is invented there it called so because of reliance on random numbers akin Monte-Carlo casinos. Random numbers are proved most effective way to simulate mathematical model with large number of free-variables. With advent of computers it became a whole lot easier than using the book.

4. Given telecom event stream, run events through the rules engine to detect and prevent telecom fraud in real-time. This is essentially CEP engine and usually implemented by creating a state-machine per rule and running the events through it. Special version of stream sql is used. Similar scheme can be used for real-time click fraud prevention.
5. Given serialized object data or nested data allow running ad-hoc interactive queries over it in BigQuery fashion.
6. Given normalized relational model, allow running any ad-hoc queries. For common joins create a materialized view to speed up joins.
7. Canned reports. I guess they are good also for some cases…….
8. OLAP/Star schema when to use? ……

What else?

Of course it is just a first step and to do it correctly it will be a project in itself, in form of a book most probably. However, as one Chinese proverb goes “A journey of a thousand miles begins with a single step”.

Feature list of ultimate BigData analytics

Camuel Gilyadov — Fri, 08 Oct 2010 14:58:28 +0000

Volume Scalability => the solution must handle high volumes of data, meaning the cost must scale linearly in the range of 10GB – 10PB.
Latency Scalability => the solution must be interactive or batch, and cost must scale linearly in the range of 1 msec – 1 week.
Sophistication Scalability => the solution must support simple summing scans or complex multi-way joins and statistics functionality and the cost must scale linearly in the range of simplistic scans to full blown SQL:2008/MDX/imperative in-database-analytics/MapReduce. Report/index viewing is not considered as analytics at all and particularly as not low-sophistication analytics. Report/index creation is analytics and can be of varied sophistication degree. ETL systems is considered as independent analytic systems.
Security => any unauthorized access to data must be prevented and in the same time, in-place data analysis (like predicate evaluation) must be possible and resource-efficient.
- Keeping data always encryption and keeping keys always on client will not work. It will require shipping all the data to the client and is non-starter for big data analytics. So compromises must be made. The issue is especially contentious in public cloud setting.
- If data is stored encrypted and is continuously decrypted in-place for predicate evaluation, for example, it means that keys must kept in same place (at least temporarily) and it compromises the whole scheme altogether, flooring its cost-benefit factor. The cost of decryption is pretty high.
- De-identification of all fields may work; random scaling may be applied to numeric fields with subsequent query/result rewrite.
- Security-by-obscurity methods and defense-in-depth approach may have good cost-benefit factors matching or exceeding overall security for in-house approach.
Cost => must have low-TCO that scales linearly to dataset size and the load factor caused by submitted queries. The breakdown (assuming cloud):
- Storage component linear to dataset size. Economies of scale must bring this cost down significantly. Eventually it must be cheaper than on-site storage.
- Computing component linear to load with infinite intra-query automatic elasticity. Guarantied elasticity may bear a fixed premium proportional to guarantied capacity. Minor failures of cloud component must not restart long running queries.
- Bandwidth component. Fedexing hard-drives are by far the cheapest way to upload data, and then query results are really small. How much information human can comprehend instantly after all?
Multi-form =>
- normalized relational
- star-schema
- cubes
- serialized objects / nested data.
- text
- media
- spatial
- bio / scientific
- topographical
- and other data forms must be equally well supported and cross-queried.

Terminology: Analysis vs. analytics and more…

Camuel Gilyadov — Fri, 08 Oct 2010 00:10:39 +0000

I see a lot of confusion in the usage of newer terms in analytics. I do confuse them myself occasionally. I find it funny that the industry as serious as analytics tolerates constant renewal of its basic terminology. Yet, I confess, I’m very guilty of it myself. I do enjoy the freshness and the novelty of newer terms even being fully aware that is fake by a large extent.

In this post I’ll take a step to clear the confusion on few most basic terms: analysis vs. analytics vs. BI and all their common derivatives.

The Spoiler (the quick answer):

Analysis is the examination process itself where analytics is the supporting technology and associated tools. BI is quite synonymous to analytics in IT context. Advanced Analytics, Business Analytics, Data Analytics, Analytics Software, Analytics Technology are almost always marketing pleonasms (redundant expressions) and can be safely substituted by just ‘analytics’. ‘Data analysis’ is yet another pleonasm. Compound expressions of these words such as ‘BI Analytic Technology’ are yet again pleonasms albeit of higher degrees. Some nuances exist tough and are elaborated in this post.

The deep dive for the brave souls:

Let’s attempt to properly define the terms and then carefully examine the alleged differences.

Before we dive in, a word of caution: definition by synonyms is wrong. It causes stack overflow in the mind of programmers. For example “analysis” => “critical examination” => “examination” => “critical inspection” => “inspection” = “critical examination” => “f…”=> “why I just don’t make myself a cup of coffee?”.

You can check what makes a good definition and common mistakes following……. Well apparently I haven’t found in a quick look a good material on proper definition but for fallacies there is a nice wikipedia article. If you find a good article on what makes a good definition drop me a note / comment, if so it would include a definition definition.

Let’s start….

What is analysis?

Analysis is a pretty old, well understood term and essentially means “breaking down” or “decomposition”. More accurately – “the process of decomposing complex entity into simpler components for easier comprehension of aforementioned entity”. As a child I did a lot of it to the toys and electronic appliances around me. I challenge you to find a better and more concise definition than mine above (it is a matter of taste but anyway). Here is some links to save you time:

http://www.google.com/search?q=define:+analysis

http://en.wikipedia.org/wiki/Analysis

http://en.wiktionary.org/wiki/analysis

http://thesaurus.com/browse/analysis

What is analytics?

Analytics is a newer term related to analysis and looking it up will usually only add to confusion since definitions vary and are fuzzy and seems to be context-dependent. Focusing on IT context I went through many usage examples and definitions. My verdict is that analytics just means: the technology and the associated tools for data analysis.

If so, then ‘data analytics technology’ is a double redundant (or more accurately pleonasmic) term because analytics is a technology by itself and it’s clearly obvious that in IT context only data can be analyzed. Hence the above phrase can be abbreviated as ‘analytics’ without any impairment to the meaning. Same goes to ‘data analytics tools’. However, when IT context is not implied, something like ’data analytics software’ could be appropriate. In this case ‘data’ links it to IT and ‘software’ further narrows its meaning.

Incorrect usage (according to my interpretation):

Software company most probably doesn’t develop “next-gen data-analysis” but “next-gen data-analytics”. And by the same token “cloud computing analysis” means examining cloud computing concept not using cloud computing as a tool for doing analysis. In latter case “cloud analytics” must be used.

Analyst performs in-database analysis or applies in-database analytics to calculate something. However analyst doesn’t performs in-database analytics.

If you look the terms used by QlikView folks you will find pretty much all the above terns used interchangeably, including the statement that they “provide fast, powerful and visual in-memory business analysis”. One may think that they provide business advise for companies in memory business. Terminology aside no bashing QlikView, it is excellent analytics software and one of very few that just works out of the box.

What is analytical?

In regard to data it means that it compiled using analysis. In regard to the tool it means that it is intended for analysis.

Data Analysis and Data Analytics

As already mentioned in IT context both are pleonasms and non-data analysis or non-data analytics are both oxymorons. So why stress data anyway? Mostly there is no reason and in other cases it is there to hint IT context. For example for bankers it is ‘financial analytics’ but for IT folks in the bank it is ‘data analytics’.

What ‘advanced analytics’ hints then?

Well, I guess it is a way for a vendor to indicate that their analytics is less stagnating than of their competitors Seriously tough, I guess it means, where it really used to mean anything that statistics methods are implemented like: predictive modeling and clustering. Also it has strong connotations with Gartner press-release naming it second most promising technology for 2010.

What is wrong with just sticking with older BI term?

It is a fashion thing I guess…. who said IT is boring? We could easily challenge Parisian fashion industry on that. Seriously tough, BI is considered as more comprehensive approach encompassing many aspect and is usually cross departmental, notorious for high project failure rate. At least that way younger startups portrait it. On the other hand ‘data analytics’ is portrait something more simple and more of a ‘quick wins’ departmental solution. Something akin ‘Data mart’. And don’t ask me what is the difference with data marts. Have I mentioned fashion thing.

Well aside of fashion, there are more rational reasons too of course. Startup pitching BI, sounds boring at best with Microsoft, IBM, Oracle dominating it. It must define a new disruptive category and then dominate it. Who read Christiansen could remember that no new terms is necessary for disruption. Somehow it is easier to communicate using new terms. I would love to believe that it is not deceiving. In fact masquerading advanced analytics as something completely distinct may work all the way from investors to the customer’s CIO that may find suspicious that he is purchasing too many BI solutions, and purchasing first “advanced analytics” solution and early enough may seems quite smart and a sign that his organization is far from being in stagnation, especially just after reading Gartner press-release.

UPDATE:

Another view on the subject: http://www.b-eye-network.com/view/13797

Yet another one: http://blogs.forrester.com/boris_evelson/10-06-07-bi_vs_analytics

The story behind this blog

Camuel Gilyadov — Fri, 01 Oct 2010 08:47:24 +0000

The story behind this blog