Redis Persistence

Databases, NoSQL, Redis August 29, 2013 1 Comment

In my today’s post i’d like to touch on Redis persistence mechanisms.

 

What we can choose from are basically two options (or the combination of those):

  • The RDB persistence – which performs point-in-time snapshots of your dataset at specified intervals.
  • The AOF (append-only file) persistence – which logs every write operation received by the server, that can later be “played” again at server startup, reconstructing the original dataset (commands are logged using the same format as the Redis protocol itself).

 

Both of those options are controlled by two different groups of configuration settings in the redis.conf file:

  • RDB persistence:
    • save <seconds> <changes> – saving the DB on disk – the command will save the DB if both the given number of seconds and the given number of write operations against the DB occurred. You can have multiple save configurations “stacked” one after another, handling saves in different “seconds/changes” scenarios or you can disable saving at all commenting out all the “save” lines.
    • stop-writes-on-bgsave-error <yes|no> – by default Redis will stop accepting writes if RDB snapshots are enabled (at least one save point) and the latest background save failed. This will make the user aware (in an hard way) that data is not persisting on disk properly. If the background saving process will start working again Redis will automatically allow writes again.
    • rdbcompression <yes|no> – compression of string objects using LZF when dump .rdb databases.
    • rdbchecksum <yes|no> – since version 5 of RDB a CRC64 checksum is placed at the end of the file which makes the format more resistant to corruption but there is a performance hit to pay (around 10%) when saving and loading RDB files.
    • dbfilename <name> – The filename (default dump.rdb) where to dump the DB.
    • dir <path> – The working directory (default value is ./) where the DB will be written. The Append Only File will also be created inside this directory
  • AOF persistence:
    • appendonly <yes|no> – controls whether AOF mode should be turned on. By default Redis asynchronously

      dumps the dataset on disk (RDB Persistence) which is a mode good enough in many applications, but an issue with the Redis process or 

      a power outage may result into a few minutes of writes lost (depending on 

      the configured save points). AOF provides much better durability. Using the default data 

      fsync policy Redis can lose just one second of writes in a dramatic event like a server power outage, 

      or a single write if something wrong with the Redis process itself happens, but the operating system 

      is still running correctly. AOF and RDB persistence can be enabled at the same and they play very nicely

      together. If the AOF is enabled on startup Redis will load the AOF, that is the file with the better 

      durability guarantees.

    • appendfilename <name> – The name of the append only file (default: “appendonly.aof”)

    • appendfsync <mode> – mode in which fsync should operate. The fsync() call tells the Operating System to actually write data on disk 

      instead to wait for more data in the output buffer. Some OS will really flush 

      data on disk, some other OS will just try to do it ASAP. Redis supports three different modes:

      • <no>: don’t fsync, just let the OS flush the data when it wants. Faster.
      • <always>: fsync after every write to the append only log . Slow, Safest.
      • <everysec>: fsync only one time every second. Compromise. (default)
    • no-appendfsync-on-rewrite <yes|no> – when the AOF fsync policy is set to always or everysec, and a 

      background saving process (a background save or AOF log background rewriting) is 

      performing a lot of I/O against the disk, in some Linux configurations R

      edis may block too long on the fsync() call. In order to mitigate this problem it’s possible to use this option 

      which will prevent fsync() from being called in the main process while a BGSAVE or BGREWRITEAOF is in progress. 

      In practical terms, this means that it is 

      possible to lose up to 30 seconds of log in the worst scenario (with the default 

      Linux settings).

    • auto-aof-rewrite-percentage <percentage> and auto-aof-rewrite-min-size <size> – are both related to automatic rewrite of the append only file. Redis is able to automatically rewrite the log file (implicitly calling BGREWRITEAOF) when the AOF log size grows by the specified percentage. This is how it works: Redis remembers the size of the AOF file after the latest rewrite (if no rewrite has happened since the restart, the size of the AOF at startup is used). This base size is compared to the current size. If the current size is bigger than the specified percentage, the rewrite is triggered. Also you need to specify a minimal size for the AOF file to be rewritten, this is useful to avoid rewriting the AOF file even if the percentage increase is reached but it is still pretty small. Specify a percentage of zero in order to disable the automatic AOF rewrite feature.

 

