What is time? Does it flow linearly? If so, how are we sure? Distances in our world (classically at least) can be defined by considering our world to be a model for the Euclidean normed three dimensional space. But how can we set the notion of time on a firm footing? What are the first principles here?
Because almost everywhere in physics, we want to see how a system evolves with “time”. But when I think about it, I can’t find a clear understanding of what time is.
I’m not talking of “the arrow of time”, just time.
Before relativity also, physicists worked with time rates. But how can we be sure that a ticking device is measuring time linearly? As far as I can see, there must be a guaranteed (local, for relativity) existence at every place in the universe of some time keeping mechanism which is infinitely accurate and can be accessed by the observer to read off the time differences between events he observes.
What guarantees such existence?
Basically what I’m asking is against what the rate of time flow is measured. Or asking it is nonsense?
Is there some different way to firmly define this notion?

This is NOT the same question as the marked question, here.
Here, I ask how do we assure that a time keeping device ticks at “equal” intervals? How do we measure these “equal intervals” with? We surely can’t rely on our perception for it.
It is much like (to me) the problem of defining temperature in classical thermodynamics. We have to resort to statistical theory for a firm definition of it. We just can’t say that temperature is proportional to the height of mercury column in a thermometer. Because we’ll, it just isn’t...
 A: Although the answer given above is good, I want to add something for both the OP and future readers of this post.
In your question you state:

. . .But when I think about it, I can’t find a clear understanding of
  what time is.

Physics, as a mainstream science, doesn't seem to have much of an answer to questions about what time actually is.  Physicists certainly wonder about the nature of time in their own spare time just as you seem to be wondering about it.  But as far as normal experimental physics goes, being able to measure time with clocks is about as close to understanding time as we get.  Scientists in general do not have much of any way to resolve issues about things above and beyond what they can measure.
A: Time (specifically proper time) is the thing measured by clocks. We can be sure that equal time intervals measured by clocks are equal because we have defined time to be the thing that clocks measure. If a clock measured twice as much of something and if the thing that clocks measure is defined to be time then what it measured was by definition twice as much time. 
Now, there is no such thing as an ideal clock, but there are some clocks that agree with each other better than other clocks. These clocks that agree with each other well over a long time are used as the standard clocks, and groups of them (at least 3) are used together to detect when one starts to fail electronically or mechanically. Other clocks that are less stable are compared to the standard clocks and adjusted as needed. Clocks that don’t agree with the standard clocks are fixed or removed. 
A: Much of the answer to your question is actually part of philosophy more than physics.  "What is time?" is a famously difficult open ended question in philosophy.  For example, philosophers will question whether time is discrete or continuous.
As for the practical scientist, what we observe is that the things we call clocks (i.e. hour glasses, watches, atomic clocks, etc.) behave in a way which is consistent with each other.  If you look at the state of one clock, you can very reliably predict the state of another clock.  And it seems the more "reliable" a clock is, the more predictable they are.  Atomic clocks, for instance, are known to be remarkably consistent with respect to one another.
When we measure physical events, and reference this against the behaviors of these accurate clocks, we find that there is a very predictable pattern if we assume there is some variable, "time," which is ticked off linearly by these clocks.  When we make this assumption, the laws of physics become "simple."
Thus we use it.  Time can indeed be thought of as nothing more than a convenient analogy for physical behaviors.  Or one may dabble into the philosophy to dig deeper.
Or, as an alternative, consider a reversed method of thinking. The thing scientists refer to as "time" is that which best fits the observations made about clocks.  After all, science is an art of drawing conclusions about reality using data.
A: In a comment you wrote:

But suppose that the group of clocks we chose were such that they ticked in unison but the length between successive ticks increased quadratically with each number of tick.

You seem to have a mental model of our universe as being some sort of simulation that’s running on a computer in some meta-universe, which has a notion of “meta-time” that you are thinking of as the “true” time. And yes, in this mental model it’s possible to imagine the operators of the simulation programming their computer to speed up or slow down the speed at which the simulation is running according to a quadratic function, or indeed any other nonlinear function. For example, they could decide that on meta-Mondays and meta-Wednesdays they will pause the simulation entirely between meta-noon and meta-1 pm to go eat meta-lunch. How would we humans know that this has happened? Well, we wouldn’t, because we are living inside the simulation, so while the simulation was paused, we would be paused too. When it resumes, we would resume too, and to us it would seem that the moment after meta-1 pm came immediately after the moment before meta-noon. From our point of view we would experience a sense of time flowing “linearly” and continuously, despite the discontinuity when you look at things in the meta-time parameter.
The key to resolving this difficulty, and to answering your “how can we be sure” question, is to recognize that these sorts of questions are meaningless within the framework of scientific theories and the scientific method. Specifically, your speculative theory about time flowing quadratically with respect to a more “true” time variable lacks the property of falsifiability, which is one of the basic requirements a scientific theory must satisfy:

I shall require that [the] logical form [of the theory] shall be such that it can be singled out, by means of empirical tests, in a negative sense: it must be possible for an empirical scientific system to be refuted by experience.
— Karl Popper, Popper 1959. p 19

The point is that science deals only with scientific questions, and what makes a question scientific is if it can be tested via experiment. Your question belongs to a class of “what if” questions that involve assumptions about how the universe “really” works, or what is happening “behind the curtains” or “under the hood” or “outside the simulation”, which invariably cannot be tested by any experiment, and therefore are not scientific questions. They may be debated by philosophers, or sometimes by physicists if they are in a certain mood, but they are not really mainstream physics questions, and physics has nothing useful to say about them.
(With that being said, such questions seem to be very common on this site, and are often interesting and entertaining to think about, so I don’t mean to suggest that there’s anything wrong with your asking about this.)
