What's an appropriate HTTP status code to return by a REST API service for a validation failure?

If "validation failure" means that there is some client error in the request, then use HTTP 400 (Bad Request). For instance if the URI is supposed to have an ISO-8601 date and you find that it's in the wrong format or refers to February 31st, then you would return an HTTP 400. Ditto if you expect well-formed XML in an entity body and it fails to parse.

(1/2016): Over the last five years WebDAV's more specific HTTP 422 (Unprocessable Entity) has become a very reasonable alternative to HTTP 400. See for instance its use in JSON API. But do note that HTTP 422 has not made it into HTTP 1.1, RFC-7231.

Richardson and Ruby's RESTful Web Services contains a very helpful appendix on when to use the various HTTP response codes. They say:

400 (“Bad Request”) Importance: High. This is the generic client-side error status, used when no other 4xx error code is appropriate. It’s commonly used when the client submits a representation along with a PUT or POST request, and the representation is in the right format, but it doesn’t make any sense. (p. 381)

and:

401 (“Unauthorized”) Importance: High. The client tried to operate on a protected resource without providing the proper authentication credentials. It may have provided the wrong credentials, or none at all. The credentials may be a username and password, an API key, or an authentication token—whatever the service in question is expecting. It’s common for a client to make a request for a URI and accept a 401 just so it knows what kind of credentials to send and in what format. [...]

From RFC 4918 (and also documented at http://www.iana.org/assignments/http-status-codes/http-status-codes.xhtml):

The 422 (Unprocessable Entity) status code means the server understands the content type of the request entity (hence a 415 (Unsupported Media Type) status code is inappropriate), and the syntax of the request entity is correct (thus a 400 (Bad Request) status code is inappropriate) but was unable to process the contained instructions. For example, this error condition may occur if an XML request body contains well-formed (i.e., syntactically correct), but semantically erroneous, XML instructions.

A duplicate in the database should be a 409 CONFLICT.

I recommend using 422 UNPROCESSABLE ENTITY for validation errors.

I give a longer explanation of 4xx codes here: http://parker0phil.com/2014/10/16/REST_http_4xx_status_codes_syntax_and_sematics/

Here it is:

rfc2616#section-10.4.1 - 400 Bad Request

The request could not be understood by the server due to malformed syntax. The client SHOULD NOT repeat the request without modifications.

rfc7231#section-6.5.1 - 6.5.1. 400 Bad Request

The 400 (Bad Request) status code indicates that the server cannot or will not process the request due to something that is perceived to be a client error (e.g., malformed request syntax, invalid request message framing, or deceptive request routing).

Refers to malformed (not wellformed) cases!

rfc4918 - 11.2. 422 Unprocessable Entity

The 422 (Unprocessable Entity) status code means the server understands the content type of the request entity (hence a 415 (Unsupported Media Type) status code is inappropriate), and the syntax of the request entity is correct (thus a 400 (Bad Request) status code is inappropriate) but was unable to process the contained instructions. For example, this error condition may occur if an XML request body contains well-formed (i.e., syntactically correct), but semantically erroneous, XML instructions.

Conclusion

Rule of thumb: [_]00 covers the most general case and cases that are not covered by designated code.

422 fits best object validation error (precisely my recommendation:) As for semantically erroneous - Think of something like "This username already exists" validation.

400 is incorrectly used for object validation

I would say technically it might not be an HTTP failure, since the resource was (presumably) validly specified, the user was authenticated, and there was no operational failure (however even the spec does include some reserved codes like 402 Payment Required which aren't strictly speaking HTTP-related either, though it might be advisable to have that at the protocol level so that any device can recognize the condition).

If that's actually the case, I would add a status field to the response with application errors, like

4Date range is invalid

There's a little bit more information about the semantics of these errors in RFC 2616, which documents HTTP 1.1.

Personally, I would probably use 400 Bad Request, but this is just my personal opinion without any factual support.

Here's another interesting scenario to discuss.

What if its an type detection API that for instance accepts as input a reference to some locally stored parquet file, and after reading through some metadata of the blocks that compose the file, may realize that one or more of the block sizes exceed a configured threshold and therefor the server decided the file is not partitioning correctly and refuses to start the type detection process. This validation is there to protect against one of two (or both) scenarios: (1) Long processing time, bad user experience ; (2) Server application explodes with OutOfMemoryError

What would be an appropriate response in this case?

400 (Bad Request) ? - sort of works, generically.

401 (Unauthorized i.e. Unauthenticated) ? - unrelated.

403 (Forbidden i.e. Unauthorized) ? - some would argue it may be somewhat appropriate in this case -

422 (Unprocessable entity) ? - many older answers mention this as appropriate option for input validation failure. What bothers me about using it in my case is the definition of this response code saying its "due to semantic error" while I couldn't quite understand what semantic error means in that context and whether can we consider this failure indeed as a semantic error failure.

Also the allegedly simple concept of "input" as part of "input validation" can be confusing in cases like this where the physical input provided by the client is only but a pointer, a reference to some entity which is stored in the server, where the actual validation is done on data stored in the server (the parquet file metadata) in conjunction with the action the client tries to trigger (type detection).

413 (PayloadTooLarge)? Going through the different codes I encounter one that may be suitable in my case, one that no one mentioned here so far, that is 413 PayloadTooLarge which I also wonder if it may be suitable or again, not, since its not the actual payload sent in the request that is too large, but the payload of the resource stored in the server.

Which leads me to thinking maybe a 5xx response is more appropriate here.

507 Insufficient Storage ? If we say that "storage" is like "memory" and if we also say that we're failing fast here with a claim that we don't have enough memory (or we may blow out with out of memory trying) to process this job, then maybe 507 can me appropriate. but not really.

My conclusion is that in this type of scenario where the server refused to invoke an action on a resource due to space-time related constraints the most suitable response would be 413 PayloadTooLarge

What exactly do you mean by "validation failure"? What are you validating? Are you referring to something like a syntax error (e.g. malformed XML)?

If that's the case, I'd say 400 Bad Request is probably the right thing, but without knowing what it is you're "validating", it's impossible to say.

if you are validating data and data is not, according to defined rules its better to send 422(Unprocessable Entity)so that sender will understand that he braking the rules what agreed upon.

Bad request is for syntax errors. some of the tools like postman shows syntax errors upfront.