Advantages and disadvantages of both methods (redis.io):

  • RDB advantages
    • RDB is a very compact single-file point-in-time representation of your Redis data. RDB files are perfect for backups. For instance you may want to archive your RDB files every hour for the latest 24 hours, and to save an RDB snapshot every day for 30 days. This allows you to easily restore different versions of the data set in case of disasters.
    • RDB is very good for disaster recovery, being a single compact file can be transfered to far data centers, or on Amazon S3 (possibly encrypted).
    • RDB maximizes Redis performances since the only work the Redis parent process needs to do in order to persist is forking a child that will do all the rest. The parent instance will never perform disk I/O or alike.
    • RDB allows faster restarts with big datasets compared to AOF.
  • RDB disadvantages
    • RDB is NOT good if you need to minimize the chance of data loss in case Redis stops working (for example after a power outage). You can configure different save points where an RDB is produced (for instance after at least five minutes and 100 writes against the data set, but you can have multiple save points). However you’ll usually create an RDB snapshot every five minutes or more, so in case of Redis stopping working without a correct shutdown for any reason you should be prepared to lose the latest minutes of data.
    • RDB needs to fork() often in order to persist on disk using a child process. Fork() can be time consuming if the dataset is big, and may result in Redis to stop serving clients for some millisecond or even for one second if the dataset is very big and the CPU performance not great. AOF also needs to fork() but you can tune how often you want to rewrite your logs without any trade-off on durability.
  • AOF advantages
    • Using AOF Redis is much more durable: you can have different fsync policies: no fsync at all, fsync every second, fsync at every query. With the default policy of fsync every second write performances are still great (fsync is performed using a background thread and the main thread will try hard to perform writes when no fsync is in progress.) but you can only lose one second worth of writes.
    • The AOF log is an append only log, so there are no seeks, nor corruption problems if there is a power outage. Even if the log ends with an half-written command for some reason (disk full or other reasons) the redis-check-aof tool is able to fix it easily.
    • Redis is able to automatically rewrite the AOF in background when it gets too big. The rewrite is completely safe as while Redis continues appending to the old file, a completely new one is produced with the minimal set of operations needed to create the current data set, and once this second file is ready Redis switches the two and starts appending to the new one.
    • AOF contains a log of all the operations one after the other in an easy to understand and parse format. You can even easily export an AOF file. For instance even if you flushed everything for an error using a FLUSHALL command, if no rewrite of the log was performed in the meantime you can still save your data set just stopping the server, removing the latest command, and restarting Redis again.
  • AOF disadvantages
    • AOF files are usually bigger than the equivalent RDB files for the same dataset.
    • AOF can be slower then RDB depending on the exact fsync policy. In general with fsync set to every second performances are still very high, and with fsync disabled it should be exactly as fast as RDB even under high load. Still RDB is able to provide more guarantees about the maximum latency even in the case of an huge write load.
    • Redis AOF works incrementally updating an existing state, like MySQL or MongoDB does, while the RDB snapshotting creates everything from scratch again and again, that is conceptually more robust.

 

The general advice from Redis team is that you should use both persistence methods if you want a degree of data safety comparable to what PostgreSQL can provide you.

 

 

Take care!

 

Resources:

JSON Activity Streams 1.0

Others, Specifications August 28, 2013

In this post i’d like to address the subject of Activity Streams spec., something I’ve been working with recently in one of the projects.

 

