Key Concepts Data Structure and Algorithm In Apache Cassandra

Connect with

Apache Cassandra
In this post, I tried to list down key concept, data structure, and Algorithm used. Few of the concept picked from Amazon’s Dynamo and few of them picked from Google’s BigTable, that is why, Cassandra is best known for the rich features in NOSQL space.

Key Concept in Cassandra

Following are few of the key Concept, Data structures and Algorithm used in Apache Cassandra.

  • Gossip protocol:
    The Gossip protocol is similar to real-world gossip, where a node says “A” tells a few of its peers in the cluster what it knows about the state of a node say “B”. Those nodes tell a few other nodes about node “B”, and over a period of time, all the nodes know about node “B” and its peer. Cassandra is a peer-to-peer system with no single point of failure, the cluster topology information is communicated via the Gossip protocol.
  • Partitioners:
    A partitioner determines how data is distributed across the nodes in the cluster. The Murmur3Partitioner is the default partitioner. You can also create your own partitioner by implementing the org.apache.cassandra.dht.IPartitioner class and placing it on Cassandra’s classpath.
  • Replication Strategies:
    The first replica will always be the node that claims the range in which the token falls, but the remainder of the replicas are placed according to the replication strategy chosen while creating of keyspace. The first replica will always be the node that claims the range in which the token falls, but the remainder of the replicas are placed according to the replication strategy.
  • Commit Log:
    When perform a write operation, it’s immediately written to a commit log. The commit log is a crash-recovery mechanism that supports Cassandra’s durability goals.
  • memtable:
    memtable is memory-resident data structure. After it’s written to the commit log, the value is written to a memory-resident data structure called the memtable.
  • SSTable:
    SSTable is a compaction of Sorted String Table.When the number of objects stored in the memtable reaches a threshold, the contents of the memtable are flushed to disk in a file called an SSTable. The SSTable is a concept borrowed from Google’s Bigtable. Once a memtable is flushed to disk as an SSTable, it is immutable and cannot be changed by the application.
  • Tombstone:
    Tombstone is a similar like soft-delete concept implementation in Cassandra. A tombstone is a deletion marker that is required to suppress older data in SSTables until compaction can run.
  • Bloom Filters:
    Bloom filters are very fast, non-deterministic algorithms for existence checking whether an element is a member of a set. They are non-deterministic because it is possible to get a false-positive read from a Bloom filter, but not a false-negative. Bloom filters are used in other distributed database and caching technologies: Apache Hadoop, Google’s Bigtable, and Squid Proxy Cache.
  • Snitches: A snitch determines which datacenters and racks nodes belong to. This help while replication of data to another node.

Connect with

Leave a Reply

Your email address will not be published. Required fields are marked *