Let’s start with a definition of an activity stream (Wikipedia):

  • “An activity stream is a list of recent activities performed by an individual, typically on a single website. For example, Facebook’s News Feed is an activity stream. Since the introduction of the News Feed on September 6, 2006, other major websites have introduced similar implementations for their own users. Since the proliferation of activity streams on websites, there have been calls to standardize the format so that websites could interact with a stream provided by another website. The Activity Streams project, for example, is an effort to develop an activity stream protocol to syndicate activities across social Web applications. Several major websites with activity stream implementations have already opened up their activity streams to developers to use, including Facebook and MySpace. Though activity stream arises from social networking, nowadays it has become an essential part of business software. Enterprise social software is used in different types of companies to organize their internal communication and acts as an important addition to traditional corporate intranet.”

 

Activity Streams is an open format specification for activity stream protocols, which are used to syndicate activities taken in social web applications and services.

 

JSON Activity Streams 1.0 is the name of the specification published on May 2011 by the working group consisting of: J. Snell (IBM), M. Atkins (SAY Media), W. Norris (Google), C. Messina (Citizen Agency, Google), M. Wilkinson (MySpace, Facebook, VMware), R. Dolin (Microsoft).

 

On the homepage of the specification activitystrea.ms you’ll find more details including a list of early adopters (BBC, Gnip, Google, Buzz, Gowalla, IBM, MySpace, Opera, Socialcast, Superfeedr,
TypePad, Windows Live, YIID, and many others).

 

Introduction:

  • In its simplest form, an activity consists of an actor, a verb, an an object, and a target.
  • It tells the story of a person performing an action on or with an object — “Geraldine posted a photo to her album” or “John shared a video”. In most cases these components will be explicit, but they may also be implied.
  • Goal of the specification is to provide sufficient metadata about an activity such that a consumer of the data can present it to a user in a rich human-friendly format. (this may include constructing readable sentences about the activity that occurred, visual representations of the activity, or combining similar activities for display).
  • The basic properties that comprise the description of an activity are defined in the appropriate sections of the specification.
  • Within the specification, an object is a thing, real or imaginary, which participates in an activity. It may be the entity performing the activity, or the entity on which the activity was performed.
  • An object consists of properties defined in appropriate sections of the specification. Certain object types may further refine the meaning of these properties, or they may define additional properties.
  • Some types of objects may have an alternative visual representation in the form of an image, video or embedded HTML fragments. A Media Link represents a hyperlink to such resources.
  • An Activity Stream is a collection one or more individual activities. The relationship between the activities within the collection is undefined by this specification.

 

Following is a simple, minimal example of a JSON serialized activity:

{
    "published": "2011-02-10T15:04:55Z",
    "actor": {
        "url": "http://example.org/martin",
        "objectType" : "person",
        "id": "tag:example.org,2011:martin",
        "image": {
            "url": "http://example.org/martin/image",
            "width": 250,
            "height": 250
        },
        "displayName": "Martin Smith"
    },
    "verb": "post",
    "object" : {
        "url": "http://example.org/blog/2011/02/entry",
        "id": "tag:example.org,2011:abc123/xyz"
    },
    "target" : {
        "url": "http://example.org/blog/",
        "objectType": "blog",
        "id": "tag:example.org,2011:abc123",
        "displayName": "Martin's Blog"
    }
}

 

To give you an idea on the “breadth” of the spec., and how many various activities got its individual verb, take a look at the following complete list of “verbs”:

  • accept – Indicates that that the actor has accepted the object. For instance, a person accepting an award, or accepting an assignment.
  • access – Indicates that the actor has accessed the object. For instance, a person accessing a room, or accessing a file.
  • acknowledge – Indicates that the actor has acknowledged the object. This effectively signals that the actor is aware of the object’s existence.
  • add – Indicates that the actor has added the object to the target. For instance, adding a photo to an album.
  • agree – Indicates that the actor agrees with the object. For example, a person agreeing with an argument, or expressing agreement with a particular issue.
  • append – Indicates that the actor has appended the object to the target. For instance, a person appending a new record to a database.
  • approve – Indicates that the actor has approved the object. For instance, a manager might approve a travel request.
  • archive – Indicates that the actor has archived the object.
  • assign – Indicates that the actor has assigned the object to the target.
  • at – Indicates that the actor is currently located at the object. For instance, a person being at a specific physical location.
  • attach – Indicates that the actor has attached the object to the target.For instance, a person attaching a file to a wiki page or an email.
  • attend – Indicates that the actor has attended the object. For instance, a person attending a meeting.
  • author – Indicates that the actor has authored the object. Note that this is a more specific form of the verb “create”.
  • authorize – Indicates that the actor has authorized the object. If a target is specified, it means that the authorization is specifically in regards to the target. For instance, a service can authorize a person to access a given application; in which case the actor is the service, the object is the person, and the target is the application. In contrast, a person can authorize a request; in which case the actor is the person and the object is the request and there might be no explicit target.
  • borrow – Indicates that the actor has borrowed the object. If a target is specified, it identifies the entity from which the object was borrowed. For instance, if a person borrows a book from a library, the person is the actor, the book is the object and the library is the target.
  • build – Indicates that the actor has built the object. For example, if a person builds a model or compiles code.
  • cancel – Indicates that the actor has canceled the object. For instance, canceling a calendar event.
  • close – Indicates that the actor has closed the object. For instance, the object could represent a ticket being tracked in an issue management system.
  • complete – Indicates that the actor has completed the object.
  • confirm – Indicates that the actor has confirmed or agrees with the object. For instance, a software developer might confirm an issue reported against a product.
  • consume – Indicates that the actor has consumed the object. The specific meaning is dependent largely on the object’s type. For instance, an actor may “consume” an audio object, indicating that the actor has listened to it; or an actor may “consume” a book, indicating that the book has been read. As such, the “consume” verb is a more generic form of other more specific verbs such as “read” and “play”.
  • checkin – Indicates that the actor has checked-in to the object. For instance, a person checking-in to a Place.
  • create – Indicates that the actor has created the object.
  • delete – Indicates that the actor has deleted the object. This implies, but does not require, the permanent destruction of the object.
  • deliver – Indicates that the actor has delivered the object. For example, delivering a package.
  • deny – Indicates that the actor has denied the object. For example, a manager may deny a travel request.
  • disagree – Indicates that the actor disagrees with the object.
  • dislike – Indicates that the actor dislikes the object. Note that the “dislike” verb is distinct from the “unlike” verb which assumes that the object had been previously “liked”.
  • experience – Indicates that the actor has experienced the object in some manner. Note that, depending on the specific object types used for both the actor and object, the meaning of this verb can overlap that of the “consume” and “play” verbs. For instance, a person might “experience” a movie; or “play” the movie; or “consume” the movie. The “experience” verb can be considered a more generic form of other more specific verbs as “consume”, “play”, “watch”, “listen”, and “read”
  • favorite – Indicates that the actor marked the object as an item of special interest.
  • find – Indicates that the actor has found the object.
  • flag-as-inappropriate – Indicates that the actor has flagged the object as being inappropriate for some reason. When using this verb, thecontext property can be used to provide additional detail about why the object has been flagged.
  • follow – Indicates that the actor began following the activity of the object. In most cases, the objectType will be a “person”, but it can potentially be of any type that can sensibly generate activity. Processors MAY ignore (silently drop) successive identical “follow” activities.
  • give – Indicates that the actor is giving an object to the target. Examples include one person giving abadge object to another person. Theobject identifies the object being given. Thetarget identifies the receiver.
  • host – Indicates that the actor is hosting the object. As in hosting an event, or hosting a service.
  • ignore – Indicates that the actor has ignored the object. For instance, this verb may be used when an actor has ignored a friend request, in which case the object may be the request-friend activity.
  • insert – Indicates that the actor has inserted the object into the target.
  • install – Indicates that the actor has installed the object, as in installing an application.
  • interact – Indicates that the actor has interacted with the object. For instance, when one person interacts with another.
  • invite – Indicates that the actor has invited the object, typically a person object, to join or participate in the object described by the target. The target could, for instance, be an event, group or a service.
  • join – Indicates that the actor has become a member of the object. This specification only defines the meaning of this verb when theobject of the Activity has an objectTypeof group, though implementors need to be prepared to handle other types of objects.
  • leave – Indicates that the actor has left the object. For instance, a Person leaving a Group or checking-out of a Place.
  • like – Indicates that the actor marked the object as an item of special interest. The “like” verb is considered to be an alias of “favorite”. The two verb are semantically identical.
  • listen – Indicates that the actor has listened to the object. This is typically only applicable for objects representing audio content, such as music, an audio-book, or a radio broadcast. The “listen” verb is a more specific form of the “consume”, “experience” and “play” verbs.
  • lose – Indicates that the actor has lost the object. For instance, if a person loses a game.
  • make-friend – Indicates the creation of a friendship that is reciprocated by the object. Since this verb implies an activity on the part of its object, processors MUST NOT accept activities with this verb unless they are able to verify through some external means that there is in fact a reciprocated connection. For example, a processor may have received a guarantee from a particular publisher that the publisher will only use this Verb in cases where a reciprocal relationship exists.
  • open – Indicates that the actor has opened the object. For instance, the object could represent a ticket being tracked in an issue management system.
  • play – Indicates that the actor spent some time enjoying the object. For example, if the object is a video this indicates that the subject watched all or part of the video. The “play” verb is a more specific form of the “consume” verb.
  • present – Indicates that the actor has presented the object. For instance, when a person gives a presentation at a conference.
  • purchase – Indicates that the actor has purchased the object. If a target is specified, in indicates the entity from which the object was purchased.
  • qualify – Indicates that the actor has qualified for the object. If a target is specified, it indicates the context within which the qualification applies.
  • read – Indicates that the actor read the object. This is typically only applicable for objects representing printed or written content, such as a book, a message or a comment. The “read” verb is a more specific form of the “consume”, “experience” and “play” verbs.
  • receive – Indicates that the actor is receiving an object. Examples include a person receiving abadge object. Theobject identifies the object being received.
  • reject – Indicates that the actor has rejected the object.
  • remove – Indicates that the actor has removed the object from the target.
  • remove-friend – Indicates that the actor has removed the object from the collection of friends.
  • replace – Indicates that the actor has replaced the target with the object.
  • request – Indicates that the actor has requested the object. If a target is specified, it indicates the entity from which the object is being requested.
  • request-friend – Indicates the creation of a friendship that has not yet been reciprocated by the object.
  • resolve – Indicates that the actor has resolved the object. For instance, the object could represent a ticket being tracked in an issue management system.
  • return – Indicates that the actor has returned the object. If a target is specified, it indicates the entity to which the object was returned.
  • retract – Indicates that the actor has retracted the object. For instance, if an actor wishes to retract a previously published activity, the object would be the previously published activity that is being retracted.
  • rsvp-maybe – The “possible RSVP” verb indicates that the actor has made a possible RSVP for the object. This specification only defines the meaning of this verb when its object is an event, though implementors need to be prepared to handle other object types. The use of this verb is only appropriate when the RSVP was created by an explicit action by the actor. It is not appropriate to use this verb when a user has been added as an attendee by an event organiser or administrator.
  • rsvp-no – The “negative RSVP” verb indicates that the actor has made a negative RSVP for the object. This specification only defines the meaning of this verb when its object is an event, though implementors need to be prepared to handle other object types. The use of this verb is only appropriate when the RSVP was created by an explicit action by the actor. It is not appropriate to use this verb when a user has been added as an attendee by an event organiser or administrator.
  • rsvp-yes – The “positive RSVP” verb indicates that the actor has made a positive RSVP for an object. This specification only defines the meaning of this verb when its object is an event, though implementors need to be prepared to handle other object types. The use of this verb is only appropriate when the RSVP was created by an explicit action by the actor. It is not appropriate to use this verb when a user has been added as an attendee by an event organiser or administrator.
  • satisfy – Indicates that the actor has satisfied the object. If a target is specified, it indicate the context within which the object was satisfied. For instance, if a person satisfies the requirements for a particular challenge, the person is the actor; the requirement is the object; and the challenge is the target.
  • save – Indicates that the actor has called out the object as being of interest primarily to him- or herself. Though this action MAY be shared publicly, the implication is that the object has been saved primarily for the actor’s own benefit rather than to show it to others as would be indicated by the “share” verb.
  • schedule – Indicates that the actor has scheduled the object. For instance, scheduling a meeting.
  • search – Indicates that the actor is or has searched for the object. If a target is specified, it indicates the context within which the search is or has been conducted.
  • sell – Indicates that the actor has sold the object. If a target is specified, it indicates the entity to which the object was sold.
  • send – Indicates that the actor has sent the object. If a target is specified, it indicates the entity to which the object was sent.
  • share – Indicates that the actor has called out the object to readers. In most cases, the actor did not create the object being shared, but is instead drawing attention to it.
  • sponsor – Indicates that the actor has sponsored the object. If a target is specified, it indicates the context within which the sponsorship is offered. For instance, a company can sponsor an event; or an individual can sponsor a project; etc.
  • start – Indicates that the actor has started the object. For instance, when a person starts a project.
  • stop-following – Indicates that the actor has stopped following the object.
  • submit – Indicates that the actor has submitted the object. If a target is specified, it indicates the entity to which the object was submitted.
  • tag – Indicates that the actor has associated the object with the target. For example, if the actor specifies that a particular user appears in a photo. the object is the user and the target is the photo.
  • terminate – Indicates that the actor has terminated the object.
  • tie – Indicates that the actor has neither won or lost the object. This verb is generally only applicable when the object represents some form of competition, such as a game.
  • unfavorite – Indicates that the actor has removed the object from the collection of favorited items.
  • unlike – Indicates that the actor has removed the object from the collection of liked items.
  • unsatisfy – Indicates that the actor has not satisfied the object. If a target is specified, it indicates the context within which the object was not satisfied. For instance, if a person fails to satisfy the requirements of some particular challenge, the person is the actor; the requirement is the object and the challenge is the target.
  • unsave – Indicates that the actor has removed the object from the collection of saved items.
  • unshare – Indicates that the actor is no longer sharing the object. If a target is specified, it indicates the entity with whom the object is no longer being shared.
  • update – The “update” verb indicates that the actor has modified the object. Use of the “update” verb is generally reserved to indicate modifications to existing objects or data such as changing an existing user’s profile information.
  • use – Indicates that the actor has used the object in some manner.
  • watch – Indicates that the actor has watched the object. This verb is typically applicable only when the object represents dynamic, visible content such as a movie, a television show or a public performance. This verb is a more specific form of the verbs “experience”, “play” and “consume”.
  • win – Indicates that the actor has won the object. This verb is typically applicable only when the object represents some form of competition, such as a game.

 

The complete schema can be found on the Github page of the project, here.

 

Take care!

 

 

Resources:

Redis data sharding – part 2 – hash-based keys

Databases, Java, NoSQL, Redis, Spring Data August 23, 2013

In my previous post on Redis data sharding i introduced the concept of data sharding/partitioning and provided a small Java code example to illustrate the idea. As you noticed i was creating fixed-size “emailbuckets”, containing 1024 emails each. An email address was the key of my hash, while user id was the value. For a shard identifier i used a simple integer value (shardKey) obtained as a result of “i mod shardSize” operation.

Whereas such approach illustrates the concept well, it’s impractical in “real life” applications. This is due to a simple reason – knowing the email address alone (which may often be the only thing you’d know at some point of the app execution flow; for example when you’re using Spring Security and requesting emails “as usernames” during sign-in process), you wouldn’t be able to retrieve the corresponding userId. If you would know the algorithm by which shardKey was generated, in this case – yes – you would be able to traverse emailbuckets one-by-one looking for the appropriate email, but without that knowledge you wouldn’t be able to tell which shard the email address you’re looking for, ended up in.

One solution to that problem is to use a different key for sharding data; something that is computed directly based on the data you’re interested in partitioning. An obvious candidate here is the email address itself. If you’d be able to generate shardKey based on email address you could reproduce the same scenario every time a user provides you with his email during signing in and retrieve his userId (which you could use later on (for example) to further query another hash in Redis – “users:id” – that stores complete user profile).

 

This seems like an ideal task for a hash function… Let’s start first with some background on hashing. According to Neil Coffey’s Javamex article Introduction to hashing:

  • Hashing means using some function or algorithm to map object data (eg. content of a String object) to some representative integer value. This so-called hash code (or simply hash) can then be used as a way to narrow down our search when looking for the item…

 

Also, when you search Wikipedia after Java hashCode() function, you’ll get the following definition:

  • In the Java programming language, every class must provide a hashCode() method which digests the data stored in an instance of the class into a single hash value (a 32-bit signed integer). This hash is used by other code when storing or manipulating the instance – the values are intended to be evenly distributed for varied inputs in order to use in clustering. This property is important to the performance of hash tables and other data structures that store objects in groups (“buckets”) based on their computed hash values.

 

Looks like this is exactly what we’re interested in – …evenly distributed values for varied inputs…, which …is important to the performance of data structures that store objects in groups (shards in our case) based on their computed hash values.

Conclusion: Java hashCode() function is what we’ll proceed with.

 

More from Wikipedia on Java hashCode():

  • Starting with Java version 1.2, the java.lang.String class implements its hashCode() using a product sum algorithm over the entire text of the string.
  • An instance s of the java.lang.String class, would have a hash code h(s) defined by:
    Java String hashCode()

     

  • where terms are summed using Java 32-bit int addition, s[i] denotes the i-th character of the string, and n is the length of s.

 

Now, looking at Java docs on String.hashCode() function we can read:

  • The hash code for a String object is computed as
    s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1]

     

  • using int arithmetic, where s[i] is the ith character of the string, n is the length of the string, and ^ indicates exponentiation. (The hash value of the empty string is zero.)

 

Finally let’s take a look at some Java code of String object showing how hashCode() has actually been implemented:

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

 

An alternative (faster) implementation may look like this (from Apache Harmony JDK):

public int hashCode() {
    if (hashCode == 0) {
        int hash = 0, multiplier = 1;
        for (int i = offset + count - 1; i >= offset; i--) {
            hash += value[i] * multiplier;
            int shifted = multiplier << 5;
            multiplier = shifted - multiplier;
        }
        hashCode = hash;
    }
    return hashCode;
}

what’s the difference between the two above code snippets? As you can see, multiplication can be replaced by a bitwise shift operation and a subtraction for better performance. “(multiplier << 5) – multiplier” is just 31*multiplier after all (however VMs nowadays do this optimization automatically). If you’re interested in good reading on the subject of Binary numbers i strongly recommend Neil Coffey’s Javamex article: Introduction to binary numbers.

 

OK, applying all this knowledge to our sharding code example results in the following implementation:

while(i<1000000) {
    String userId = String.valueOf(i++);
    String emailAddress = String.format("user_%s@mariuszprzydatek.com", userId);
    int shardKey = emailAddress.hashCode();
    redisTemplate.opsForHash().put(String.format("emailsbucket:%s", shardKey), emailAddress, userId);
}

 

Happy coding! 🙂

 

 

Resources: